Re:When You Should Use Lists in Haskell (Mostly Not)
by theoh on Thursday March 16, 2017 @09:20PM
(#13890590)
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?
[ Parent
| on HN ]
Re:When You Should Use Lists in Haskell (Mostly Not)
by chongli on Thursday March 16, 2017 @09:36PM
(#13890656)
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.
Re:When You Should Use Lists in Haskell (Mostly Not)
by theoh on Thursday March 16, 2017 @11:23PM
(#13891167)
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...