On 28/02/06, Johannes Waldmann
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