code.org 11 KB
Prerequisites
(define atom?
(λ (x)
(and (not (pair? x))
(not (null? x)))))
#+end_src
In theory we could define other things as numbers, for example church numerals.
#+NAME: defonep
#+BEGIN_SRC scheme :noweb yes :results none :exports code :eval never-export
(define one?
(λ (x)
(= x 1)))
#+end_src
#+NAME: defpick
#+BEGIN_SRC scheme :noweb yes :results none :exports code :eval never-export
(define pick
(λ (n lat)
(cond
[(one? n) (car lat)]
[else
(pick (- n 1) (cdr lat))])))
#+end_src
** Y-combinator
In the first book the Y-combinator was derived. It is again:
#+NAME: y-combinator-def
#+begin_src scheme :noweb yes :results none :exports code :eval never-export :language guile
(define Y
(λ (proc)
((λ (f) (f f))
(λ (f)
(proc
(λ (x) ((f f) x)))))))
#+end_src
** All prerequisites :noexport:
#+NAME: prereq
#+BEGIN_SRC scheme :noweb yes :results none :exports none :eval never-export
<<defatom>>
<<defonep>>
<<defpick>>
<<y-combinator-def>>
Chapter 12
Recap of Y
Recursive length function using Y
<>
(define length (Y (λ (length) (λ (lst) (cond [(null? lst) 0] [else (+ (length (cdr lst)) 1)])))))
The length function is injected as an argument. Thus the expression is not referring to itself, but only ever to its argument.
The inner part looks just like the usual recursive length function. It is using an argument (length) as the thing it calls in the recursive case though.
<>
(simple-format #t "(length '(a b c d)) = ~a\n" (length '(a b c d)))
(length '(a b c d)) = 4
multirember (remove member multiple times) function using Y
The argument of Y is always a lambda expression, which takes as argument the function to be called in the recursive case. That function itself returns a function, which takes the actual input. In this example that is a list of atoms.
<>
(define multirember (λ (a lat) ((Y (λ (mr) (λ (lat) (cond [(null? lat) '()] [(eq? a (car lat)) (mr (cdr lat))] [else (cons (car lat) (mr (cdr lat)))])))) lat)))
Usage
(multirember 'a '(a b c a d))
Results
<>
(simple-format #t "~a\n" (multirember 'a '(a b c a d)))
(b c d)
Introduction of letrec
letrec offers a way to avoid using Y and possibly get a more easily understandable definition of recursive functions.
multirember (remove member multiple times) function using letrec
The following definition of multirember makes use of letrec instead of Y, because the definition of mr inside makes use of mr recursively itself. A normal let would not work here. The recursive mr is then returned and applied to lat, a list of atoms. This chapter introduces letrec.
(define multirember (λ (a lat) ((letrec ([mr (λ (lat) (cond [(null? lat) '()] [(eq? a (car lat)) (mr (cdr lat))] [else (cons (car lat) (mr (cdr lat)))]))]) mr) lat)))
Usage
(multirember 'a '(a b c a d))
Result
<>
(simple-format #t "~a\n" (multirember 'a '(a b c a d)))
(b c d)
A more readable version
Using the following definition, one can avoid 1 wrapping of parentheses of the letrec expression and move it into the value part of the letrec expression:
(define multirember (λ (a lat) (letrec ([mr (λ (lat) (cond [(null? lat) '()] [(eq? a (car lat)) (mr (cdr lat))] [else (cons (car lat) (mr (cdr lat)))]))]) (mr lat))))
This seems a bit more readable to me.
multirember with configurable test? predicate
We can use 1 layer of currying to make a "factory" of multirember functions, which know how to test for whether an element should be removed from a list.
(define make-multirember (λ (test?) (λ (a lat) (letrec ([mr (λ (lat) (cond [(null? lat) '()] [(test? a (car lat)) (mr (cdr lat))] [else (cons (car lat) (mr (cdr lat)))]))]) (mr lat)))))
(simple-format #t "~a\n" ((make-multirember =) 1 '(2 4 6 12 1 2)))
(2 4 6 12 2)
Set union implementation
First version
(define member? member)
(define union (λ (set1 set2) (cond [(null? set1) set2] [(member? (car set1) set2) (union (cdr set1) set2)] [else (cons (car set1) (union (cdr set1) set2))])))
(simple-format #t "~a\n" (union '(a b c d) '(s b a e)))
(c d s b a e)
Second version with captured set2
The text has objections about the fact, that union is always called with 2 arguments, the 2 sets to build the union of, although set2 never changes. It argues, that one can make the recursive calls simpler, by capturing set2 outside of the recursive part.
(define member? member)
(define union (λ (set1 set2) (letrec ([U (λ (set1°) (cond [(null? set1°) set2] [(member? (car set1°) set2) (U (cdr set1°))] [else (cons (car set1°) (U (cdr set1°)))]))]) (U set1))))
(simple-format #t "~a\n" (union '(a b c d) '(s b a e)))
(c d s b a e)
Third version with protected member?
The text also notes, that union relies on member?, which is implemented elsewhere. union serves as an example. member? or member is usually implemented in Scheme dialects, so it will not suddenly change. However, if it were a function, which were to change for example the order of its arguments, then we would have to adapt union and all other functions depending on member? as well. For this reason, the text argues for internalizing the definition of member? inside of union.
(define union (λ (set1 set2) (letrec ([U (λ (set1°) (cond [(null? set1°) set2] [(member? (car set1°) set2) (U (cdr set1°))] [else (cons (car set1°) (U (cdr set1°)))]))] [member? (λ (elem lst) (letrec ([M? (λ (lst°) (cond [(null? lst°) #f] [(eq? elem (car lst°)) #t] [else (M? (cdr lst°))]))]) (M? lst)))]) (U set1))))
(simple-format #t "~a\n" (union '(a b c d) '(s b a e)))
(c d s b a e)
Fourth version
Maybe instead of defining a whole member? inside letrec one could make a minimalistic wrapper for the member function already defined in Scheme. This way we would not reimplement things which are already in our language:
(define union (λ (set1 set2) (letrec ([U (λ (set1°) (cond [(null? set1°) set2] [(member? (car set1°) set2) (U (cdr set1°))] [else (cons (car set1°) (U (cdr set1°)))]))] [member? (λ (elem lst) (letrec ([M? (λ (lst°) (not (null? (member elem lst))))]) (M? lst)))]) (U set1))))
(simple-format #t "~a\n" (union '(a b c d) '(s b a e)))
The book has a bootstrapping approach, so it opts to implement member? inside union. A disadvantage of that is, that it cannot be separately unit-tested. Perhaps the philosophy there is, that encapsulation is more important than tests.