16 ms·

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.

• brmgb 7y ago
  Yes, 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 ago
    foldl' is fine an Haskell, and one of 2 endorsed by this.
    • dependenttypes 7y ago
      Note 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 ago
        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.
        • 08-15 7y ago
          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)
          • dependenttypes 7y ago
            {-# LANGUAGE Strict, StrictData, BangPatterns #-} should imply the !, right?
            • 08-15 7y ago
              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.)
          • nimih 7y ago
            Thanks, this is a helpful example :)
• pansa2 7y ago
  > 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'`.
  • skrebbel 7y ago
    > 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?
    • pansa2 7y ago
      Although `foldr` accumulates the result right-to-left, it processes the list left-to-right, which allows it to short-circuit. `reduceRight` processes and accumulates right-to-left, so it doesn’t have the short-circuiting ability of `foldr`.
      • skrebbel 7y ago
        Right! Super clear, thanks :-)
• Ericson2314 7y ago
  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.
• TylerE 7y ago
  Most other languages don't use singly linked lists to begin with. Because they suck.
  • cryptonector 7y ago
    In Haskell, because of laziness, lists work well enough, but they're really just a thunk container. Conduits are better.
    • Retric 7y ago
      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.
      • jerf 7y ago
        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.
        • cryptonector 7y ago
          > 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.
• tirumaraiselvan 7y ago
  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.
  • candeira 7y ago
    The bracketed "in Haskell" really tied the title together.
  • dnautics 7y ago
    It's also true in other languages. Erlang's foldr specifically annotates this in the documentation.
    • Dylan16807 7y ago
      The advantages to foldr in certain situations are very cross-language. 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".
    • masklinn 7y ago
      Erlang's foldr says exactly the opposite though, because Erlang is an eager language: > foldl/3 is tail recursive and is usually preferred to foldr/3.
      • dnautics 7y ago
        oh jeez I totally missed that. Thanks!
• thaumasiotes 7y ago
  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.
  • EvilTerran 7y ago
    > 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.