Re: functional programming is great, but why lists?

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

   I'm not sure what is "strange" about cons as a data structure. 

   (reverse (a (b (c (d)))))      => ((b (c (d))) a) 

Oops!  Thanks to everyone who wrote today.  This probably isn't worth
a long thread, but I'd like to clarify, since I really garbled my
original message, many apologies.

I'm glad to know why `cons' should be a separate data type, for
`cons?' reasons (I liked MF's Expressive Power paper), but my real
question wasn't why we use `cons' instead of stripped down LC_v where
you'd have to use a procedure def of `cons'.

My real question was why use such a rigid data structure as `cons',
rather than a more flexible vector type of data structure.  To an
algebraic (i.e. linear algebra) topologist like me, it's really hard
to junk vectors and just use lists.  In particular, we're always
letting permutations (bijections of {1,...,n}) act on R^n.  That's the
sort of thing that's trivial to do with vectors, but with lists, you
have to write recursive functions to do it.

I suppose one answer is it would be harder to teach high school
students linear algebra and permutation groups than lists + recursion.
Perhaps there are other answers.  But let me explain anyway...

I wrote a trivial 1-line nonrecursive function

(define (scramble-fun lat-fun)
  (lambda (n)
    (lat-fun (add1 (- n (lat-fun n))))))

that's essentially does the same thing as what still seems like a gem
to me, on p 15 of TSS:

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

   (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) '()))))

When I say gem, I mean something I would not have figured out, because
I already know the trivial solution.   And I'm perfectly capable
(after reading this much of TSS & TLS) to translate my trivial
function solution into a trivial list solution:

   (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 (make-lat-into-function lat)
     (lambda (n) (pick n lat)))

Those 2 functions wrote themselves, it was boring as Shriram said, and
that's good, and now I can rewrite my original trivial 1-line
nonrecursive function. It's now 3 lines, but 2 of the lines are duds:

   (define (scramble-foobar lat)
     (let* ((f (make-lat-into-function lat))
	    (g (lambda (n)
		 (f (add1 (- n (f n)))))))
       (make-function-into-lat g (length lat))))


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

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

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

and it seems to be the same:

   Welcome to DrScheme, version 103p1.
   Language: Graphical Full Scheme (MrEd).
   (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)
   > 

So here's the pedagogical problem.  If I were to teach a TLS or HTDP
course, or coach nephews & nieces on it, it seems like I've got to be
able to forget a lot of permutation + vector techniques that I use all
the time.  I'm sure there are folks here who are pretty good at
permutation + vector techniques themselves, there must be a way.