CSC 324, Summer 2001

Tutorial notes for week 4

****************************************************************

This tutorial emphasizes the use of higher-order functions to create
simple solutions using functions they have already written.


A. Set operations. The arguments are two lists (non-nested).

(union lst1 lst2) => returns a list consisting of all elements in
  either lst1 or lst2, with no duplicates.

(define (union lst1 lst2) 
  (cond ((null? lst1) lst2)
        ((member (car lst1) lst2)
         (union (cdr lst1) lst2))
        (else (cons (car lst1) (union (cdr lst1) lst2)))
  )
)  


(intersection lst1 lst2) => returns a list consisting of all the
  elements that are in both lst1 and lst2.

(define (intersection lst1 lst2)
  (cond ((null? lst1) '())
        ((member (car lst1) lst2)
         (cons (car lst1) (intersection (cdr lst1) lst2)))
        (else (intersection (cdr lst1) lst2))
  )
)


Further practice:

(difference lst1 lst2) => returns a list consisting of all elements
  that are in lst1 and NOT in lst2.


************************************************************

(B) Higher-Order Functions (HOFs such as 'map', 'apply', 'eval', and
'reduce')

++++++++++++++++
(intersect-all lst1 lst2) => returns a list of elements that
  corresponding sublists of lst1 and lst2 have in common, with no
  duplicates.  (lst1 and lst2 are lists of lists, with the same number
  of sublists.)

  Example:  If l1 is '((1 2 4 5) (2 4 5) (3 8))
               l2 is '((1 3 5) (2 5) (1 5 8))

            (intersect-all l1 l2) => (1 2 5 8)

  (Note: order of elements in result doesn't matter. )

++++++++++++++++
(union-all lst1 lst2) => returns a list of elements consisting of the
  union of corresponding sublists of lst1 and lst2, with no
  duplicates.  (lst1 and lst2 are lists of lists, with the same number
  of sublists.)

  Example:  If l1 is '((1 2 4 5) (2 4 5) (3 8))
               l2 is '((1 3 5) (2 5) (1 5 8))

            (union-all l1 l2) => (1 2 3 4 5 8)

  (Note: order of elements in result doesn't matter)

++++++++++++++++
(in-all-lists e lst) => returns #t if e is in every sublist
  of lst, #f/() otherwise.  (lst is a list of lists.)  Note: If lst is
  empty, then in-all-lists should return #f.

  Example: (in-all-lists 5 '((1 3 5) (2 5) (1 5 8))) => #t
           (in-all-lists 1 '((1 3 5) (2 5) (1 5 8))) => #f
           (in-all-lists 1 '()) => #f


SOLUTIONS:

Helper function:

(define (rm-dups lst)
  (cond ((null? lst) '())
        ((member (car lst) (cdr lst))
         (rm-dups (cdr lst)))
        (else (cons (car lst) (rm-dups (cdr lst))))
))
++++++++++++++++
(define (intersect-all lst1 lst2)
  (rm-dups (apply append (map intersection lst1 lst2)))
)
++++++++++++++++
(define (union-all lst1 lst2)
  (rm-dups (apply append (map union lst1 lst2)))
)

**** NOTE: This is exactly like intersection.  See if you can think
of an alternative way to do this, as:

(define (union-all lst1 lst2)
  (rm-dups (union (apply append lst1) (apply append lst2)))
)

**** There's even a way that uses union twice!

(define (union-all lst1 lst2)
  (reduce union (map union lst1 lst2) '())
)

Here's reduce from the lecture notes:
(define (reduce op l id)
 (if (null? l) 
     id
     (op (car l) 
         (reduce op (cdr l) id))
))

++++++++++++++++
(define (in-all-lists e lst)
  (cond ((null? lst) #f)
        (else (in-all-lists-helper e lst))
))
(define (in-all-lists-helper e lst)
  (or (null? lst)
      (and (member e (car lst))
           (in-all-lists-helper e (cdr lst))))
)

**** NOTE:

**** You can't use map on member here, because you have one element
     and a list of lists, not two lists of arguments that map could
     apply member to.

**** You need to use the helper function to get the base cases to work
     out right -- ie, if the list of lists is initially null, you must
     return false, but the recursive step on null list needs to return
     true. 

**** You may feel more comfortable using cond in the helper function, 
     but this is not as nice code.  It is better to use cond (or if) in
     the main function, as it emphasize the special case of the initial
     null list.  Another option that is fine is a combination of cond and
     'and' in the helper function.

Using cond and 'and' (good):
(define (in-all-lists-helper e lst)
  (cond ((null? lst) #t)
        (else (and (member e (car lst))
                   (in-all-lists-helper e (cdr lst))))
))

Using cond only (not so good):
(define (in-all-lists-helper e lst)
  (cond ((null? lst) #t)
        ((member e (car lst))
         (in-all-lists-helper e (cdr lst))))
        (else #f)
))