When You Should Use Lists in Haskell (Mostly Not)
imn.htwk-leipzig.de
imn.htwk-leipzig.de
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.
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.
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.
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.
Site needs to upgrade its certs.