code.org 10 KB
Prerequisites
(define atom?
(λ (x)
(and (not (pair? x))
(not (null? x)))))
#+end_src
#+NAME: defonep
#+BEGIN_SRC scheme :noweb yes :results none :exports none :eval never-export
(define one?
(λ (x)
;; In theory we could define other things as numbers, for example church
;; numerals.
(= x 1)))
#+end_src
#+NAME: defpick
#+BEGIN_SRC scheme :noweb yes :results none :exports none :eval never-export
(define pick
(λ (n lat)
(cond
[(one? n) (car lat)]
[else
(pick (- n 1) (cdr lat))])))
#+end_src
#+NAME: prereq
#+BEGIN_SRC scheme :noweb yes :results none :exports code :eval never-export
<<defatom>>
<<defonep>>
<<defpick>>
Chapter 11
member?
(define member? (λ (a lat) (cond [(null? lat) #f] [else (or (eq? a (car lat)) (member? a (cdr lat)))])))
Lets test it:
<>
(display (simple-format #f "(member? 1 '(3 2 1)) -> ~a\n" (member? 1 '(3 2 1))))
(display (simple-format #f "(member? 1 '(3 2 4)) -> ~a\n" (member? 1 '(3 2 4))))
(member? 1 '(3 2 1)) -> #t (member? 1 '(3 2 4)) -> #f
two-in-a-row?
A function shall be defined, which determines, whether there are 2 subsequent elements inside a given list, for which eq? is #t.
(define is-first? (λ (a lat) (cond [(null? lat) #f] [else (eq? a (car lat))])))
<>
(define two-in-a-row? (λ (lat) (cond [(null? lat) #f] [else (or (is-first? (car lat) (cdr lat)) (two-in-a-row? (cdr lat)))])))
However, this version obscures, that in one case it performs a check twice. When it checks, whether the list is null? in is-first? and returns #f, two-in-a-row? will recur and call itself. Then it will check for a second time, whether the list it receives is null?. To avoid this duplicate check, the book suggests to leave the decision of whether to recur or not to the function, which checks for en empty list first. That is is-first?.
Let us try to leave that responsibility to ~is-first?~:
(define is-first-b?
(λ (a lat)
(cond
[(null? lat) #f]
[else
(or (eq? a (car lat))
;; Not (cdr lat) here! is-first-b? is already given the cdr of the
;; list and the argument a is the actual car of the list!
(two-in-a-row? lat))])))
<>
(define two-in-a-row? (λ (lat) (cond [(null? lat) #f] [else (is-first? (car lat) (cdr lat))])))
Now we have two functions which are mutually recursive.
(Note: There is also a problem of src_scheme[:exports code]{(two-in-a-row? lat)} in is-first-b? not being in the tail position and thus growing the stack each call.)
There is still a duplicate check of src_scheme[:exports code]{(null? lat)}, because when two-in-a-row? is called from is-first-b?, it checks again, whether the list is empty.
When we look at what two-in-a-row? actually does, when called from is-first-b?, we can see, that it does not actually do much. The null? check for the empty list will always be #f, because the same thing was already checked in is-first-b? about lat and lat is given to two-in-a-row?. So two-in-a-row? will always enter the else branch, when called from is-first-b? and the null? check is only useful, when two-in-a-row? is initially called from outside of is-first-b?. This observation leads to the conclusion, that one could write a single function, by modifying is-first-b? a little more, so that the call to two-in-a-row? is no longer needed.
The modified version of is-first-b? will be renamed to two-in-a-row-b? to express what it does.
(define two-in-a-row-b? (λ (preceding lat) (cond [(null? lat) #f] [else (or (eq? preceding (car lat)) (two-in-a-row-b? (car lat) (cdr lat)))])))
There is still a problem here: two-in-a-row-b? receives always 2 arguments. This is inconvenient and unexpected to work with. One could use two-in-a-row? to avoid this:
(Note: The problem of non-tail position of the call to (two-in-a-row-b? (car lat) (cdr lat)) still persists.)
<>
(define two-in-a-row? (λ (lat) (cond [(null? lat) #f] [else (two-in-a-row-b? (car lat) (cdr lat))])))
This clears up the interface for the user.
A tail call optimized version, getting rid of the non-tail position of the recursive call, could be written as follows:
(define two-in-a-row? (λ (preceding lat) (cond [(null? lat) #f] ;; It is a bit meh, that we cannot simply return the result of the ;; expression here and need to write #t instead. Perhaps there is a better ;; way? [(eq? preceding (car lat)) #t] [else ;; Tail-recursive. (two-in-a-row-b? (car lat) (cdr lat))])))
sum-of-prefixes
This part introduces a function, which calculates the sum of the prefix for each element in the given list.
My first attempt:
(define sum-of-prefixes (λ (tup)
(define iter (λ (tup prefix-sum) (cond [(null? tup) (cons prefix-sum '())] [else (cons prefix-sum (iter (cdr tup) (+ prefix-sum (car tup))))])))
(cond [(null? tup) '()] [else (iter (cdr tup) (car tup))])))
Let us try it:
<>
(display (simple-format #f "(sum-of-prefixes '(1 1 1 1 1)) -> ~a\n" (sum-of-prefixes '(1 1 1 1 1))))
(sum-of-prefixes '(1 1 1 1 1)) -> (1 2 3 4 5)
The book does not make use of inner definitions using define. Instead it uses additional functions defined separately:
(define sum-of-prefixes (λ (tup) ;; Start with a sum of 0, the neutral element of addition. (sum-of-prefixes-b 0 tup)))
(define sum-of-prefixes-b (λ (sonssf tup) (cond [(null? tup) '()] [else (cons (+ sonssf (car tup)) (sum-of-prefixes-b (+ sonssf (car tup)) (cdr tup)))])))
Let us try it:
<>
(display (simple-format #f "(sum-of-prefixes '(1 1 1 1 1)) -> ~a\n" (sum-of-prefixes '(1 1 1 1 1))))
(sum-of-prefixes '(1 1 1 1 1)) -> (1 2 3 4 5)
sum-of-prefixes just like in my own solution takes only one argument, so that the caller does not need to think about the implementation detail. The interface is simple. The definition in the book has advantages and disadvantages. An advantage is, that the code is less nested. A disadvantage is, that sum-of-prefixes-b pollutes the namespace of the module, in which it is defined and serves no other purpose than being called by sum-of-prefixes.
The point the book makes is, that for recursive functions, which need to know about previous arguments to the function, one can define a helper function, which takes additional arguments. This is stated in the Eleventh Commandment:
Use additional arguments when a function needs to know what other arguments to the function have been like so far.
scramble
Next the book goes on to show a weird but in principle similar example scramble, which takes a tuple and calculates another tuple from it:
<>
<>
(define scramble (λ (tup) (scramble-b tup '())))
(define scramble-b (λ (tup rev-pre) (cond [(null? tup) '()] [else (cons (pick (car tup) ;; Here we artificially make the reversed prefix longer by the ;; current element, so that pick will pick the correct element. (cons (car tup) rev-pre)) (scramble-b (cdr tup) ;; We add the current element to the reversed prefix of the ;; next iteration. (cons (car tup) rev-pre)))])))
The scramble function looks at each number in the tuple. The number at each position (position = index + 1, or "distance from the start of the list") is substracted from its position and the resulting value is the index of the value, which shall be the final result for the number in the resulting tuple.
Let us try it:
<>
(display (simple-format #f "(scramble '(1 2 3 1 2 3 4 1 8 2 10)) -> ~a\n" (scramble '(1 2 3 1 2 3 4 1 8 2 10))))
(scramble '(1 2 3 1 2 3 4 1 8 2 10)) -> (1 1 1 1 1 1 1 1 2 8 2)