'(1 2 3) |-> (2 3 4)
'(a b)   |-> ((a 3) (b 4))

test whether 7 is a member of a list
'(a 7 9) |-> (() T ()) |-> T

(set mapcar
  ; TYPE: (a -> b), list of a -> list of b
  (lambda (f lst)
    (if (null? lst) '()
      (cons (f (car lst))
	    (mapcar f (cdr lst))))))

(mapcar add1 '(1 2 3))
   = (2 3 4)
(mapcar (lambda (x) (list2 x 3)) '(a b))
   = ((a 3) (b 4))
(mapcar (lambda (y) (= 7 y)) '(a 7 9))
   = (() T ())

(set mapc
  ;TYPE:(a -> b)
  ;   ->  (list of a -> list of b)
  (lambda (f)
    (lambda (lst)
      (if (null? lst) '()
	(cons (f (car lst))
	      ((mapc f) (cdr lst)))))))

((mapc add1) '(1 2 3))
  = (2 3 4)
(set add1* (mapc add1))
(add1* '(2 3 1))
  = (3 4 2)
(set seven-checker
 (mapc (lambda (y) (= 7 y))))
(seven-checker '(a 7 9))
  = (() T ())

(set false '())

(set =c
  ; TYPE: o -> (o -> bool)
  (lambda (x)
    (lambda (y)
      (= x y))))

(set seven-checker (mapc (=c 7)))
(seven-checker '(a 7 9))
  = (() T ())

(set member
  ; TYPE: a, list of a -> bool
  (lambda (x lst)
    (if (null? lst) false
      (if (= x lst) true
	(member x (cdr lst))))))

(set memberc
  ; TYPE: a -> (list of a -> bool)
  (lambda (x)
    (lambda (lst)
      (if (null? lst) false
	(if (= x lst) true
	  ((memberc x) (cdr lst)))))))

; simpler still
(set curry
  ; TYPE: (a,b -> c) -> (a -> (b -> c))
  (lambda (f)
    (lambda (x)
     (lambda (y)
       (f x y)))))

(set mapc (curry mapcar))
(set =c (curry =))
(set memberc (curry member))

	SETS
(set find
  ; TYPE: (a -> bool), list of a -> bool
  (lambda (pred lis)
    (if (null? lis) '()
      (if (pred (car lis)) 'T
	(find pred (cdr lis))))))

(set nullset '())  ; TYPE: set of s-exp
(set addelt
 ;TYPE: s-exp,set of s-exp -> set of s-exp
 (lambda (x s)
   (if (member? x s) s
     (cons x s))))
(set member?
  ; TYPE: s-exp, set of s-exp -> bool
  (lambda (x s)
    (find ((curry equal) x) s)))
(set union
  ; TYPE: set of s-exp, set of s-exp
  ;        -> set of s-exp
  (lambda (s1 s2)
    ((combine id addelt s1) s2)))

	THE PROBLEM
(set equal 
  ; TYPE: s-exp, s-exp -> bool
  (lambda (l1 l2)
    (if (atom? l1) (= l1 l2)
      (if (atom? l2) false
	(if (equal (car l1) (car l2))
	    (equal (cdr l1) (cdr l2))
	  false)))))

(set member?
  ; TYPE: s-exp, list of s-exp -> bool
  (lambda (x s)
    (if (equal x s) true
	(member? x (cdr s)))))

(set al-member?
  ; TYPE: alist, list of alist -> bool
  (lambda (x s)
    (if (=alist x s) true
	(member? x (cdr s)))))

             ; FIRST APPROACH
(set nullset '())  ; TYPE: all a. set of a
(set addelt
 ;TYPE: all a. a, set of a, (a,a -> bool)
 ;        -> set of a
   (lambda (x s eqfun)
     (if (member? x s eqfun) s
       (cons x s))))
(set member?
  ;TYPE: all a. a, set of a, (a,a -> bool)
  ;       -> bool
  (lambda (x s eqfun)
    (find ((curry eqfun) x) s)))
(set union
  ; TYPE: all a. set of a, set of a, 
  ;        (a,a -> bool) -> set of a
  (lambda (s1 s2 eqfun)
    ((combine id
	      (lambda (x s)
		(addelt x s eqfun))
	      s1)
     s2)))

             ; SECOND APPROACH
(set nullset
  ; TYPE: all a. (a,a->bool) -> set of a
  (lambda (eqfun) (lst2 eqfun '())
(set set-test
  (lambda (s) (car s)))
(set set-elems
  (lambda (s) (cadr s)))
(set set-cons
  (lambda (x s)
    (list2 (set-test s)
	   (cons x (set-elems)))))

(set addelt
 ;TYPE: all a. a, set of a -> set of a
   (lambda (x s)
     (if (member? x s) s
       (set-cons x s))))
(set member?
  ;TYPE: all a. a, set of a -> bool
  (lambda (x s)
    (find ((curry (set-test s)) x)
	  (set-elems s))))
; ...

             ; THIRD APPROACH
(set mk-set-ops
 ; TYPE: all a. (a,a -> bool)
 ;       -> list of objects + functions
 (lambda (eqfun)
   (cons '()  ; empty set
   (cons (lambda (x s)  ; member?
         (find ((curry eqfun) x) s))
   (cons (lambda (x s) ; addelt
	   (if (find ((curry eqfun) x) s)
	       s
	     (cons x s)))
	 '()
       )))))

(set list-of-al-ops (mk-set-ops =alist))
(set al-nullset (car list-of-al-ops))
(set al-member? (cadr list-of-al-ops))
(set al-addelt (caddr list-of-al-ops))