Re: functional programming is great, but why lists?

[Shriram Krishnamurthi <sk@cs.brown.edu>]

Bill Richter wrote:

> 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.  A vector has type

  vector = TST^n

where TST = The Scheme Type (aka, any Scheme value).  Since this is
virtually impossible to program in a principled fashion (a la HtDP),
in practice we want

  vector[T] = T^n

In contrast,

  list[T] = empty
          | (cons T list[T])

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.

It's possible to deal with vector-like structures.  Unfortunately, the 
structure of the datum doesn't lend itself to a clear decomposition
pattern.  As a result, simple algorithms use the decomposition of the
*index* instead:

  nat = zero
      | (add1 nat)

More sophisticated algorithms (eg, quicksort) use much cleverer
decompositions that require ingenuity rather than following (purely)
from the structure of the data.  We discuss this point in quite some
detail in the book's section entitled Generative Recursion.  (I
personally think it's one of HtDP's highlights.)

Shriram