[kevinclancy]

I think the author has made a false assumption about how lists are typically used in Haskell. Being algebraic datatypes, lists in Haskell are built on a foundation of universal algebra. The operations that you perform on them are inherently inductive: process the head and recurse on the tail. The most common tasks in functional programming, such as program analysis, fit into this paradigm nicely. So including "(Mostly Not)" in the title is misguided; the designers of Haskell and other functional languages knew what they were doing when they decided to make lists prominent in accessible in their languages.

[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...