Re: functional programming is great, but why lists?

[Bill Richter <richter@math.northwestern.edu>]

   > My real question was why use such a rigid data structure as `cons',
   > rather than a more flexible vector type of data structure.
   
   Fair enough.  If I understand what you're saying, then my response is
   that we want both vectors and lists.  We don't want either one to take
   the place of the other.  

Shriram, again I mangled my point.  I don't mean the vectors that are
already in Scheme.  The Scheme vectors are hard to use in a functional
programming course because there's too much vector-set!, and not
enough ways to form new vectors, nothing like append or cons to make
larger vectors from smaller ones.

   The former is essentially a random-access collection of fixed size,
   while the latter is a sequential-access collection of arbitrary size.
   Those are two different things, and you (Bill) can probably give me
   some clever algebraic terminology that captures that difference.

Hmm, I was trying to make a joke at my own expense, that the `algebra'
of algebraic topology is mostly linear algebra.  The topology is
mostly just some strange constructions, like "smash product", which
curiously enough comes up in Matthias's Extensible DS paper (although
he uses the wrong symbol $\otimes$ instead of $\wedge$, and the
obvious topology you'd put on his smash product wouldn't be right, not
that he needs a topology).

Thanks for mentionin HTDP's "section entitled Generative Recursion,"
it looks pretty good.  Hey I'll finally understand sorting!


Let me just try one more time to explain.  I was often flummoxed by
exercises and solutions in TLS/TSS, but I think I came up with a
function (by using the TLS/TSS technique) that removes my confusion.

It's an extra vector-like functionality that I was always missing with
lists.  But we can add this functionality in with a simple function:

   (define (function-act-on-list f n list)
     ;; we're assuming a list of length m and a function 
     ;; f: {1,...,n} ---> {1,...,m}
     ;; and we return a new list which is the composition 
     ;; {1,...,n} -f--> {1,...,m} -list--> Values
     ;; i.e. the list whose i'th element is l_{(f i)}
     (if (= n 0)
	 '()
	 (cons (pick (f 1) list)
	       (function-act-on-list (lambda (i) (f (add1 i)))
				     (sub1 n) list))))

I'd even write this as f^* list, pull the list `list' back along the
function `f'.  This uses the TLS/TSS function `pick':

   (define (pick n lat)
     (if (= n 1)
	 (car lat)
	 (pick (- n 1) (cdr lat))))

And now I can easily solve a problem that I would not have known how
to do if presented in TSS: How can we cyclically permute a list?
That is, replace (l_1 l_2 ... l_n) with either 
(l_n l_1 ... l_{n-1}),     which is forwards to me
or
(l_2 ... l_n l_1),	   which is backwards to me.

The backwards one is tractable, because it's 

(append (cdr list) (car list))

and I can see how to write the solution out in TSS form:

   (define (cyclic lat)
     (if (null? lat)
	 '()
     (union (cdr lat) (cons (car lat) '()))))

   (define (union lat extra)
     (if (null? lat)
	 extra
	 (cons (car lat) (union (cdr lat) extra))))

But the forward cyclic permutation flummoxes me.  Maybe I'd come up
with a slick solution if I thought about it for a long time, but it's
trivial with my 5-line function above `function-act-on-list':


   (define (cyclic-permute-backward n)
     (lambda (i) 
       (if (= i 1)
	   n
	   (sub1 i))))

   (define (cyclic-permute-forward n)
     (lambda (i) 
       (if (< i n)
	   (add1 i)
	   1)))


   (function-act-on-list (cyclic-permute-backward 6) 6
			 '(a b c d e f))

   (function-act-on-list (cyclic-permute-forward 6) 6
			 '(a b c d e f))

and they work:

(f a b c d e)
(b c d e f a)

And I'll just beat the point into the ground by re-doing `scramble':

   (define (scramble-br lat rev-pre)
     (cons (pick (car lat) rev-pre)
	   (if (null? (cdr lat))
	       '()
	       (scramble-br (cdr lat)
			    (cons (cadr lat) rev-pre)))))

   (define (scrambler lat)
     (if (null? lat)
	 '()
	 (scramble-br lat (cons (car lat) '()))))

That's pretty much the TSS solution.  I still say it's very nice!
Here's my trivial solution:

   (define (scramble-barbaz lat)
     (let ((g (lambda (n)
		 (add1 (- n (pick n lat))))))
       (function-act-on-list g (length lat) lat)))


   (scrambler       '(1 2 3 4 5 6 7 8 9))
   (scramble-barbaz '(1 2 3 4 5 6 7 8 9))

   (scrambler       '(1 2 3 1 2 3 4 1 8 2 10))
   (scramble-barbaz '(1 2 3 1 2 3 4 1 8 2 10))

   (scrambler       '(1 1 1 3 4 2 1 1 9 2))
   (scramble-barbaz '(1 1 1 3 4 2 1 1 9 2))


And we can see actually works:

(1 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 2 8 2)
(1 1 1 1 1 1 1 1 2 8 2)
(1 1 1 1 1 4 1 1 1 9)
(1 1 1 1 1 4 1 1 1 9)

I really like the permutation capability:

   (define (sigma123 n)
     (cond ((= n 1) 2)
	   ((= n 2) 3)
	   ((= n 3) 1)))

   (define (sigma231 n)
     (cond ((= n 1) 3)
	   ((= n 2) 1)
	   ((= n 3) 2)))


   (function-act-on-list sigma123 3 '(a b c))
   (function-act-on-list sigma231 3 '(a b c))

   (define (2switch n)
     (cond ((= n 1) 2)
	   ((= n 2) 1)
	   ((= n 3) 4)
	   ((= n 4) 5)
	   ((= n 5) 3)))

   (function-act-on-list 2switch 5
			 '(a b c d e))

(b c a)
(c a b)
(b a d e c)


So what's the moral?  The TSS technique for writing recursive
functional programs (the various commandments, like `Cons onto the
natural recursion', which I used) is quite nice, and I'm glad I
learned it, but somehow I knew too much Linear Alg to be able to use
it on the problems presented.  

Oh, and one more "functoriality" demanded by Linear Algebraists is the
union procedure of TLS, another TLS exam I flunked, but is trivial in
this function framework:

   (define (make-function-into-lat f n)
     (if (= n 0)
	 '()
	 (cons (f 1) 
	       (make-function-into-lat 
		(lambda (n) (f (add1 n))) (sub1 n)))))

   (define (union L M)
     (make-function-into-lat
      (lambda (n)
	(if (<= n (length L))
	    (pick n L)
	    (pick (- n (length L)) M)))
      (+ (length L) (length M))))

   (union '(a b c) '(1 2 3))

   => (a b c 1 2 3)

So maybe the real moral is that if you have extra-mathematical
hangups, you have to program them in, just like anything else!