; Scheme and the Art of Programming
; Chapter 2

(define testlist '(1 2 3 4 5 6 7 8 9 10))

; -- Exercise 2.0: first
; This is a wrapper procedure which makes explicit the 
; fact that car returns the first element in a list.
; Precondition: The input list is non-empty.
; Postcondition: Returns the first element in list. 
(define (first ls) (car ls))

; -- Exercise 2.1: second
; Define a procedure second that takes as its argument a 
; list and returns the second item in the list.  
; Precondition: The input list contains atleast two items.
; Postcondition: Returns the second element in list.

(define (second ls) (cadr ls))

(second testlist)
;Value: 2

; -- Exercise 2.2: third
; Define a procedure third that takes as its argument a 
; list and returns the third item in the list.  
; Precondition: The input list contains atleast three items.
; Postcondition: Returns the third element in list.

(define (third ls) (caddr ls))

(third testlist)
;Value: 3

; -- Exercise 2.3: firsts-of-both
; Define a procedure firsts-of-both that takes as its 
; arguments two lists, and returns a list comprised of 
; the first two elements of its arguments.
; Precondition: The two lists must be non-empty.
; Postcondition: A list of size two.

(define (firsts-of-both ls1 ls2)
  (list (car ls1) (car ls2)))

(firsts-of-both testlist testlist)
;Value 12: (1 1)

; -- Exercise 2.4: juggle
; Define a procedure juggle that rotates a three element 
; list.  The procedure juggle returns a list that is a 
; rearrangement of the input list so that the first 
; element of the input list so that the first element 
; of this list becomes the second, the second element 
; becomes the third, and the third element becomes the 
; first.
; Precondition: The input list contains three elements.

(define test1 '(jump quick spot))
(define test2 '(dog bites man))

(define (juggle ls) (list (third ls) (first ls) (second ls)))

(juggle test1)
;Value 14: (spot jump quick)
(juggle test2)
;Value 15: (man dog bites)

; -- Exercise 2.5: switch
; Define a procedure switch that interchanges the first 
; and third element.
; Precondition: The input list contains three elements.

(define (switch ls) (list (third ls) (second ls) (first ls)))

(switch test2)
;Value 17: (man bites dog)


; -- Exercise 2.6:
(define a #t)
(define b #t)
(define c #t)
(define e #f)
(define f #f)

; Decide whether the following expressions are true or false.

(and a (or b e))
;Value: #t
(or e (and (not f) a c))
;Value: #t
(not (or (not a) (not b)))
;Value: #t
(and (or a f) (not (or b e)))
;Value: ()


; -- Exercise 2.7:
(define expr #t)

; Decide whether the following expressions are true or false.

(or (symbol? expr) (not (symbol? expr)))
;Value: #t

(and (null? expr) (not (null? expr)))
;Value: ()

(not (and (or expr #f) (not expr)))
;Value: #t


; -- Exercise 2.8:
(define (s-and-n-list? ls)
  (and (pair? ls)
       (symbol? (car ls))
       (pair? (cdr ls))
       (number? (cadr ls))))

; Decide whether the following expressions are true or false.

(s-and-n-list? '(2 pair 12 dozen))
;Value: ()

(s-and-n-list? '(b 4 u c a j))
;Value: #t

(s-and-n-list? '(a ten))
;Value: ()

(s-and-n-list? '(a))
;Value: ()


; -- Exercise 2.9:
(define (s-or-n-list? ls)
  (and (pair? ls)
       (or (symbol? (car ls))
	   (number? (car ls)))))

; Decide whether the following expressions are true or false.

(s-or-n-list? '(b))
;Value: #t

(s-or-n-list? '(c 2 m))
;Value: #t

(s-or-n-list? '(10 10 10 10))
;Value: #t

(s-or-n-list? '())
;Value: ()


; -- Exercise 2.10
; Write the following procedures:

; last-item accepts a list as its argument and 
; returns the last element in the list.
; precondition: the list ls must contain atleast one value

(define (last-item ls)
  (if (null? (cdr ls)) (car ls) (last-item (cdr ls))))

(last-item testlist)
;Value: 10

; member? accepts a symbol and a list and returns 
; true if the symbol can be found in list or false otherwise
; Precondition: The input list contains only symbols

(define (member? a ls)
  (if (null? ls) #f (or (eq? (car ls) a) (member? a (cdr ls)))))

(member? 10 testlist)
;Value: #t
(member? 4 testlist)
;Value: #t
(member? a testlist)
;Value: ()

; remove-1st accepts a symbol and a list, and returns a list 
; without the first occurence of that symbol.

(define (remove-1st a ls)
  (if (null? ls) ls 
      (if (eq? (car ls) a) 
	  (cdr ls)
	  (cons (car ls) (remove-1st a (cdr ls))))))

(remove-1st 7 testlist)
;Value 19: (1 2 3 4 5 6 8 9 10)

(define testlist '(1 2 3 4 5 6 7 8 9 10))

; -- Exercise 2.11
; Define a procedure member? which takes as its 
; argument an atom and a list and returns true if 
; the atom is found in a list and false otherwise

(define (member? atom list)
  (cond
   ((null? list) #f)
   ((equal? atom (car list)) #t)
   (else (member? atom (cdr list)))))

(member? 5 testlist)
;Value: #t

(member? 12 testlist)
;Value: ()


; -- Exercise 2.12

(define mystery 
  (lambda (ls)
    (if (null? (cddr ls))
	(cons (car ls) '())
	(cons (car ls) (mystery (cdr ls))))))

(mystery '(1 2 3 4 5))
;Value 12: (1 2 3 4)


; -- Exercise 2.13
; Define a procedure subst-1st that takes three parameters: 
; an item new, an item old, and a list of items ls.  The 
; procedure subst-1st looks for the first top-level 
; occurence of the item old in ls and replaces it with the 
; item new.

(define (subst-1st new old ls)
  (cond
   ((null? ls) '())
   ((equal? old (car ls)) (cons new (cdr ls)))
   (else (cons (car ls) (subst-1st new old (cdr ls))))))

(subst-1st 'dog 'cat '(my cat is clever))
;Value 15: (my dog is clever)

(subst-1st 'b 'a '(c a b a c))
;Value 16: (c b b a c)

(subst-1st '(0) '(*) '((*) (1) (*) (2)))
;Value 17: ((0) (1) (*) (2))

(subst-1st 'two 'one '())
;Value: ()

; Note: In order to be able to include lists as possible 
; arguments to which the parameters new and old are bound, 
; we must use equal? to test.


; -- Exercise 2.14
; Define a procedure insert-left-1st that takes three 
; arguments: an item new, an item old, and a list ls. 
; The procedure should insert the item new to the left 
; the item old.

(define (insert-left-1st new old ls)
  (cond
   ((null? ls) '())
   ((eq? old (car ls)) (cons new ls))
   (else (cons (car ls) (insert-left-1st new old (cdr ls))))))

(insert-left-1st 'hot 'dogs '(I eat dogs))
;Value 18: (i eat hot dogs)

(insert-left-1st 'fun 'games '(some fun))
;Value 19: (some fun)

(insert-left-1st 'a 'b '(a b c a b c))
;Value 20: (a a b c a b c)

(insert-left-1st 'a 'b '())
;Value: ()


; -- Exercise 2.15
; Define a procedure list-of-first-items that takes as its 
; argument a list composed of nonempty lists of items.  Its 
; value is a list composed of the first top-level item in 
; each of the sublists.
; Precondition: The input list contains only non-empty lists

(define (list-of-first-items ls)
  (if (null? ls) '()
      (cons (caar ls) (list-of-first-items (cdr ls)))))

(list-of-first-items '((a) (b c d) (e f)))
;Value 21: (a b e)

(list-of-first-items '((1 2 3) (4 5 6)))
;Value 22: (1 4)

(list-of-first-items '((one)))
;Value 23: (one)

(list-of-first-items '())
;Value: ()


; -- Exercise 2.16
; Define a procedure replace that replaces each top-level 
; item in a list of items ls by a given new-item.

(define (replace new-item ls)
  (if (null? ls) '() (cons new-item (replace new-item (cdr ls)))))

(replace 'no '(will you do me a favor))
;Value 25: (no no no no no no)

(replace 'yes '(do you like ice cream))
;Value 26: (yes yes yes yes yes)

(replace 'why '(not))
;Value 27: (why)


; -- Exercise 2.17
; Define a procedure remove-2nd that removes the second 
; occurence of a given item a from a list of items ls.

(define (remove-1st a ls)
  (cond
   ((null? ls) '())
   ((eq? a (car ls)) (cdr ls))
   (else (cons (car ls) (remove-1st a (cdr ls))))))

(define (remove-2nd a ls)
  (cond
   ((null? ls) '())
   ((eq? a (car ls)) (cons a (remove-1st a (cdr ls))))
   (else (cons (car ls) (remove-2nd a (cdr ls))))))

(remove-2nd 'cat '(my cat loves cat food))
;Value 31: (my cat loves food)


; -- Exercise 2.18
; Define a procedure remove-last that removes the last 
; top-level occurence of a given element item in a list ls.


; -- Exercise 2.19
; Define a procedure sandwich-1st that takes two items, a 
; and b, and a list ls as its arguments.  It replaces the 
; first occurence of two successive b's in ls with b a b. 

(define (sandwich-1st a b ls)
  (cond
   ((null? ls) '())
   ((= (length ls) 1) ls)
   ((and (eq? (car ls) b) (eq? (car ls) (cadr ls))) 
    (cons b (cons a (cdr ls))))
   (else (cons (car ls) (sandwich-1st a b (cdr ls))))))

(sandwich-1st 'meat 'bread '(bread cheese bread bread))
; Value 35: (bread cheese bread meat bread)

(sandwich-1st 'meat 'bread '(bread jam bread cheese bread))
; Value 36: (bread jam bread cheese bread)

(sandwich-1st 'meat 'bread '())
; Value 37: ()


; -- Exercise 2.20
; Define a procedure list-of-symbols? that tests whether 
; a given list ls is a list of top-level symbols.

(define (list-of-symbols? ls)
  (if (null? ls) 
      #t 
      (and (symbol? (car ls)) (list-of-symbols? (cdr ls)))))

(list-of-symbols? '(one two three four five))
; Value 38: #t

(list-of-symbols? '(cat dog (hen pig) cow))
; Value 39: #f

(list-of-symbols? '(a b 3 4 d))
; Value 40: #f

(list-of-symbols? '())
; Value 41: #t


; -- Exercise 2.21
; Define a procedure all-same? that takes a list ls as 
; its argument and tests whether all top-level elements 
; of ls are the same.

(define (all-same? ls)
  (cond
   ((null? ls) #t)
   ((= (length ls) 1) #t)
   (else (and (equal? (car ls) (cadr ls)) (all-same? (cdr ls))))))

(all-same? '(a a a a a))
; Value 42: #t

(all-same? '(a b a b a b))
; Value 43: #f

(all-same? '((a b) (a b) (a b)))
; Value 44: #t

(all-same? '(a))
; Value 45: #t

(all-same? '())
; Value 46: #t