Recursive append
The recursive definition of append follows:
It is equivalent to the Lisp
(defun recAppend (x y)
(if (null x)
y
(cons (car x) (recAppend (cdr x) y))))
If the first argument is NIL ,
recAppend returns the second argument. Otherwise it joins
the two lists together.
decons is short for deconstruct and takes
a List and returns two values: its first element and the rest
of the list. This does the work of the (car x) and
(cdr x) calls in the recAppend Lisp function.
If the inputs to recAppend are (a b c) and
(d e) , the values produced at each stage are
Inputs  Vertex  Outputs 
NIL (a b c) 
unless+ 
(a b c) 
(a b c) 
decons 
a (b c) 
(b c) (d e) 
recAppend 
(b c d e) 
a (b c d e) 
cons 
(a b c d e) 
Tailrecursive reverse
recAppend is not the best implementation of
append , as the repeated recursive calls require a lot of stack
space. For very long lists this would result in stack overflow. It would
be better to reverse the first argument, and then reverse it onto the second. This gives us the same answer, but in addition, gives us a reverse function.
It would be best to implement reverse iteratively, which will be done in a
later tutorial, but first we give a tailrecursive implementation.
It is equivalent to the Lisp
(defun tailRecReverse (x y)
(if (null x)
y
(tailRecReverse (cdr x) (cons (car x) y))))
If the first argument is NIL, tailRecReverse returns the second
argument. Otherwise, it reverses the first argument onto the second,
e.g.
(tailRecReverse '(c b a) '(d e)) returns
(a b c d e) .
Inputs  Vertex  Outputs 
NIL (a b c) 
unless+ 
(a b c) 
(a b c) 
decons 
a (b c) 
a NIL 
cons 
(a) 
(b c) (a) 
tailRecReverse 
(c b a) 
In the sandbox, first tailRecReverse is called
to reverse a list. Then, tailRecReverse is called twice, giving
the same result we would get were recAppend called
instead:
We can wrap the two calls into a new append function, and then call
that:
The results of making the three calls are:
Pascal's triangle
Now, let's look at a more complex function, to compute Pascal's
triangle.
This builds up a list of lists of integers in reverse order. The
first two branches which output NIL when the input is
0 , and ((1)) when the input is 1, are the
base cases. The other branch will be easier to understand by
going through the values produced at each stage:
Inputs  Vertex  Outputs 
1 6 
= 
NIL 
NIL 6 
unless+ 
6 
6 
sub1 
5 
5 
pascal 
((1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1)) 
((1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1)) 
car 
(1 4 6 4 1) 
0 (1 4 6 4 1) 
cons 
(0 1 4 6 4 1) 
(0 1 4 6 4 1) 
reverse 
(1 4 6 4 1 0) 
iAdd (0 1 4 6 4 1) (1 4 6 4 1 0) 
mapcar 
(1 5 10 10 5 1) 
(1 5 10 10 5 1) ((1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1)) 
cons 
((1 5 10 10 5 1) (1 4 6 4 1) (1 3 3 1) (1 2 1) (1 1) (1)) 
The first attempt at output wasn't particularly readable,
so we reversed the output of pascal to get it in the usual order,
and then transcribed each list separately. This was done by mapping
transcribe1 (which transcribes a single value) over each list
comprising pascal 's output.
Previous
Up
Next
© Copyright Donald Fisk 2015, 2016
