Export lists in modules

[Cale Gibbard]

On 28/02/06, Johannes Waldmann <waldmann at imn.htwk-leipzig.de> wrote:
> Cale Gibbard wrote:
>
> > This is exactly why lists are so common. If people ask why lists are
> > so common in lazy functional languages, they ought also to ask why
> > loops are so common in imperative languages.
>
> A loop is a sequence of actions. In FP, I don't typically have actions,
> rather I collect values, so I'd need several collections types,
> among them: sequences, and among them: classical left-biased lists.

Sure you do, you have pure functions, there are lots of those.
Further, you have things like sequence, which turns a list of monadic
actions into a monadic action returning a list of results, and mapM,
which is just mapping a function to construct those actions over a
list before sequencing them.

Numerical algorithms involving iteration can get quite a lot of
flexibility out of lists, using them to represent the output and
intermediate values of the algorithm at each iteration. These lists
are lazy of course, so that you can just take as many iterations off
as you need, and since it's so nicely explicit, it's comparatively
easy to determine where you'd like to chop, and to apply higher-order
methods of reducing error.

See "Why Functional Programming Matters" for some brilliant examples.
http://www.math.chalmers.se/~rjmh/Papers/whyfp.html

>
> I admit that my typical Haskell program does use such lists
> all over the place, but mostly in monad comprehensions:
> do x <- ... ; guard ; let ... ; return ...
> and often it's a list only because there is no such syntactical
> convenience for, e. g. Sets.
> (I have to write lots of setToList/mkSet, which look plain ugly.)
>
> Even if I really want sequences, I rarely rely on the
> left-biased representation. (E. g. in the above example,
> there's no visible pattern matching on the 'cons'.)

Then perhaps you're missing out :) It sounds like you might be using
lists like a strict functional programmer would, but not really
relying on the laziness aspect. When you start doing so, it becomes
much more apparent why lists are so special, and, for the many of the
places where they work, AVL trees, for example, just wouldn't do. (Not
that there's anything against AVL trees, it's just that they're not
any kind of a substitute for lists in these common lazy functional
programming cases.)

>
> For reference, in Java, List<> is an interface, not a type
> (it has instances like LinkedList<> and ArrayList<>).
>
> And, there's nice syntactic sugar for looping
> over collections:  Collection<E> c; for (E item : c) { ... }
> (it hides the pre-1.5 Iterator.hasNext/next stuff.
> I'd say this is an example of moving away from a left-biased
> representation, or at least freeing the programmer from having
> to think about it).

None of that is lazy, so it just isn't the same thing at all. The
important point is that the elements and structure of the collection
are being constructed one at a time as you iterate over it, and they
are easily garbage collected as soon as you're done with them. That's
what allows you to say "hey, these are actually loops which just
haven't happened yet". Only a list can really easily provide that for
linear iteration through a collection of values. Certain trees can
come close, (with a logarithmic additional space hit) and trees are
quite useful for directed searching, but they don't replace the high
position that lists have, just as non-linear forms of recursion don't
quite replace common linear recursion. (Look at some imperative
programs and count the loops and linear recursions compared with the
number of general recursive functions which are not linear recursive.)

Lists in the list-monad/list-comprehension usage are nearly trees
anyway, due to the means by which they are computed, but you can
always think of them as simple lists, or even as single
nondeterministic values (due to the monadic structure), which is
pretty neat. You can prune the tree by guards or the empty list, and
branch by using bind. In some sense, you're defining a long reified
loop which is strung along the leaves of a nonlinear recursive call
tree. You're not forced to look at it that way, though, which makes
things easy to think about when you're actually programming. It's also
what makes the list monad (and isomorphic nondeterminism monads)
really powerful.

 - Cale