Re: functional programming is great, but why lists?

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

   There's a good reason why lists don't naturally come with indices
   the way vectors do: they're not intended to be accessed at random.
   They really are intended to be accessed sequentially.

Thanks, Shriram.  I think I finally understand (after your generative
Recursion remark) that my vector stuff has been nonsense:

Lists are great for the purpose of teaching a simple kind of
recursion, what HTDP calls structural recursion.  I'd be happy to
teach a course on structural recursion, without bringing in vectors.

Here's what I understand now, I don't have it all figured out:

Let's try to write a recursive functional procedure to implement a
function F defined on Lists.

As HTDP says in `Structural versus Generative Recursion', this often
"requires a deep, often mathematical, insight into the problem-solving
process itself".  So it's great to start students off in the simpler
world of structural recursion, which includes functions F satisfying
recursion rules like either:

( F L ) = (G (F (cdr L)))	       for L nonempty

or

( F L ) = (G (car L) (F (cdr L)))	for L nonempty

for some function G we have to solve for.

The first type of function is pretty simple, like length:

(define (length L)
  (if (null? L)
      0
      (add1 (length (cdr L)))))

All the recursive TSS type procedures I understand fit the 2nd form.
No doubt more complicated recursion rules would still be called
structural recursion, and I need to learn about that.  Here's 2
examples:

Let's do forward cyclic permutations, which I falsely posted was such
a challenge yesterday.  It's easy this structural recursion way:

So my function F cycles a list forward, like this:

(F (x_1 ... x_n)) =  (x_n x_1 ... x_{n-1})

Let's look for a rule like:

( F L ) = (G (car L) (F (cdr L)))	for L nonempty

which amounts to solving for G in the equation

(x_n x_1 ... x_{n-1}) = (G x_1 (x_n x_2 ... x_{n-1}))

But that's obvious!  G basically transposes the 1st 2 elements, and
it's easier to describe in Scheme:

(define (forward-cyclic-permutation L)
  (letrec ((G (lambda (x M)
                (if (null? M)
                    (cons x '())
                    (cons (car M) (cons x (cdr M)))))))
    (if (null? L)
        '()
        (G (car L) (forward-cyclic-permutation (cdr L))))))

(forward-cyclic-permutation '(a b c d e f))
(forward-cyclic-permutation '(1 2 3 4 5 6 7 8 9 10))

and we see it works:

(f a b c d e)
(10 1 2 3 4 5 6 7 8 9)

The moral of this isn't that I know everything about structural
recursion.  The moral is that by drastically restricting the kinds of
solutions we're looking for, we might improve our chances, and it's a
good place to start!  That's a powerful pedagogical principle, used
all the time in math classes.

Here's an example of how I've got more to learn.   You wrote:

     If you use the design recipes in How to Design Programs, there's
     nothing gem-like about writing REVERSE -- it's easy, simple and
     boring, just as it should be.

Here's what's boring to me, i.e. I understand it.   Let's call R the
reverse function, which does

(R (x_1 x_2 ... x_n)) =  (x_n ... x_2 x_1)

I want a recursion rule 

( R L ) = (G (car L) (R (cdr L)))	for L nonempty, meaning 

(x_n ... x_2 x_1) = (G x_1 (x_n ... x_3 x_2))

The solution stares at us!  Even I can see that (G x M) appends x onto
the end of a list M.  OK, so we've passed our test, but now we want a
recursive procedure for G.   Let's fiddle with the car & cdr of M:

(G x (m_1 ... m_n)) = (m_1 ... m_n x) = (cons m_1 (m_2 ... m_n x))

and that clearly satisfies the equation

(G x M)  = (cons (car M) (G x (cdr M)))

and I've got a klunky reverse:

(define (reverse L)
  (letrec ((append->end-of-list
            (lambda (x M) 
              (if (null? M)
                  (cons x '())
                  (cons (car M) 
                        (append->end-of-list x (cdr M)))))))
    (if (null? L)
        '()
        (append->end-of-list (car L) 
                             (reverse (cdr L))))))

(reverse '(a b c d e f))
(reverse '(1 2 3 4 5 6 7 8 9 10))

=> 
(f e d c b a)
(10 9 8 7 6 5 4 3 2 1)

My function wrote itself, but it's a kludge compared to the more
elegant TLS reverse:

(define (reverse L)
  (letrec ((reverse-help
            (lambda (L M) 
              (if (null? L)
                  M
                  (reverse-help (cdr L)
                                (cons (car L) M))))))
    (if (null? L)
        '()
        (reverse-help L '()))))

That doesn't bore me yet, so I need to book up on "the design recipes
in How to Design Programs".   Actually, this reverse bores me in one
respect, it looks kinda like an iteration

M = '();
i = n;
while (i > 0) {
  M = (cons x_i M);
  i--;
}

you see I've got more to learn.  Sorry for posting so often, but I
feel like I really learned an important pedagogical point, the value
of using inflexible lists as a way to present structural recursion.  

A final point: I'll never believe HTDP really has "design recipes"
until I see the equations, recursion rules like
( F L ) = (G (car L) (F (cdr L)))
You guys have too much programming/mathematical ability for me to
really believe you when you say things are boring or cookbook recipes.