[wrs]

His point is Foldable is the universal thing -- applying an inductive operation. List, on the other hand, is a particular choice of Foldable data structure which is seldom the appropriate choice. The language has now separated those two concepts, but the examples and tutorials still present them as tied together.

[theoh]

Essentially, the desirable and real elegance of recursion is the thing that got fused with the slightly simplistic notion of a linked list in the minds of the language designers, then?

[chongli]

Haskell lists are not linked lists though, they're streams. In a typical strict language any list you create goes straight on the heap. Haskell, being a lazy language, is only going to evaluate what actually needs to be evaluated. If you compose a whole bunch of functions on lists Haskell will fuse them, avoiding the allocation of all those intermediate lists.

Haskell does also have a Stream data type which is similar but features a different set of tradeoffs.

[theoh]

They have a nested structure, is all I meant by "linked list". I know Haskell can deal with infinite streams (e.g. by generating the values with corecursion) but the basic "singly-linked" character remains. They aren't doubly-linked, easy to traverse in both directions: they are recursion-centric, as the article stated.

The notorious/ingenious idea of zippers exists to facilitate sane navigation and (effectively) mutation of data structures. It deals with precisely the issue of the pointers in a functional data structure pointing in inconvenient directions...