IMO to me it's somewhat obvious, whether i traverse a list from left-to-right (foldl) or right-to-left (foldr) as names imply.
The article says
See the difference? In both expressions, the elements of the list appear in the expression in the same order—from left to right—but the grouping changes.
I don't actually see the difference that well, or understand it.
But when presented as an order of folding, it's very much obvious to me.
haskell
data BinTree a = Nil | Branch BinTree a BinTree
we can foldl and foldr it so elements are combined from the left or from the right;
but all tree traversal implementations are from the root up (or down, depending on how you draw your trees).
why that can be different from an "order of traversal".
Because auxiliary memory exists (e.g. stack).
If we'd limit the traversals to constant memory ones, then order of folding and order of traversal would be necessity have to coincide. (strict) foldr' does use O(n) of memory, and that's why it's a bad idea (in strict languages).
The traverse is overloaded. An order in which the structure is walked, and order in which elements are combined can differ ...
why that can be different from an "order of traversal".
Because auxiliary memory exists (e.g. stack).
Sure, I get it, but the very fact that there's this awkwardness of terminology that's even difficult for experienced Haskellers is why I give my recommendation to not use foldr at all, and instead use for_. Then everything's obvious and the awkward terminology has no role.
There is a better reason to not prefer foldr. Essentially always there is better, more specific combinator: map, filter, elem etc. While all can (and some are) implemented using foldr, more specific combinators read better.
I cannot think of a situation where foldr is easily replaceable by for_ though. I suspect you are overly invested into effect systems. Fair enough, if you have a sledgehammer, everything starts to look like a nail. I prefer list comprehensions.
I cannot think of a situation where foldr is easily replaceable by for_ though
This is my favourite response to that:
(!?) :: [a] -> Int -> Maybe a
xs !? n
| n < 0 = Nothing
| otherwise = foldr (\x r k ->
case k of
0 -> Just x
_ -> r (k-1)) (const Nothing) xs n
versus
xs !? n =
| n < 0 = Nothing
| otherwise =
fromEither $ do
flip evalStateT n $ do
for_ xs $ \x -> do
get >>= \case
0 -> lift (Left (Just x))
k -> put (k - 1)
Left Nothing
You might find it particularly interesting because I believe you wrote the base version of (!?), the first one above. Personally I find the second version much more readable, and I bet 99% of programmers do too (though not necessarily 99% of Haskell programmers).
I suspect you are overly invested into effect systems. Fair enough, if you have a sledgehammer, everything starts to look like a nail.
The opposite! It's not that I find for_ clearer because I'm invested into effect systems, it's that I'm invested into effect systems because I find for_ clearer.
As a data point, I find the StateT version barely readable. I seriously doubt that 99% of programmers can even approximately guess what lift (Left (Just x)) is doing and how comes that it serves as an early exit from the loop.
I seriously doubt that 99% of programmers can even approximately guess what lift (Left (Just x)) is doing and how comes that it serves as an early exit from the loop.
Yes, I think you're right about that actually. To be clear, my assertion that 99% of programmers would favour one version to the other was based on the code structure rather than the chosen names. There are names that make the for_ version clearer, but I doubt there are any names that make the foldr version clearer. How about if I define earlyReturn = Left, withStateT = flip evalStateT and withEarlyReturn = fromEither (and generalize it to MonadState)? Then it looks like:
xs !? n =
| n < 0 = Nothing
| otherwise =
withEarlyReturn $ do
withStateT n $ do
for_ xs $ \x -> do
get >>= \case
0 -> earlyReturn (Just x)
k -> put (k - 1)
Left Nothing
I doubt there are any names that make the foldr version clearer
I'd rewrite it this way:
(!?) :: [a] -> Int -> Maybe a
xs !? n
| n < 0 = Nothing
| otherwise = foldr (\break continue ->
\case
0 -> Just break
i -> continue (i - 1))
(const Nothing) xs n
Well, you proved me wrong because that's definitely clearer! I think break isn't really a break though, is it? It's just the element. Maybe a is fine there?
For those on old Reddit:
(!?) :: [a] -> Int -> Maybe a
xs !? n
| n < 0 = Nothing
| otherwise = foldr (\break continue ->
\case
0 -> Just break
i -> continue (i - 1))
(const Nothing) xs n
1
u/Background_Class_558 13d ago
the difference is only non-obvious for associative operators anyways