Chapter 3 - Cons the Magnificent#
1996 Friedman, Daniel P. & Matthias Felleisen. The Little Schemer. 4e. MIT Press.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Chapter 3 - Cons the Magnificent
; REMBER - "remove a member"
; removes the first occurrence of a given atom from a lat
; inputs: atom, lat
; output: lat
;
; constructing function rember
; first commandment (prelim) - always ask null? as the first question in expressing any function
; first commandment (final) - when recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else
; second commandment - use cons to build lists
; third commandment - when building a list, describe the first typical element, and then cons it onto the natural recursion
; fourth commandment (prelim) - always change at least one argument while recurring; it must be changed to be closer to termination; the changing argument must be tested in the termination condition: when using cdr, test termination with null?.
; look at each atom in a lat, in turn, and ask if it is the given atom, until it runs out of atoms
; if the current atom is not the given atom, it saves it to be consed to the final lat later
; if the current atom is the given atom, it drops it and conses the previous atoms back onto the rest of the lat
;
; (define rember
; (lambda (a lat)
; (cond
; ( (null? lat) '() ) ; 1) Is the list empty/null?
; ( else (cond
; ( (eq? (car lat) a) (cdr lat) ) ; 2a) Is the current atom the same as the given atom?
; ; If so, then return (cdr lat)
; ( else (cons (car lat) (rember a (cdr lat))) )) )))) ; 2b) If not, then cons the current atom and recur on the remainder of the lat.
; ; ^^^^ constructor of lists
; ; ^^^^^^^^^ typical element - atom
; ; ^^^^^^^^^^^^^^^^^^^^ natural recursion of rember
;
; simplification:
(define rember
(lambda (a lat)
(cond
((null? lat) '())
((eq? (car lat) a) (cdr lat))
(else (cons (car lat) (rember a (cdr lat)))))))
(rember 'mint '(lamb chops and mint jelly)) ; (lamb chops and jelly)
(rember 'mint '(lamb chops and mint flavored mint jelly)) ; (lamb chops and flavored mint jelly)
(rember 'toast '(bacon lettuce and tomato)) ; (bacon lettuce and tomato)
(rember 'cup '(coffee cup tea cup and hick cup)) ; (coffee tea cup and hick cup)
(rember 'bacon '(bacon lettuce and tomato)) ; (lettuce and tomato)
; null? (bacon lettuce and tomato)
; eq? bacon bacon
; (lettuce and tomato)
(rember 'and '(bacon lettuce and tomato)) ; (bacon lettuce tomato)
; null? (bacon lettuce and tomato)
; eq? bacon and
; (cons bacon null? (lettuce and tomato))
; (cons bacon eq? lettuce and tomato)
; (cons bacon (cons lettuce null? (and tomato)))
; (cons bacon (cons lettuce eq? and and))
; (cons bacon (cons lettuce (tomato)))
; (cons bacon (lettuce tomato))
; (bacon lettuce tomato)
(rember 'sauce '(soy sauce and tomato sauce)) ; (soy and tomato sauce)
; FIRSTS
; composes a list containing the first S-expression of each member list in the given list
; inputs: list, either empty/null or a list which contains only non-empty lists
; output: list
(define firsts
(lambda (l)
(cond
( (null? l) '() ) ; 1) Is the list empty/null?
( else (cons (car (car l)) (firsts (cdr l))) )))) ; 2) Cons the first S-expression of the current member list and recur on the remainder of the given list.
; ^^^^ constructor of lists
; ^^^^^^^ a member list in the given list
; ^^^^^^^^^^^^^ typical element - the first S-expression of a member list
; ^^^^^^^^^^^^^^^^ natural recursion of firsts
(firsts '((apple peach pumpkin)
(plum pear cherry)
(grape raisin pea)
(bean carrot eggplant))) ; (apple plum grape bean)
(firsts '((a b) (c d) (e f))) ; (a c e)
; null? ((a b) (c d) (e f))
; (cons a null? ((c d) (e f)))
; (cons a (cons c null? ((e f))))
; (cons a (cons c (cons e null? ())))
; (cons a (cons c (cons e ())))
; (cons a (cons c (e)))
; (cons a (c e))
; (a c e)
(firsts '()) ; ()
(firsts '((five plums)
(four)
(eleven green oranges))) ; (five four eleven)
(firsts '(((five plums) four)
(eleven green oranges)
((no) more))) ; ((five plums) eleven (no))
; SECONDS
; composes a list containing the second S-expression of each member list in the given list
; inputs: list, either empty/null or a list which contains only non-empty lists
; output: list
;
; get the first S-expression of a list (car l)
; get the second S-expression of a list (car (cdr l))
; get the third S-expression of a list (car (cdr (cdr l)))
(define seconds
(lambda (l)
(cond
( (null? l) '() ) ; 1) Is the list empty/null?
( else (cons (car (cdr (car l))) (seconds (cdr l))) )))) ; 2) Cons the first S-expression of the current member list and recur on the remainder of the given list.
; ^^^^ constructor of lists
; ^^^^^^^ a member list in the given list
; ^^^^^^^^^^^^^^^^^^^ typical element - the second S-expression of a member list
; ^^^^^^^^^^^^^^^^^ natural recursion of firsts
; insertR
; inserts the new atom to the right of the first occurrence of the old atom in the lat
; inputs: new [atom], old [atom], lat [lat]
; output: lat
(define insertR
(lambda (new old lat)
(cond
( (null? lat) '() ) ; 1) Is the list empty/null?
( (eq? (car lat) old) (cons old (cons new (cdr lat))) ) ; 2a) Is the current atom the same as the given atom?
; If so, then return old + new + (cdr lat)
( else (cons (car lat) (insertR new old (cdr lat))) )))) ; 2b) If not, then cons the current atom and recur on the remainder of the lat.
; ^^^^ constructor of lists
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion of insertR
(insertR 'topping 'fudge '(ice cream with fudge for dessert)) ; (ice cream with fudge topping for dessert)
(insertR 'jalapeno 'and '(tacos tamales and salsa)) ; (tacos tamales and jalapeno salsa)
(insertR 'e 'd '(a b c d f g d h)) ; (a b c d e f g d h)
; insertL
; inserts the new atom to the left of the first occurrence of the old atom in the lat
; inputs: new [atom], old [atom], lat [lat]
; output: lat
(define insertL
(lambda (new old lat)
(cond
( (null? lat) '() ) ; 1) Is the list empty/null?
( (eq? (car lat) old) (cons new lat) ) ; 2a) Is the current atom the same as the given atom?
; If so, then return new + lat.
( else (cons (car lat) (insertL new old (cdr lat))) )))) ; 2b) If not, then cons the current atom and recur on the remainder of the lat.
; ^^^^ constructor of lists
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion of insertL
; subst
; replaces the first occurrence of the old atom with the new atom in the lat
; inputs: new [atom], old [atom], lat [lat]
; output: lat
;
; insertR (cons old (cons new (cdr lat)))
; insertL (cons new lat )
; subst (cons new (cdr lat))
(define subst
(lambda (new old lat)
(cond
( (null? lat) '() ) ; 1) Is the list empty/null?
( (eq? (car lat) old) (cons new (cdr lat)) ) ; 2a) Is the current atom the same as the given atom?
; If so, then return new + (cdr lat).
( else (cons (car lat) (subst new old (cdr lat))) )))) ; 2b) If not, then cons the current atom and recur on the remainder of the lat.
; ^^^^ constructor of lists
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion of subst
(subst 'topping 'fudge '(ice cream with fudge for dessert)) ; (ice cream with topping for dessert)
; subst2
; replaces the first occurrence of either o1 or o2 with the new atom in the lat
; inputs: new [atom], o1 [atom], o2 [atom], lat [lat]
; output: lat
;
; (define subst2
; (lambda (new o1 o2 lat)
; (cond
; ( (null? lat) '() )
; ( (eq? (car lat) o1) (cons new (cdr lat)) )
; ( (eq? (car lat) o2) (cons new (cdr lat)) )
; ( else (cons (car lat) (subst2 new o1 o2 (cdr lat))) ))))
;
(define subst2
(lambda (new o1 o2 lat)
(cond
( (null? lat) '() ) ; 1) Is the list empty/null?
( (or (eq? (car lat) o1)
(eq? (car lat) o2)) (cons new (cdr lat)) ) ; 2a) Is the current atom the same as the given atom?
; If so, then return new + (cdr lat).
( else (cons (car lat) (subst2 new o1 o2 (cdr lat))) )))) ; 2b) If not, then cons the current atom and recur on the remainder of the lat.
; ^^^^ constructor of lists
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion of subst2
; multirember
; removes all occurrences of an atom from a list of atoms
; inputs: a [atom], lat [lat]
; output: lat
(define multirember
(lambda (a lat)
(cond
( (null? lat) '() ) ; 1) Is the list empty/null?
( (eq? (car lat) a) (multirember a (cdr lat)) ) ; 2a) Is the current atom the same as the given atom?
; If so, then recur on the remainder of the lat.
( else (cons (car lat) (multirember a (cdr lat))) )))) ; 2b) If not, then cons the current atom and recur on the remainder of the lat.
; ^^^^ constructor of lists
; ^^^^^^^^^ typical element - atom
; ^^^^^^^^^^^^^^^^^^^^^^^^^ natural recursion of multirember
(multirember 'cup '(coffee cup tea cup and hick cup)) ; (coffee tea and hick)
; null? (coffee cup tea cup and hick cup)
; eq? coffee cup
; (cons coffee null? (cup tea cup and hick cup))
; (cons coffee eq? cup cup)
; (cons coffee null? (tea cup and hick cup))
; (cons coffee eq? tea cup)
; (cons coffee (cons tea null? (cup and hick cup)))
; (cons coffee (cons tea eq? cup cup))
; (cons coffee (cons tea null? (and hick cup)))
; (cons coffee (cons tea eq? and cup))
; (cons coffee (cons tea (cons and null? (hick cup))))
; (cons coffee (cons tea (cons and eq? hick cup)))
; (cons coffee (cons tea (cons and (cons hick null? (cup)))))
; (cons coffee (cons tea (cons and (cons hick eq? cup cup))))
; (cons coffee (cons tea (cons and (cons hick null? ()))))
; (cons coffee (cons tea (cons and (cons hick ()))))
; (cons coffee (cons tea (cons and (hick))))
; (cons coffee (cons tea (and hick)))
; (cons coffee (tea and hick))
; (coffee tea and hick)
; multiinsertR
; inserts an atom to the right of all occurrences of another atom in a list of atoms
; inputs: new [atom], old [atom], lat [lat]
; output: lat
(define multiinsertR
(lambda (new old lat)
(cond
( (null? lat) '() )
( (eq? (car lat) old) (cons old (cons new (multiinsertR new old (cdr lat)))) )
( else (cons (car lat) (multiinsertR new old (cdr lat))) ))))
(multiinsertR 'fried 'fish '(chips and fish or fish and fried)) ; (chips and fish fried or fish fried and fried)
; multiinsertL
; inserts an atom to the left of all occurrences of another atom in a list of atoms
; inputs: new [atom], old [atom], lat [lat]
; output: lat
(define multiinsertL
(lambda (new old lat)
(cond
( (null? lat) '() )
( (eq? (car lat) old) (cons new (cons old (multiinsertL new old (cdr lat)))) )
( else (cons (car lat) (multiinsertL new old (cdr lat))) ))))
(multiinsertL 'fried 'fish '(chips and fish or fish and fried)) ; (chips and fried fish or fried fish and fried)
; multisubst
; replaces all occurrences of one atom for another in a list of atoms
; inputs: new [atom], old [atom], lat [lat]
; output: lat
(define multisubst
(lambda (new old lat)
(cond
( (null? lat) '() )
( (eq? (car lat) old) (cons new (multisubst new old (cdr lat))) )
( else (cons (car lat) (multisubst new old (cdr lat))) ))))
(multisubst 'taco 'fish '(chips and fish or fish and fried)) ; (chips and taco or taco and fried)