;; Sample solutions for list exercises.
;;
;; a word on notation. I've used some shorthand notations to describe 
;; scheme lists in places, for example I refer to the list:
;;  (cons 'hi (cons 1 (cons 'world empty)))
;;   simple as (list 'hi 1 'world)
;;
;;  you may notice that scheme does this also, and that in fact list is
;;  and operation!

;;
;; lon-equal? consumes two lists and produces a boolean
;;
;; (lon-equal? alist blist) 
;;    is true only if the lists are the same size, and the corresponding
;;    elements are equal (in the number sense). This will only work for
;;    lists of numbers, since it uses the primitive operation '=' to 
;;    compare two list entries.
;;
;;    If the lists are not the same length, this function will
;;    evaluate to false.
;;

(define (lon-equal? l1 l2) 
  (cond 
   ;; if both lists are empty - they are equal!
    [ (and (empty? l1) (empty? l2)) true ]

   ;; otherwise - if only one is empty - the lists can't be equal
    [(or (empty? l1) (empty? l2)) false]

   ;; neither list is empty - if the first elements of the lists are 
   ;; not equal we can say that the lists are not equal.
    [(not (= (first l1) (first l2))) false]

   ;; if we get here it means the first elements are equal - now just check the
   ;;    rest of the lists.
    [else 
	 (lon-equal? (rest l1) (rest l2)) ]))

;; test code
;; (lon-equal? empty empty)            ;; should produce true
;; (lon-equal? (cons 1 empty) empty)   ;; should produce false
;; (lon-equal? 
;;      (cons 1 (cons 2 empty))
;;      (cons 2 (cons 1 empty)))       ;; should produce false
;;
;; (lon-equal? 
;;       (cons 2 (cons 3 (cons 5 empty)))
;;       (cons 2 (cons 3 (cons 5 empty)))) ;; should produce true


;; addright consumes a value and a list and produces a list.
;;
;;   (addright elem alist) will add elem to the right end of the 
;;       list alist - the value of the function is this new list.
;;

(define (addright elem alist)
  (cond
   [ (empty? alist) (cons elem alist) ]
   [ else 
	 (cons (first alist) (addright elem (rest alist)))]))

;; test code for addright
;; (addright 'blah (cons 1 (cons 'hi empty)))   ;; should produce
;;                                            ;; (list 1 'hi 'blah)
;;  (addright 'only empty)        ;; should produce (list 'only)


;;
;; remove-first consumes a list and produces a list
;;
;; (remove-first alist) produces the list given by (rest alist)
;; This is trivial...
;;
(define (remove-first alist)
  (rest alist))


;;
;; remove-last consumes a list and produces a list
;;
;; (remove-last alist) produces the list alist with the rightmost element
;;   removed.
;;
;; NOTE: this implementation generates an error if the list given is 
;;   empty (since it can't find anything to remove). There may be situations
;;   in which you might not want this behavior - you might want it to
;;   simply produce the empty list in this case.

(define (remove-last alist)
  (cond
   [(empty? alist) (error 'remove-last "There is no last - the list is empty!")]
   [(empty? (rest alist)) empty]
   [else
	(cons (first alist) 
		  (remove-last (rest alist)))]))

;; test-code for remove-first and remove-last

;; (remove-first (cons 1 (cons 2 empty)))    ;; (list 2)
;; (remove-last (cons 1 (cons 2 empty)))     ;; (list 1)
;; (remove-last (cons 1 empty))              ;; empty
;; (remove-last empty)                       ;; this will generate an error


;;
;; sum-lons consumes two lists and produces a list.
;;
;; (sum-lons alist blist) 
;;    treats both lists as lists of numbers.
;;    constructs a new list of the same size as alist,blist 
;;    (they are expected to be the same size).
;;   
;;    The new list produced by sum-lons is constructed 
;;    by setting the first element of the new list to be the
;;    sum of the first element of alist with the first element of blist.
;;    The second element of the list produced is the sum of the second
;;    elements of alist,blist (and so on).
;;
;;    If the lists are not the same size, this function generates an error.

(define (sum-lons alist blist)
 (cond
  [ (and (empty? alist) (empty? blist)) empty ]
  [ (or (empty? alist) (empty? blist))
	(error 'sum-lons "Can't sum lists of number - they don't have same number if elements")]
  [ else
	(cons 
	 (+ (first alist)
		(first blist))
	 (sum-lons (rest alist) (rest blist)))]))

;; test code for sum-lons

;; (sum-lons
;;   (cons 1  (cons 3.3 empty))
;;   (cons 12 (cons 4 empty)))  ;; should produce (list 13 7.3)



;;
;; reverse-lon consumes a list and produces a list.
;;
;; (reverse-lon alist) 
;;    alist is a list of numbers (although this function doesn't
;;    really care - it would work fune with any kind of list).
;;    
;;  the list produced is the revers if alist, so the first element is
;;  moved to the right, the second element becomes second to last, etc.
;;
;;  This function uses the addright function defined above.
;;  
(define (reverse-lon alist)
  (cond
   [(empty? alist) empty]
   [else
	(addright (first alist) (reverse (rest alist)))]))

;; test code for reverse-lon
;;
;; (reverse-lon (cons 1 (cons 2 (cons 3 empty)))) 
;;     ;; should produce (list 3 2 1)