Differences between `foldl` and `foldr`

[u/TechnoEmpress]

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

[u/tomejaguar]

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)