The first-class status of linked lists in Haskell really bothers me. In Idris there's no special syntax for lists; lists of `a` are denoted `List a` and `[]` is simply syntactic sugar for the `null` function of that module. This means `List` and other structures like vectors are on the same level.
It made sense to me to think of a lazy list as a cute way to write an eager generator method, but the implication you should ever use a linked list for anything is unfortunate.
GHC has the `IsList` type class which basically allows overloading the list syntax to create any other sequential container.
It still uses linked lists as an intermediate representation (the type class consists of a function `fromList :: [a] -> t a`) but since lazy lists are generators this is quite sensible.
I do agree but I also remeber that Haskell is 27 years old. Newer Haskell-inspired languages like PureScript don't have a built-in list any more.
There's a lot of old stuff in Haskell, e.g. String which is a list of char. We have a number of new preludes (base, foundation, protolude, ..) that improve the situation a lot, so I'm not sure we really need a "python 3" moment.
We could definitely be more aggressive in pointing out that you need to use a new prelude though.
Any recommendations on which new prelude to use? I'm fairly competent with Haskell but have never looked into these and am feeling decision paralysis -- too many choices.
I've tried a bunch of alternative prelude and my experience is that it makes it very hard to integrate with code that uses the standard prelude. Foundation seems to have the highest chances of success right now, ClassyPrelude seems to be the most well-used, and Protolude seems to be more like a framework to build your own prelude.
If you're competent with Haskell, don't bother. A new Prelude will save you a bunch of imports; that's it. If you're fretting over which one to use, you've already spent too much time making this decision; just stick with the regular Prelude and use your imports.
The worst thing about the default Prelude is that it encourages bad behavior among new users--for instance, with partial functions like `head`. Experienced people know what to avoid and what to work around. So if picking an alternative Prelude seems like too much work, it is.
I have a project where I have mostly dumped the Prelude. All it is doing is saving me a bunch of imports. That's nice but not earth-shaking.
We're mostly using Protolude at the moment. It has some nice properties, e.g.
* "id" renamed to "identity" so you can use id in your own code
* panic functions like "notImplemented"
* a generic string converter "toS"
* lots more
But to be fair most modern preludes work OK.
Foundation is a bit different in that it doesn't ship a huge amount yet but has the potential to eventually replace the core prelude with saner default types like utf8-encoded strings. If you need to ship to production yesterday I would not use Foundation just yet.
Everything that's wrong with [] is wrong with [Char] and more so. In a Unicode world, it rarely makes sense to iterate over codepoints in a string, and it's rarely useful to prepend codepoints or drop codepoints at the beginning of a string. Usually an array-like string (e.g. Text) is better; occasionally something like Seq Char might be useful.
>In a Unicode world, it rarely makes sense to iterate over codepoints in a string
I love that people think that being Unicode somehow makes strings into opaque objects that you can never inspect or manipulate. Do you think that strings magically pop into existence fully formed and then magically disappear into a magic box and come out as rendered glyphs on a screen?
I don't disagree that [Char] is a stupid way to represent strings. Strings should very obviously just be byte arrays. Go does it right, it's one of the few things it does right. It turns out the creators of UTF-8 know how to deal with Unicode properly. Who would have thought?
I just mean that inspecting and manipulating strings is sufficiently complex that most of the time you use something like libicu to do it, so the apparent convenience of [] is not useful to the average programmer.
I have no problem with an opaque string type that supports being serialised into bytes. I also have no problem with a string type that exposes the reality that it's internally represented as UTF-8. But I can understand that maybe that's a little imperfect, because you might not want to maintain a perfect normalised correct UTF-8 encoding all the time. e.g. if you concatenate "blahblahlblaha" and the combining acute symbol followed by "blahlbahlblah", you might want to just store them together and normalise them later or something? I don't know.
The special syntax is really just a convenience. If you want to build `Seq` everywhere, you can always do `3 <| 2 <| 1 <| Seq.empty`. Or you can use `{-# LANGUAGE OverloadedLists #-}`, though this will use lists as an intermediate type.
However these problems only exist for literals, and typically literals in source code are not going to be so huge for lists to be a problem anyway.
A list literal is like a string literal: convenient. Getting rid of the special syntax wouldn't accomplish anything.
Something the article does not touch on is the huge cache performance penalty you pay with linked lists. With a linked list, all of the nodes are scattered around your heap. So whenever you iterate a linked list, you are accessing random memory locations. Random access is not really cacheable.
Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower.
This is because the CPU will load contiguous chunks of memory into cache. On x86, the cache block size is 64 bytes. So for an array of 4 byte ints, you are loading 16 ints into cache at a time. With a linked list, you will likely get a cache miss on most nodes and have to access RAM. Access time for L1 cache is 0.5 nanoseconds, access time for RAM is ~100 nanoseconds.
For what it's worth, I did the following benchmarks in Java 8:
Make two List<Object>s. One is LinkedList one is ArrayList.
Then timed how long it took to empty the list by deleting random indexes.
For LinkedList this is O(n) to iterate up to the element and O(1) to remove it.
For ArrayList isn't O(n) to shift all of the following elements down by 1 index.
As the list size approaches infinity, the benchmark shows that the ArrayList is 10x faster. That's because even though you are copying a ton of memory, it's all contiguous in memory and highly cacheable. In the LinkedList you are just chasing pointers to iterate the array, but they are not cacheable.
A more common example is the case of queues. I made two Queue<Object>s, one was LinkedList and another ArrayDeque. Then I polled the head of the queue until empty. As N gets larger, the ArrayDeque is 3x faster.
List nodes being scattered depends on the memory management. When you start out with a blank heap, if you grab successive cons cells, they can be adjacent (in the same cache line). Also, when a garbage collection pass reclaims unreachable conses and puts them into a free list, it can sweep them in heap order, so physically neighboring free cells end up together in the free list.
That's true. You still have the heap overhead, though. If the heap allocates an int (for the block size) just before the block it returns, then if your linked list contains ints, the heap memory overhead is 50%. This means you get half as many entries in a cache line, even if they were allocated in order.
Haskell's garbage collector is compacting (see below). When the GC compacts, it is very easy to put linked list entries together for more efficient access.
[citation needed, in the form of actual benchmarks]
The thing is that list fusion and whatnot is all just there to get around the handicap that was placed there in the first place by the language paradigm. So you start by insisting on shooting yourself in the foot, then put lots of armor on your boot so the bullet hopefully bounces off.
I assume by "vectors" you mean arrays ... there is no case in which this can be faster than arrays, because in the limit, if the list fusion system works perfectly, it is just making an array. A thing can't be faster than itself.
If you need something predictable, you'll usually use a vector in Haskell. Nothing obligates you to use a list.
I regard it as more of a pleasant surprise and something that surprises/confuses people when they benchmark `String` (which is `[Char]` under the hood) against `Text` (which is an `Array` under the hood: http://hackage.haskell.org/package/text-1.2.2.1/docs/src/Dat... )
What I'm not going to do is perform free labor for a man with a bad attitude who is 100x wealthier than I am. I'm not saying you should design a performance oriented language around short-cut fusion, but the "cost" of using Haskell is generally not what people think it is.
The span of applicability for Haskell, IME, ranges from Java/Golang to Ruby. It's no replacement for C++, but it does come close in some applications that aren't hard/soft real-time.
There are two advantages of lists, however: you can add elements to a list without modifying the original list or ever having to reallocate it, and garbage collection never requires defragmentation as all lists (except NIL) are implemented as exactly two words, the head and a pointer to the tail.
If you're processing huge quantities of data or writing games, the speed hit you take from frequent cache misses probably means you should avoid lists whenever you can. You should certainly avoid them in non-garbage collecting languages such as C where you have the additional inconvenience of manual memory management of two word data structures. But those kinds of programs are atypical - most involve frequent user interaction.
Almost all languages (including Lisp) have contiguous data structures and these will often fit the data better. Also, lists which aren't built up a cell at a time will be CDR-coded if the language implementation supports that.
> Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower.
Careful. I've actually done some recent benchmarking (in OCaml, not Haskell), and the results don't necessarily bear that out, especially if you need dynamic arrays rather than static arrays.
A particular use case is the creation of dynamically sized temporary data. A bump allocator will put list nodes in a contiguous section of memory, but does not require resizing. A dynamic array may be resized several times, requiring additional copying and allocations (and possibly expensive major heap allocations).
As a result, the relative performance difference not only may not be as dramatic, but can actually swing in the favor of linked lists.
Note that I'm not saying that performance degradation due to poor memory locality of linked lists won't happen, just that there are plenty of use cases where this is not a problem.
You can allocate more space than you might need to avoid resizing. It's not uncommon for Java programmers to pass a size when initializing empty array lists, knowing they will be filled.
Even if the list were fully cached in L1, traversing an array can be significantly faster as the CPU can extract a lot of parallelism. On the other hand a list is a long dependency chain of non trivial latency instructions.
Linked lists (and other node-based data structures) of course shine for modification heavy work, when traversal is uncommon or when you need to preserve addresses.
just some personal experience: While i don't doubt it's true, GHC and it's GC are so optimised for this scenario that (compared to for example java) i don't notice much of a slowdown.
Also haskells different execution-model comes into play. You don't really iterate much over lists, but instead execute "specific code blocks".
Grrr. None of this (article or most of the comments) has much to do with Haskell. It applies to all languages, right? You implement an abstraction using an appropriate data structure, accounting for the frequency of various operation you plan to perform. Often a list will be the wrong data structure - no big surprise.
But if you'd like to implement a stack, perhaps with a lot of elements, then a singly linked list is a reasonable choice. But you need to think about the operations you need. If you're just pushing, popping, looking at the top element, checking for empty, then great!
If you need to check the length, then you'll need to keep a counter, otherwise you'll pay O(n) time. If you need to make a copy for read-only purposes, great, constant time. If you need to make a copy for destructive use, then you'll have to pay O(n) time. This is all Mom-n-apple pie.
You're absolutely right, but I think the article was mostly griping about Haskell list syntax and how it can lure less experienced programmers into using lists where they're inappropriate.
My favorite data structure has a list and a map under the hood. Lists are used precisely for the ordering, and you constantly index into the list, but only with direct pointers. I dunno how you'd implement it in Haskell, but lists are actually a really good building block -- although you often can replace them with arrays if you're clever enough.
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.
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.
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?
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.
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...
Insertion and removal from the start is very fast, one of the fastest data structures for insertion in Haskell. While keeping lazyness and persistency. Making them appropriate for a bunch of common use cases in functional programming/recursion/logging/timetraveling/etc...
51 comments
[ 254 ms ] story [ 1699 ms ] threadSite needs to upgrade its certs.
https://www.eff.org/https-everywhere
It still uses linked lists as an intermediate representation (the type class consists of a function `fromList :: [a] -> t a`) but since lazy lists are generators this is quite sensible.
There's a lot of old stuff in Haskell, e.g. String which is a list of char. We have a number of new preludes (base, foundation, protolude, ..) that improve the situation a lot, so I'm not sure we really need a "python 3" moment.
We could definitely be more aggressive in pointing out that you need to use a new prelude though.
The worst thing about the default Prelude is that it encourages bad behavior among new users--for instance, with partial functions like `head`. Experienced people know what to avoid and what to work around. So if picking an alternative Prelude seems like too much work, it is.
I have a project where I have mostly dumped the Prelude. All it is doing is saving me a bunch of imports. That's nice but not earth-shaking.
* "id" renamed to "identity" so you can use id in your own code
* panic functions like "notImplemented"
* a generic string converter "toS"
* lots more
But to be fair most modern preludes work OK.
Foundation is a bit different in that it doesn't ship a huge amount yet but has the potential to eventually replace the core prelude with saner default types like utf8-encoded strings. If you need to ship to production yesterday I would not use Foundation just yet.
I love that people think that being Unicode somehow makes strings into opaque objects that you can never inspect or manipulate. Do you think that strings magically pop into existence fully formed and then magically disappear into a magic box and come out as rendered glyphs on a screen?
I don't disagree that [Char] is a stupid way to represent strings. Strings should very obviously just be byte arrays. Go does it right, it's one of the few things it does right. It turns out the creators of UTF-8 know how to deal with Unicode properly. Who would have thought?
I have no problem with an opaque string type that supports being serialised into bytes. I also have no problem with a string type that exposes the reality that it's internally represented as UTF-8. But I can understand that maybe that's a little imperfect, because you might not want to maintain a perfect normalised correct UTF-8 encoding all the time. e.g. if you concatenate "blahblahlblaha" and the combining acute symbol followed by "blahlbahlblah", you might want to just store them together and normalise them later or something? I don't know.
However these problems only exist for literals, and typically literals in source code are not going to be so huge for lists to be a problem anyway.
A list literal is like a string literal: convenient. Getting rid of the special syntax wouldn't accomplish anything.
Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower.
This is because the CPU will load contiguous chunks of memory into cache. On x86, the cache block size is 64 bytes. So for an array of 4 byte ints, you are loading 16 ints into cache at a time. With a linked list, you will likely get a cache miss on most nodes and have to access RAM. Access time for L1 cache is 0.5 nanoseconds, access time for RAM is ~100 nanoseconds.
Make two List<Object>s. One is LinkedList one is ArrayList.
Then timed how long it took to empty the list by deleting random indexes.
For LinkedList this is O(n) to iterate up to the element and O(1) to remove it.
For ArrayList isn't O(n) to shift all of the following elements down by 1 index.
As the list size approaches infinity, the benchmark shows that the ArrayList is 10x faster. That's because even though you are copying a ton of memory, it's all contiguous in memory and highly cacheable. In the LinkedList you are just chasing pointers to iterate the array, but they are not cacheable.
A more common example is the case of queues. I made two Queue<Object>s, one was LinkedList and another ArrayDeque. Then I polled the head of the queue until empty. As N gets larger, the ArrayDeque is 3x faster.
http://simonmar.github.io/bib/papers/parallel-gc.pdf
So, with that proviso, the answer to your question is yes and that as a result sometimes list code can be faster than vectors.
The thing is that list fusion and whatnot is all just there to get around the handicap that was placed there in the first place by the language paradigm. So you start by insisting on shooting yourself in the foot, then put lots of armor on your boot so the bullet hopefully bounces off.
I assume by "vectors" you mean arrays ... there is no case in which this can be faster than arrays, because in the limit, if the list fusion system works perfectly, it is just making an array. A thing can't be faster than itself.
I regard it as more of a pleasant surprise and something that surprises/confuses people when they benchmark `String` (which is `[Char]` under the hood) against `Text` (which is an `Array` under the hood: http://hackage.haskell.org/package/text-1.2.2.1/docs/src/Dat... )
I've had `String` come out faster than `Text` in benchmarks plenty of times, including for a colleague when we were writing up this post https://lorepub.com/post/2016-12-17-Haskell-Pitfalls
What I'm not going to do is perform free labor for a man with a bad attitude who is 100x wealthier than I am. I'm not saying you should design a performance oriented language around short-cut fusion, but the "cost" of using Haskell is generally not what people think it is.
The span of applicability for Haskell, IME, ranges from Java/Golang to Ruby. It's no replacement for C++, but it does come close in some applications that aren't hard/soft real-time.
If you're processing huge quantities of data or writing games, the speed hit you take from frequent cache misses probably means you should avoid lists whenever you can. You should certainly avoid them in non-garbage collecting languages such as C where you have the additional inconvenience of manual memory management of two word data structures. But those kinds of programs are atypical - most involve frequent user interaction.
Almost all languages (including Lisp) have contiguous data structures and these will often fit the data better. Also, lists which aren't built up a cell at a time will be CDR-coded if the language implementation supports that.
Careful. I've actually done some recent benchmarking (in OCaml, not Haskell), and the results don't necessarily bear that out, especially if you need dynamic arrays rather than static arrays.
A particular use case is the creation of dynamically sized temporary data. A bump allocator will put list nodes in a contiguous section of memory, but does not require resizing. A dynamic array may be resized several times, requiring additional copying and allocations (and possibly expensive major heap allocations).
As a result, the relative performance difference not only may not be as dramatic, but can actually swing in the favor of linked lists.
Note that I'm not saying that performance degradation due to poor memory locality of linked lists won't happen, just that there are plenty of use cases where this is not a problem.
Linked lists (and other node-based data structures) of course shine for modification heavy work, when traversal is uncommon or when you need to preserve addresses.
Also haskells different execution-model comes into play. You don't really iterate much over lists, but instead execute "specific code blocks".
But if you'd like to implement a stack, perhaps with a lot of elements, then a singly linked list is a reasonable choice. But you need to think about the operations you need. If you're just pushing, popping, looking at the top element, checking for empty, then great!
If you need to check the length, then you'll need to keep a counter, otherwise you'll pay O(n) time. If you need to make a copy for read-only purposes, great, constant time. If you need to make a copy for destructive use, then you'll have to pay O(n) time. This is all Mom-n-apple pie.
Haskell does also have a Stream data type which is similar but features a different set of tradeoffs.
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...
The author somehow forgot to mention that.
One could argue that the mistake Haskell made was to call them "lists" instead of "streams", and to make it so easy to make list literals.