#lang racket
; Returns the length of a list.
(define (list-length xs)
  (if (null? xs)
      0
      (+ 1 (list-length (rest xs)))))
; rest means the same thing as cdr,
; but makes clear that we are using this cons cell as a list.

; Returns the sum of a a list of numbers.
(define (sum xs)
  (if (null? xs)
      0
      (+ (first xs) (sum (rest xs)))))
; first means the same thing as car,
; but makes clear that we are using this cons cell as a list.
  
; Returns a list with consecutive integers in order from lo to hi.
(define (range lo hi)
  (if (<= hi lo)
      null
      (cons lo (range (+ lo 1) hi))))
; Note it is crucial that we use cons, NOT list, for incremental list building.
; They definitely result in different things.
  
; Returns a list where each element is the square
; of the corresponding element in xs.
(define (squares xs)
  (if (null? xs)
      null
      (cons (* (first xs) (first xs)) (squares (rest xs)))))
  
; Returns a list containing only even numbers in xs, in order.
(define (evens xs)
  (if (null? xs)
      null
      (if (= 0 (modulo (first xs) 2))
          (cons (first xs) (evens (rest xs)))
          (evens (rest xs)))))
  
; Returns #t if the list ys contains element x and #f otherwise.
(define (contains? x ys)
  (if (null? ys)
      #f
      (or (equal? x (first ys)) ; = is for numbers, equal? is general
          (contains? x (rest ys)))))
(define (contains?-if x ys)
  (if (null? ys)
      #f
      (if (equal? x (first ys))
          #t
          (contains? x (rest ys)))))
(define (contains?-noif x ys)
  (and (cons? ys)
       (or (equal? x (first ys))
          (contains? x (rest ys)))))

; Returns a new list containing all the elements of ys, in order,
; except x.
(define (remove x ys)
  (if (null? ys)
      null
      (if (equal? x (first ys))
          (remove x (rest ys))
          (cons (first ys) (remove x (rest ys))))))
  
; Returns #t if the list is in sorted order and #f otherwise.
(define (sorted? xs)
  (or (null? xs) ; empty list is sorted
      (null? (rest xs)) ; 1-element list is sorted
      (and (<= (first xs) (second xs)) ; first 2 elems in order
           (sorted? (rest xs))))) ; rest of list is sorted

; Returns a list containing all of the elements of xs, but
; with no duplicates.
(define (dedup xs)
  (if (null? xs)
      null
      (cons (first xs) (dedup (remove (first xs) (rest xs))))))