It's worth noting, if you either just read the title or are skimming the post, that "never" is used here specifically in the context of a language like Haskell. If your language uses strict evaluation (like most languages), it probably makes sense to use a left fold on lists.
> If your language uses strict evaluation (like most languages), it probably makes sense to use a left fold on lists.
The standard libraries of strict languages agree. Python's `functools.reduce` and JavaScript's `Array.prototype.reduce` perform strict left folds equivalent to Haskell's `foldl'`.
Interestingly, JavaScript also has `Array.prototype.reduceRight`, but it's not equivalent to a `foldr`. It processes the list from right-to-left, so is approximately equivalent to `reverse` followed by `foldl'`.
> Interestingly, JavaScript also has `Array.prototype.reduceRight`, but it's not equivalent to a `foldr`. It processes the list from right-to-left, so is approximately equivalent to `reverse` followed by `foldl'`.
I don't understand how that's different in practice. Can you elaborate?
OP here. My original submitted title was: It never makes sense to use foldl on lists (in Haskell); first line of the linked content. But someone dropped the bracketed content.
Out of curiosity, what causes foldl' to leak memory in most cases? I generally use it out of habit if I know I will consume the entire list and don't have a good reason to use foldr, so it would be nice to know if I'm shooting myself in the foot.
Foldl' doesn't leak, but it sure looks like it does, if you think the folded function is strict in the accumulator argument, but isn't.
For example, this attempt at computing the average of a list
uncurry (/) . foldl' (\(s,l) x -> (s+x,l+1)) (0,0)
leaks, because during the recursion, there is no reason to scrutinize the intermediate pairs. This version is fine:
uncurry (/) . foldl' (\(!s,!l) x -> (s+x,l+1)) (0,0)
I don't think it does. 'Strict' doesn't add an implicit ! to nested patterns (so (s,l) becomes !(s,l), not (!s,!l)), and 'StrictData' doesn't change anything about the tuple, which comes from a different module. (Disclaimer: I haven't actually used 'Strict', this is my interpretation of the user guide.)
The post is not saying don't use left folds, but use foldl' not foldl if you want a left fold. foldl' is (as far as these things are concerned) the strict language one.
The example of why you might want to use foldr instead of foldl is really poorly chosen. It relies on the idea that you don't want to reduce the list. There is even original emphasis on this assumption:
> foldr can possibly save on work if the reducing function is lazy in its second argument, and the result list is not entirely consumed. In fact, foldr can operate on infinite lists this way, while foldl cannot.
And to support the idea, we look at an implementation of map in terms of foldr. But I assume that if you're programming in Haskell and you want to map a function over a list, you'll use map instead of defining an ad-hoc mapped version of your function with foldr. This would be a great example of why, when we're defining map itself, we use foldr instead of foldl. But I wanted to see an example of why I might want to use foldr instead of foldl, not why I might want to reimplement map from scratch. They couldn't imagine a reduction that produced a scalar instead of another vector?
Of course, if you're reducing the list to a scalar, you lose all the benefits this article wants to claim.
> if you're reducing the list to a scalar, you lose all the benefits this article wants to claim.
Not quite - for example, these both benefit from foldr, despite each producing a scalar:
and, or :: [Bool] -> Bool
and = foldr (&&) True
or = foldr (||) False
... as they can both "bail out early" without evaluating the entire list (if they find a False or a True, respectively).
The distinction lies not so much in "are you reducing to a scalar?" as "can your binary operation be productive without evaluating its second parameter?" - or, if you prefer, "is it ever lazy in its second parameter?". If so, then foldr may be appropriate.
I mean, they might suck, but that's not really true that most languages don't use them. I can think of a lot that use them as their default data structure (OCaml, Haskell, Scala, Common Lisp, Racket, Clojure, etc). They're nice with recursion or if you don't know the size of your data ahead of time. But honestly, I've only used recursion a handful of times in my entire career, despite working almost exclusively with functional languages.
Correction for Clojure. It doesn't use singly linked list by default. It uses something more akin to an ArrayList, Clojure calls it Vector. Elements are indexed, and have pseudo O(1) lookup, and it adds to the end in pseudo O(1) as well.
Parent was talking about default data-structure, and for Clojure Vectors are the default "list" data-structure, even though it has other type of lists.
Not trying to throw any of the other languages mentioned under the bus, I do not know them well enough to know what list structure they default too or more idiomatically rely on.
In Clojure, most standard functions return lazy sequences, and in code people usually use vectors which are not linked lists. But it does of course have the classic Lisp list as well.
The way modern memory works linked lists are practically a denial of service attack on system performance. IMO, like goto’s it’s better to just forget they exist.
Linked lists stink as a manifested in-memory data structure. However, if what your linked list is is "{concrete value} : {code to generate the rest of the list}" and you walk it once, never having the whole thing at once, it isn't necessarily bad. That is the point cryptonector is making. The memory inefficiency of a linked list doesn't matter if you never really have it "in memory".
That said, the ready availability of linked lists in Haskell does mean that you end up with rather more strictly-manifested linked lists than you might like, since any of them can be manifested as actual linked lists. If you're using Haskell though, while you haven't exactly completely given up on that sort of performance, it must not be foremost on your mind.
> Linked lists stink as a manifested in-memory data structure. However, if what your linked list is is "{concrete value} : {code to generate the rest of the list}" and you walk it once, never having the whole thing at once, it isn't necessarily bad. That is the point cryptonector is making. The memory inefficiency of a linked list doesn't matter if you never really have it "in memory".
Yes, exactly. A lazy list is just another term for generator. If you hold on to a reference to the head of such a list as you run the generator, then you'll consume a lot of memory and will end up with a strict list, and also you'll be sad. But if you don't hold on to that reference, then it will be very efficient.
> That said, the ready availability of linked lists in Haskell does mean that you end up with rather more strictly-manifested linked lists than you might like, since any of them can be manifested as actual linked lists. If you're using Haskell though, while you haven't exactly completely given up on that sort of performance, it must not be foremost on your mind.
Especially strings as lists of characters. That was a mistake. Well, in some sense, character data has to be a list, since with Unicode you really can't efficiently index a string... unless it's a rope and you apply the sorts of tools that xi does (e.g., keeping track of character counts per rope segment, etc.). But strings should be sufficiently opaque that arrays, lists, and ropes are all equally able to implement their semantics.
Haskell has a duality between flow control and data structures as a result of its laziness. It is a perfectly valid point of view to look at such a thing as a control structure, rather than a data structure.
Technically, if you want to really understand how the "IO monad" does its thing, this is actually how it works. Technically your program declares a probably-infinite data structure that contains all possible paths your code could take, e.g., if you have a "if user input is negative then do X else do Y", what you really have is a data structure representing the if-then clause. What keeps the infinite data structure from being manifested in RAM is that the whole thing is resolved lazily, so only one branch will be actually evaluated. That's why the "IO monad" is actually pure; it simply "purely" creates a huge data structure that is resolved by an interpreter later. In the theoriest of theories, an IO value in Haskell really doesn't execute anything either and the whole language is pure... it is only the interpretation of the IO value that finally interfaces with the real world.
It isn't always the most helpful perspective and you can become an expert Haskell programmer without ever looking at your program this way, but technically, under the theory hood, that's what's happening.
Haskell is lazy, all data structures work this way unless specifically annotated otherwise.
Within standard haskell 2010 it is hard to declare a linked list that doesn't work this way.
It is also worth noting that haskell has library specified fusion rules so the closure isn't even allocated most of the time. So
sum (take 10 [0..])
compiles into an allocation free loop. I will give you that this isn't a linked list anymore, though.
In Haskell lazy values are just thunks. So a Lisp-style cons can have a tail that's just a thunk, and when you need to coerce it to a non-thunk value, it just happens and presto, you have the next cons. That's a list! A lazy list.
> The way modern memory works linked lists are practically a denial of service attack on system performance
Wrong. Intrusive, doubly-linked lists are extremely performant and useful in the right places, especially if you have callbacks which store a pointer to a list element (this often happens with device drivers in low level programming), or if the elements can belong to several lists.
The Linux kernel, for example, makes plenty use of linked lists.
> IMO, like goto’s it’s better to just forget they exist.
Wrong again. In a language without automatic memory management and without scoped destruction (cough C cough), they are immensely useful. Again, refer to the Linux kernel. Or any competently written, non-trivial C program for that matter. Note: I'm not defending C here, I'm defending correctly used gotos in C programs.
I don't think you can really get around linked lists having bad cache locality even if they're intrusive. The point of arrays usually being faster is that they're much more cache friendly, and fitting data in cache and avoiding branch mispredictions is usually much more important than o(1) insert/delete.
Linked lists fare worse than arrays only for sequential iteration in tight loops. That includes many/most cases, but not all. As for O(1) insertion/deletion: It's not always about amortized cost, sometimes you actually do care about worst case execution time.
Look, I'm not saying that linked lists can replace arrays. In fact, I almost always use arrays instead of linked lists. What I'm arguing against is the notion that arrays always trump linked lists, which is false, and repeating that meme shows a lack of deeper understanding.
I don't think I've heard anyone seriously suggest never using a linked list -- the advice usually just ends up being "are you really sure?" which seems appropriate.
Linked lists require you to be on the node in order to do an insertion so it’s generally not O(1) it’s O(n) with sky high constants. Thus for random inserts arrays are actually faster.
If you have a degenerate case and are never traversing nodes, you’re still likely better of with a rung buffer, array list, 2 different stacks, or various other options. And frankly you’re never going to endlessly just insert data without reading it.
Look we can all agree if you’re writing ASM your going to use goto’s. Further if linked lists are tiny or rarely used, it’s not a problem. If you can ensure the data stays in L2 cache it’s far less of an issue. If any number of things they don’t create problems, but frankly the general case encountered by most programmers are not that.
PS: If you don’t feel like pointing to a concrete example, I am going to counter with 99% of the stuff you can find here: www.google.com.
Arn't there hybrid array lists? Like where instead of growing the array when it goes beyond bound, the last slot is reserved to create a link to the next array chunk?
Linked lists are O(N) random insertion as you need to traverse the tree to locate the correct node. The only way that they are always O(1) are a degenerate case better suited for another data structure. Aka if you want a queue then use a ring buffer not a linked list.
This is only true if you’re writing code that’s compute bound: in 90% of the production code I’ve seen, the “inefficiency” of a singly-linked list is the absolute last thing that I worry about.
O(N) random reads and O(N) random inserts can quickly turn a wide rage of things to be compute bound. Creating a linked list from scratch via random insertions for example is an N^2 operation with surprisingly large constants.
Now sure, if it’s small and you’re only creating then reading it once then that’s fine. But, you’re assumptions need to be accurate or you just created a problem.
That's really not true. Whole web frameworks are built strictly around linked list structures that are far more robust, performant and DOS-proof than anything you'll write in your lifetime.
Basically, anything written in Elixir Phoenix, or erlang, so: Discord, Pagerduty, Bet365, the entire NHS. If you're a startup, in SF, there's a good chance your payments goes through Brex. You might be using Slab for your documentation, you might use Boston's MBTA, etc. Probably a not-insignificant chunk of what you do as a startup at some level depends on a framework that uses linkedlists. Do you use RabbitMQ or Riak? Linked lists are the primary list datatype for that system.
Singly linked lists let you do fast immutable list copies on entry into a new function context.
In python, for example let's say:
def f:
arr = [0, 1, 2]
g(arr)
return arr[0]
What does f return? You don't know. It depends on g. If g has other dependencies, and someone changes a deep dependency (or maybe a library changes an implementation) you could completely fuck up the result of f, spooky action at a distance, and all of your code could be hosed.
Languages that default to using linked lists do not have this problem.
There are better alternatives to linked lists for this use case.
1. Clojure uses wide balanced trees as its general-purpose ordered collection.[0] These have probably already been adapted for Haskell, and they offer persistence and fast random access and some degree of cache-friendliness. In my opinion it makes better trade-offs as a general-purpose structure.
2. By passing an &[usize] in Rust, or a const size_t* in C (i.e. by making g accept a read-only pointer), you can be guaranteed that g doesn't modify the array.
>>> x = ([1,2,3,4],"whatever")
>>> x[0].append('z')
>>> x
([1, 2, 3, 4, 'z'], 'whatever')
And python gives you access to anything:
>>> def gotcha():
... z = globals()['x']
... z = list(z)
... z.append("I've seen'em do it man!")
... globals()['x'] = tuple(z)
...
>>> x = (1,2,3,4)
>>> gotcha()
>>> x
(1, 2, 3, 4, "I've seen'em do it man!")
It be shallow with a Singly Linked List too no? What inherently makes a Singly Linked List better at addressing this problem if it contains mutable elements?
Typically, in a functional language, values are immutable.
So if you cons to a list, you create a new value that has the current list as its tail. Since all lists are immutable, they can be shared and there's no need for a deep copy.
Python is not a functional programming language....
sure but IIRC the performance characteristics of manipulating python tuples ultimately way worse if you need to change the contents of the list, by say, prepending, or trimming, or whatever. This is no fun in python:
"Copying" an immutable singly-linked list is just copying the reference to the first element. That is, the entire list is really shared, not actually copied element by element like an array would have to be. But since it is immutable, this doesn't matter: You cannot change it in a way that would mess up other users' view of the list.
What you can still do is cons new elements to the front of your copy. No other copy of the list will be affected. Because the list is singly linked, other owners of references into the list cannot walk back to observe your elements. They can even cons their new elements to the "same" list without any conflict.
All this is very useful if you want to process something with a stack, such that sub-operations can push elements to the stack that they have to remove again before returning. Pushing x and y to the stack is just constructing the list y : x : stack. Popping y and x from the stack when you're done is a no-op: "stack" is still a reference to the stack as it was before these operations.
It perhaps rarely makes sense, but not 100% never. You might at some point in your life have a situation where you want to fold an operator with short-circuiting behavior left-associatedly over a list (thus, with later elements of the list controlling whether short-circuiting happens skipping evaluation of-and-concerning earlier elements of the list). In this case, foldl is the way to go. foldl' can't execute the desired short-circuiting, and foldr can but only in the other direction, of right-associated bundling with earlier elements of the list controlling the short-circuiting of-and-concerning later elements of the list.
If there's ever a situation where you want to reverse a list and then foldr over it, taking advantage of the short-circuiting foldr allows, well, that reverse and then foldr is essentially the definition of foldl, have at it.
Probably you were just adding a reference and didn't miss the first one, but for anyone who did, it's "Once in a Lifetime" by Talking Heads: https://www.youtube.com/watch?v=5IsSpAOD6K8
> want to fold an operator with short-circuiting behavior left-associatedly over a list
And then you'd find out that it doesn't work the way you hoped it would. foldl always traverses the whole list, because there is no way for it to see that arbitrarily nested applications of the operator would still return the absorbing first argument.
If you need short-circuiting and left-associated traversal, you have to implement an improved fold. Oleg did, and called it iteratee.
I'd like to take the opportunity to thank lexi-lambda for multiple thoughtful contributions to the programming community. In the world of open source and software in general there are names that are recognizable - some feel more like "brands," intentionally cultivated, but I don't feel like I'm really being sold something when I see a post/article/wall of text from lexi-lambda, rather through repeated examples I've come to feel a bit of excitement that someone who has gone much deeper down an interesting technical path than I has taken the time to meaningfully share their knowledge and experience for the benefit of others. Thank you.
The linked comment is great. However, I think the HN heading is confusing, particularly for people who may not know about the existence of Haskell and its lazy-by-default semantics.
The linked comment recommends using strict/eager fold-left instead (`foldl'` in Haskell) of using lazy fold-left (`foldl`, with no trailing apostrophe). It's not saying that you shouldn't use fold-left in any language.
Reading the HN title alone, in its front-page context, it looks like it's saying that it's the fold-left generic operation that's wrong for lists, and not just `foldl`, Haskell's default lazy implementation of fold-left. Paradoxically, following the guidelines and re-using a boiled-down version of the linked comment's first line results in the line being misleading and/or link-bait (I guessed what it was about, but I still had to go and check).
For some time I've thought that the HN policy of disallowing editing of post titles, while correct, can be taken too far, and that many titles would be better with some annotation.
In this case, "It never makes sense to use [lazy] foldl on lists [in Haskell, use foldl' instead]" would be a better title. A bit awkward and maybe inelegant, but it says what the article means. Out of its original context, the HN title doesn't say what the posted article means.
Maybe "Lazy foldl versus strict foldl' in Haskell" would have been an even better title, if the guidelines allow for using one's discretion on when to disregard them.
Other common case is that of headlines in the first person: "My X ..." would often be improved by editing it to "[Name's] X ..." or "[Name of whatever X is] ..." while leaving it otherwise unchanged.
--
I don't know if @sama will get summoned to this comment like he would if this were Twitter, but it doesn't hurt to try.
I don't think HN automatically drops title items. Mods edit them. Mods regularly edit them to be significantly worse, because they'd rather the title exactly match the "article's" than the title being useful in and of itself.
This was the same for me. I think it’s because it was a line-level GitHub comment and the line has now changed.
It is possible to expand the post if you click “Show Outdated” on the two collapsed posts underneath the comment saying:
> Now, in this case, this is a silly operation, since foldr (:) [] is just a complicated identity function on lists, but we could imagine a slightly more complicated function, such as one that doubles each element in a list.
This whole post is great, but this part would be less awkward and easier to understand with a simpler example of more practical use like:
To spell things out a bit more:
A list is fundamentally constructed from [] and :. In the sense that a list is either empty [] or a head : tail, where tail is another list.
One might write 1:2:3:4:[].
foldr is deciding where to map [] and :. So for example:
This is a way better explanation than the cryptic:
" it (foldr) takes the second argument and the last item of
the list and applies the function, then it takes the
penultimate item from the end and the result, and so on.
See scanr for intermediate results. "
Haskell seems to be used with projects that are heavy on parsing (shellcheck, pandoc, graphql). I think that's partly because there just isn't a parser generator that feels right for general purpose languages, with haskell you seem to have less of a mismatch between the parser itself and handling of the parse tree. Is that a correct impression?
As I mentioned, foldMap requires associativity. Per your link I guess it also requires existence of a neutral element (whereas foldr instead makes you specify a starting element).
The issue is basically that haskell is a lazy language which ends up leaking memory left and right.
Most people that I have talked to about it seem to agree that haskell would be a trillion times better if it was a strict language. At least we now have Idris.
If Haskell was a strict language, we would never have invented monadic effects and would still be using () -> to (poorly) represent effects. Laziness forces you to avoid many such janky hacks that pervade almost every single strict language in existence (including most strict "functional" languages, where "functions" are, half the time, actually not), and which most people aren't even aware are janky hacks until they program with some kind of typed effect system
Whether it has an effect is not an issue. The issue is that it is referentially transparent.
Sure, we could have a discussion about whether partiality is an effect. Someone, somewhere is having that discussion. If the Haskell committee had had this discussion in 1987, chances are we wouldn't have Haskell at all.
This is the exact same objection people have been raising for 20 years. Yes, lifted types and partiality are probably bad. No, this isn’t an argument against distinguishing between functions and other objects. If anything, it just goes to show that Haskell should have been even more extremist about effect management.
Haskell is the only language outside of the proof assistant family to avoid the temptation to conflate evaluation with execution. It’s pretty clear in retrospect from looking at old papers on e.g. lazy list IO and old mailing list threads that modern monadic effects were born out of “well shit, Haskell makes us actually deal with this problem instead of doing what every ML language does with ()->”
> Please elaborate.
An object that is not referentially transparent is not a function. “Functions” in most languages are not necessarily referentially transparent, and even if they happen to be in a given case, it’s usually clear to neither the programmer nor the compiler.
Purity is what drives that as much or more than laziness. Well, I guess you can say that laziness came first and drove purity, which in turn drove effects.
Let me provide you a different perspective: A lazy language is one that "leaks space". A strict language, however, can "leak time". Imagine building an infinite list and pulling only ten elements from it. This is a situation where a strict language will create a "time leak" by attempting to build an infinite list.
I'm going to take inspiration from @lexi-lambda and respond in mini-composition form. Note that great writers write essays. I, write compositions.
It's just like Haskell for the crucial difference between two functions to be denoted by prime. For half of the essay I thought that this was a deep philosophical treatise about the degenerate case equality of lazy and strict languages. But, in reality, fold and fold-prime (can you inline code in HN?) are totally different functions.
And like with all pairs of things in Haskell once you learn the fundamental difference between them, the fact of that difference becomes obvious. So obvious that you don't know how anyone could possibly confuse the two. And so you call the method everyone should use foldl-prime even though a casual programmer doesn't even know that "single-quotes" are an acceptable value name. When you could have just called it foldl and moved the old one to the deprecated module.
This seems like a weird complaint - basically everywhere in programming two variables/functions/classes/etc with different names are different things. I'd be much more surprised if appending a ' to a function name did nothing in haskell.
> When you could have just called it foldl and moved the old one to the deprecated module.
1. Most people aren't a fan of randomly changing existing library functions
2. The lazy (non-prime) version of foldl isn't useless! There's even a section at the end of the post explaining how this post _only applies to lists_ and that with other data structures foldl and foldr' are actually useful.
