; Julie Petrusa

; 991339





;--------------------------------------------------------------------------------------

; 1.



; - returns #f if a is not an atom, i.e., if it is a pair

; - returns #t otherwise



(define atom?

  (lambda (a)

    (cond

      ((pair? a) #f)            

      (else #t))))             

;--------------------------------------------------------------------------------------

; 2.



; - if a is a number, returns its square

; - if a is a non­empty list, returns its length

; - returns a otherwise



(define myfunc 

  (lambda (a)

    (cond

      ((number? a) (* a a))     

      ((pair? a) (length a))    

      (else a))))               

;--------------------------------------------------------------------------------------

; 3.



; - if lst is not a list, returns an error message

; - if lst does not contain at least n elements, returns an error message

; - bottoming out of recursion: if n = 0, returns the remaining sublist after the 

;   first n elements of lst have been removed 

; - recursion: otherwise calls list-tail with (lst without 1st item) and (n - 1)



(define list-tail

  (lambda (lst n)

    (cond 

      ((eq? (list? lst) #f) "lst is not a list") 

      ((< (length lst) n) "n is too large")      

      ((= n 0) lst)                              

      (else (list-tail (cdr lst) (- n 1))))))    

;--------------------------------------------------------------------------------------

; 4.



; - defines a new list that will hold the first n elements of lst

; - if lst is not a list, returns an error message

; - if lst does not contain at least n elements, returns an error message

; - bottoming out of recursion: if n = 0, returns a list with the first

;   n elements of lst 

; - recursion: otherwise calls list-head with (lst without 1st item) and (n - 1) 

;   and cons it with (the first member of lst)



(define list-head

  (lambda (lst n)

    (define newlst (list))                       

    (cond 

      ((eq? (list? lst) #f) "lst is not a list")

      ((< (length lst) n) "n is too large")      

      ((= n 0) newlst)                           

      (else (cons (car lst) (list-head (cdr lst) (- n 1)))))))    

;--------------------------------------------------------------------------------------

; 5.

  

; - if lst is null, returns empty lst

; - if lst is not a list, returns an error message

; - bottoming out of recursion: if (length of lst = 0), returns a list containing 

;   a boolean for each element of lst indicating whether it is an atom   

; - recursion: if (the first member of lst) is an atom, calls atoms with 

;   (lst without 1st item) and cons it with #t

; - recursion: otherwise calls atoms with (lst without 1st item) and cons it with #f



(define atoms

  (lambda (lst)                              

    (cond

      ((null? lst) '())                           

      ((eq? (list? lst) #f) "lst is not a list")                   

      ((atom? (car lst)) (cons #t (atoms (cdr lst)))) 

      (else (cons #f (atoms (cdr lst))))))) 

;--------------------------------------------------------------------------------------

; 6.

                                                 

; - if lst is null, returns empty lst

; - if a is not an atom, returns an error message

; - if b is not an atom, returns an error message

; - if lst is not a list, returns an error message

; - bottoming out of recursion: if (length of lst = 0), returns a copy of lst 

;   with every occurence of a in lst (at the top level only) replaced by b

; - recursion: if a is equal to (the first member of lst), calls substitute with

;   a, b, and (lst without first item) and cons it with b

; - recursion: otherwise calls substitute with a, b, and (lst without first item)

;   and cons it with (the first member of lst)



(define substitute

  (lambda (a b lst)

    (cond

      ((null? lst) '())

      ((eq? (atom? a) #f) "a is not an atom")

      ((eq? (atom? b) #f) "b is not an atom")

      ((eq? (list? lst) #f) "lst is not a list")

      ((equal? a (car lst)) (cons b (substitute a b (cdr lst))))

      (else (cons (car lst) (substitute a b (cdr lst))))))) 

;--------------------------------------------------------------------------------------

; 7.



; - if lst is null, returns empty lst

; - if lst is not a list, returns an error message

; - if (the first member of lst) is not a number, returns an error message

; - bottoming out of recursion: if (length of lst = 0), returns a list 

;   in which each element is 1 greater than the corresponding element of lst

; - recursion: otherwise calls add1-to-each with (lst without 1st item) and cons

;   it with (the first member of lst) plus one

 

(define add1-to-each

  (lambda (lst)

    (cond

      ((null? lst) '())

      ((eq? (list? lst) #f) "lst is not a list")      

      ((eq? (number? (car lst)) #f) "lst is not a list of numbers")

      (else (cons (+ 1 (car lst)) (add1-to-each (cdr lst)))))))

;--------------------------------------------------------------------------------------

; 8.



; - if a is not an atom, returns an error message

; - if lst is not a list, returns an error message

; - if lst is null, returns #f

; - if a is equal to (the first member of list), returns #t

; - bottoming out of recursion: if (length of lst = 0), returns #t if a occurs in lst 

;   at any level, #f otherwise 

; - recursion: if (the first member of lst) is a list, calls deep-search with a and 

;   (the first member of lst) appended to (lst without first item)

; - recursion: otherwise calls deep-search with a and (lst without first item)



(define deep­search

  (lambda (a lst)

    (cond     

      ((eq? (atom? a) #f) "a is not an atom")

      ((eq? (list? lst) #f) "lst is not a list")

      ((null? lst) #f)

      ((equal? a (car lst)) #t)

      ((list? (car lst)) (deep­search a (append (car lst) (cdr lst))))

      (else (deep­search a (cdr lst))))))

;--------------------------------------------------------------------------------------

; 9.



; - if lst is null, returns empty lst

; - if lst is not a list, returns an error message

; - bottoming out of recursion: if (length of lst = 0), returns the reverse of lst 

;   with all sublists at all levels also reversed 

; - recursion: if (the first member of lst) is a list, calls deep-reverse with 

;   (lst without first item) and appends it to the reverse of (the first member of lst)

; - recursion: otherwise calls deep-reverse with (lst without first item) and appends 

;   it to (the first member of lst)

       

(define deep­reverse

  (lambda (lst)

    (cond

      ((null? lst) '())

      ((eq? (list? lst) #f) "lst is not a list") 

      ((list? (car lst)) (append (deep­reverse (cdr lst)) (list (reverse (car lst)))))

      (else (append (deep­reverse (cdr lst)) (list (car lst)))))))

;--------------------------------------------------------------------------------------