It never makes sense to use foldl on lists in Haskell (2019)
github.com
github.com
In most language, you should generally prefer foldleft to foldright as foldright is not tail-recursive.
(and chances are that you will still leak memory like crazy)
uncurry (/) . foldl' (\(s,l) x -> (s+x,l+1)) (0,0)
uncurry (/) . foldl' (\(!s,!l) x -> (s+x,l+1)) (0,0)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'`.
I don't understand how that's different in practice. Can you elaborate?
`reduceRight` processes and accumulates right-to-left, so it doesn’t have the short-circuiting ability of `foldr`.
Because they suck.
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.
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.
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..])
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.
The majority of langauges web frameworks are written in do not have linked lists, at all.
Python doesn't. Ruby doesn't. Java doesn't.
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.
IDK if this is the case for device drivers, but AFAICT device drivers tend to preallocate memory on loading and manage it locally.
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.
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.
Re-read my original post: "[...] especially if you have callbacks which store a pointer to a list element [...]"
This happens all the time in kernel code or bare-metal programming.
What else can I say? Open the Linux source code [1] and see for yourself.
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.
> The way modern memory works linked lists are practically a denial of service attack on system performance.
and
> IMO, like goto’s it’s better to just forget they exist.
That's as close to "never use a linked list" as you can get without saying that literal sentence.
So do arrays, FYI.
> It's really better to aim for non-circularity and to avoid the need for locks.
How does an array avoid the need for a lock where a linked list needs one?
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.
But, yeah, if you’re relying heavily on random access, pick a vector/array or some kind of tree/hash table.
They're quite useful in functional languages.
In Haskell in particular they can have nice performance effects if you use them sensibly.
That's for streaming I/O. Lazy linked lists are appropriate for streaming without side effects
Don't blame the language, & learn to use the right data structure for the job.
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 python, for example let's say:
def f:
arr = [0, 1, 2]
g(arr)
return arr[0]
Languages that default to using linked lists do not have this problem.
there are immutable non-linked list datastructures (the most obvious one in python are tuples)
def f(some_tuple):
part_one = take_the_last_three_parts_of_the_tuple(some_tuple)
part_two = append_to_self(part_one)
part_three = tail(part_two)
>>> x = ([1,2,3,4],"whatever")
>>> x[0].append('z')
>>> x
([1, 2, 3, 4, 'z'], 'whatever')
>>> 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!")Python is not a functional programming language....
You saying before the call to "g", you would make a deep copy of "arr" and that's faster to do with a singly linked list? Could you explain why?
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.
I'd still have to say that Singly Linked List arn't ideal for that either, better use a persistent hash array mapped trie backed list instead.
there's a real memory overhead for that structure.
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.
[0]: https://hypirion.com/musings/understanding-persistent-vector...
But foldl vs. foldl' is more about a badly-optimized implementation detail than anything else. It's very fair to qualify it as "in Haskell".
> foldl/3 is tail recursive and is usually preferred to foldr/3.
> 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.
Not quite - for example, these both benefit from foldr, despite each producing a scalar:
and, or :: [Bool] -> Bool
and = foldr (&&) True
or = foldr (||) False
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.
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.
Living in a shotgun shack
And you may find yourself
In another part of the world
And you may find yourself
folding an operator with short-circuiting behavior left-associatedly over a list
Let the data go by....
;)
would foldl makes sense as a map that teats for winning or death conditions?
Would it be folding a list of Nothing/Just X with an "or" operator
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.
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.
Here it is for your convenience: https://paste.rs/SWO
“LGTM aside from two minor comments”
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:
and = foldr (&&) True
all f = foldr (&&) True . map f
One might write 1:2:3:4:[].
foldr is deciding where to map [] and :. So for example:
[] => 0
: => +
With that understanding, foldr (:) [] becomes:
[] => []
: => :
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. "https://www.stackage.org/haddock/lts-15.4/base-4.13.0.0/Prel...
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).
What makes you think that?
> where "functions" are, half the time, actually not
Please elaborate.
function foo() {
print('effects');
}
bar = error "effects"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.
It was not supposed to be one. Rather, it was there to show that just like other languages Haskell functions can have effects (even if discouraged).
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.
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.
> 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.