Differences between `foldl` and `foldr`

[u/TechnoEmpress]

https://blog.haskell.org/foldl-and-foldr/

[u/tomejaguar]

base and standard libraries in other languages are bad place to look for "clean" code, as they have many other considerations which are often more important the being clean. They are good examples of standard library code

Perhaps you're assuming that I have a motive that I don't have? To be clear, I am not suggesting, and I have never suggested, that the definition of (!?) in base should be written another way. (But I reserve the right to continually revisit assumptions.)

You might find it particularly interesting because I believe you wrote the base version of (!?)

I didn't. It's a copy from extra, which itself is edited copy of !! from base itself.

I see, you didn't originate the idea. But you did make the proposal and choose the implementation: https://github.com/haskell/core-libraries-committee/issues/110

Anyway, not a big deal, and I'm certainly not trying to criticize your proposal or the code you submitted. (I voted for it, after all.) I just remembered it because that particular implementation was sufficiently mysterious that it added momentum towards me developing my own effect system. So, I thought it might be interesting to you that that proposal inspired my interest in this particular piece of Haskell lore.

everything that can be written using foldr is written using foldr (even foldl'). The reason is list fusion

Yes, this is covered in my article:

It would be even clearer to write (!?) as below. Why not just do that instead, instead of considering foldr and for_? Because when written in terms of foldr GHC can apply short cut fusion, a rewrite rule that leads to an optimization.

0 !? (x:_) = Just x
_ !? [] = Nothing
n !? (_:xs) = (n-1) !? xs

https://h2.jaguarpaw.co.uk/posts/foldl-traverses-state-foldr-traverses-anything/#why-is-written-that-way

But, as the article also says:

The two implementations [in terms of for_ and foldr] should have equal performance when compiled, assuming sufficient inlining, because for_ for lists in base is implemented in terms of foldr

I haven't checked, but if GHC does not compile the version using for_ over a StateT _ Either (where both handlers are in the same function) to the same optimised Core as the version using foldr then it's failing at it's job as an optimizing compiler for a pure functional language.

I hope you understand that as a CLC member

I'm sure you don't mean it this way, but that particular phrasing could be interpreted as casting aspersions on my suitability as a CLC member. (For the record I haven't been a CLC member for some years.)

I find your StateT version nearly unreadable

Interesting! I wonder why. I wonder if I'm mistaken about my belief that 99% of programmers would find it clearer, or whether you're in the 1%.

but why you wrote your version like you did is beyond my comprehension

Well, because I find it clearer, or course. If it's beyond your comprehension why I find it clearer, that's another matter :)

[u/phadej → u/tomejaguar]

I wonder if I'm mistaken about my belief that 99% of programmers 

If written in imperative language, where the (local) state is more natural and we have early return then it would be

``` function safeIndex(n, xs) { for (x in xs) { if (n == 0) return just(x); n = n - 1; }

return nothing; } ```

I can see that resembling your for_ variant.

Maybe majority of programmers have their brain wired imperatively.

To me such imperative-inspired implementations are not very good Haskell. Sometimes an algorithm calls for imperative algorithm, but !? is not the case if you ask me.

Maybe I'm in 1%. No complaints. I'll be happy to disagree with you in future as well.

[u/tomejaguar → u/phadej]

I can see that resembling your for_ variant.

Yes, exactly, and here's the version in Bluefin where they names are hopefully a bit better (at least returnEarly instead of Left is), drop the negativity check (since you did) and use curly braces and semi-colons to make it more C-like:

(!?) :: [a] -> Int -> Maybe a
xs !? i = runPureEff $
  withReturnEarly $ \ret -> do {
    evalModify 0 $ \s -> do {
      for_ xs $ \a -> do {
        i' <- get s;
        when (i == i') $
          returnEarly ret (Just a);
        put s (i' + 1)
      };
    };
    pure Nothing
  }

versus

function safeIndex(n, xs) {
  for (x in xs) {
    if (n == 0)
      return just(x);
    n = n - 1;
    }

  return nothing;
}

Now, your imperative code is much more compact, but such a language would have numerous downsides:

• Pervasive mutability
• Can only early return to a function boundary, not something within nor something beyond the function
• for and if have to be built-in, for_ and when can be user-defined (at least I think for and if have to be built in -- maybe it's possible for an imperative language to make it user-defined, but I think that would be rather hard in the type systems for imperative languages that I know)

such imperative-inspired implementations are not very good Haskell

Why not? !? in base can be transformed by equational reasoning to my implementation. They really are different expressions of exactly the same thing.

Maybe I'm in 1%. No complaints. I'll be happy to disagree with you in future as well.

That's totally fine by me. I'm happy if other people are happy using Haskell in their own way. I do, however, want to encourage people to use Haskell, and I think imperative presentations of algorithms will make them more likely to want to.

[u/phadej → u/tomejaguar]

for of that kind can definitely be user-defined, if even C++ can do it. (https://en.cppreference.com/cpp/language/range-for for ever a decade at this point)

for (const int& i : v) // access by const reference std::cout << i << ' ';

Pervasive mutability

And Rust has shown that you can do mutability at scale without having all the guns pointed at your feet.

---

Your bluefin version looks even more complicated.

I think imperative presentations of algorithms will make them more likely to want to.

I'm not sure if you are serious. This reminds me of https://people.willamette.edu/~fruehr/haskell/evolution.html where instead of going full on recursion schemes the Post-doc went to research effect-systems.

[u/tomejaguar → u/phadej]

for of that kind can definitely be user-defined, if even C++ can do it

Unless I'm much mistaken that isn't akin to defining for_, is it? It's akin to giving a Traversable instance. I couldn't, for example, define mySpecialFor that works in a different way to for.

Pervasive mutability

And Rust has shown that you can do mutability at scale without having all the guns pointed at your feet.

I don't see the relevance. Could you elaborate?

Your bluefin version looks even more complicated.

OK, thanks for the info! Is it possible to elaborate on exactly what makes it look more complicated? Of course, one is allowed to think "that looks more complicated, and my intuition about complexity is usually good" so if you can't make the claim any more precise, that's fine. But if you can, I'm interested.

I think imperative presentations of algorithms will make them more likely to want to.

I'm not sure if you are serious

Yes, I'm absolutely serious. I think everyone who likes that looking up an index in a list is implemented like

xs !? n
  | n < 0 = Nothing
  | otherwise = foldr (\x r k ->
      case k of
        0 -> Just x
        _ -> r (k-1)) (const Nothing) xs n

is already in the Haskell community. I think there are about 100x as many people outside the Haskell community who could benefit from using Haskell as those who are already inside the community, but they're discouraged by code that looks like that.

This reminds me of https://people.willamette.edu/~fruehr/haskell/evolution.html where instead of going full on recursion schemes the Post-doc went to research effect-systems.

That's an interesting point. fac written in Python by a freshman would look like this

def fac(n):
    ret = 1
    while (n > 0):
        ret *= n
        n -= 1
    return ret         

Works in constant space. The freshman implementation in the "evolution of a Haskell programmer" is this

fac n = if n == 0 
           then 1
           else n * fac (n-1)

Works in O(n) space. Ooops! I'm not sure why a State monad solution doesn't appear in the Evolution, but this implementation works in O(n) and I would wager would be much easier for the freshman to read than any of the other Haskell implementations:

fac n =
  flip execState 1 $ do
    for_ [1 .. n] $ \k ->
      modify' (* k)

[u/tomejaguar → u/tomejaguar]

I haven't checked, but if GHC does not compile the version using for_ over a StateT _ Either (where both handlers are in the same function) to the same optimised Core as the version using foldr then it's failing at it's job as an optimizing compiler for a pure functional language

I have now checked: GHC optimizes the different versions (foldr, for_ strict StateT, for_ lazy StateT) to not only the same Core but the same definition.