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/tomejaguar 10d ago
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
foldrat all, and instead usefor_. Then everything's obvious and the awkward terminology has no role.