13 ms·
It never makes sense to use foldl on lists in Haskell (2019)
- microtherion 7y agoFor a second there, I thought "foldl" was the opposite of "hodl" in terms of cryptocurrency speculation.
- warkdarrior 7y agoSee Kenny Rogers's "The Gambler" for further information :) https://www.youtube.com/watch?v=kn481KcjvMo https://www.youtube.com/watch?v=kn481KcjvMo
- didgeoridoo 7y agoMaybe while the world is on fire we could have a moratorium on downvotes for attempts at levity?
- deleted 7y ago[deleted]
- hawkice 7y agoWhat does this random minor github discussion have to do with the submitted title? I'm on mobile, does 'foldl' appear on the page on desktop?
- Arnavion 7y agoIt is a direct link to a comment on the code of the PR. Here it is for your convenience: https://paste.rs/SWO https://paste.rs/SWO
- cortesoft 7y agoYeah, that doesn't show up anywhere on the page on mobile. Thanks!
- sealjam 7y agoThis 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: “LGTM aside from two minor comments”
- draw_down 7y agoI read a lot of this and eventually just gave up. If the difference between two (honestly quite similar) functions is this hard to describe, that's a smell.
- deleted 7y ago[deleted]
- jolmg 7y ago> 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: and = foldr (&&) True or all f = foldr (&&) True . map f x && y doesn't evaluate y if x is False.
- danharaj 7y agoMaybe, but foldr (:) [] ~ id is an illuminating fact in its own right that is worth pausing to understand.
- patrickthebold 7y agoTo 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: [] => 0 : => + Turns the above list into 1+2+3+4+0. With that understanding, foldr (:) [] becomes: [] => [] : => : which is fairly clearly the identity.
- toolslive 7y ago> foldr is deciding where to map [] and : 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. "
- kccqzy 7y agoIt absolutely is. It is the basis for the build/foldr stream fusion built into the standard library.
- im3w1l 7y agoSo if I got that right, the future best practice will be to use foldMap/foldMap' on all data structures unless you require a particular associativity.
- MaxGabriel 7y agoThat doesn’t sound like the correct reading to me, because foldMap and foldl/foldr have different type signatures https://www.stackage.org/haddock/lts-15.4/base-4.13.0.0/Prelude.html#v:foldMap https://www.stackage.org/haddock/lts-15.4/base-4.13.0.0/Prel...
- im3w1l 7y agoYeah, but they solve basically the same problem. 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).
- solomonb 7y agoOnly if you have a valid Monoid instance to work with..
- chc 7y agoIt'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.
- brmgb 7y agoYes, that's a very peculiar feature of Haskell. I'm slightly surprised this managed to reach the front page. In most language, you should generally prefer foldleft to foldright as foldright is not tail-recursive.
- Ericson2314 7y agofoldl' is fine an Haskell, and one of 2 endorsed by this.
- dependenttypes 7y agoNote that you need to import Data.List if you want to use foldl' (and chances are that you will still leak memory like crazy)
- nimih 7y agoOut 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.
- 08-15 7y agoFoldl' 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)
- deleted 7y ago[deleted]
- Chinjut 7y agoIt 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.
- erikpukinskis 7y agoAnd you may find yourself 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....
- DoreenMichele 7y agoLetting the data go by... ;)
- idclip 7y agoMakes me want to listen to letting the cables sleep by bush https://youtu.be/d8TrkCObypE https://youtu.be/d8TrkCObypE
- deleted 7y ago[deleted]
- taejo 7y agoProbably 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 https://www.youtube.com/watch?v=5IsSpAOD6K8
- dependenttypes 7y agoThe 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.
- wyager 7y agoIf 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
- dependenttypes 7y ago> we would never have invented monadic effects and would still be using () -> to (poorly) represent effects What makes you think that? > where "functions" are, half the time, actually not Please elaborate.
- yakshaving_jgt 7y agofunction foo() { print('effects'); } The above is not a function. It's a procedure.
- dependenttypes 7y agoAnd what about bar = error "effects"
- 08-15 7y agoIt's a partial function that always returns _|_. Haskell is not a total language (and whether a total language can be practical is yet to be seen).
- candeira 7y agoThe 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.
- Talanes 7y agoThe OP mentioned in another reply that their submitted title did include a (in Haskell) at the end, and it was dropped (automatically?)
- candeira 7y agoHow counterproductive.
- masklinn 7y ago> and it was dropped (automatically?) 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.
- thayne 7y agoWhat is the connection between the title and the linked PR. Where is the explanation of why it never makes sense?
- thayne 7y agoah, apparantly it is hidden on the page when you follow the link on mobile, but is visible on the desktop version :shrug:
- ionforce 7y agoPoorly written headline.
- abhayb 7y agoI'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.
- thenewnewguy 7y agoThis 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.
- ISO-morphism 7y agoI'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.
- MichaelMoser123 7y agoHaskell 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?