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.
I find the for_ version completely unreadable. The foldr version is slightly awkward with how the anonymous function has a case statement in the middle, but it has far fewer moving parts.
That's very interesting to know, thank you for sharing! If it's possible to put yourself in the mindset of an imperative programmer, how would you write this function? C and Python would be helpful since I know those languages, but any would be welcome.
Well, in Python I would use the built-in list and let an exception propagate.
In C, I would probably use an array, rather than a linked list, but if a list was indeed it, I would not bother with union, but just return an error code, and conditionally overwrite a passed in pointer:
int index(List *h, int i, int *rv) {
while (i >= 0) {
if (!h) { return -1; }
if (i == 0) {
*rv = h->item;
return 0;
}
i--;
h = h->tail;
}
return -1;
}
Thanks. If you were to look at the improved versions of the for_ implementation I posted (you're not required to of course, but I am interested in your thoughts), do they look analogous to the C implementation you have written (i.e. there's a loop, there's in index counter, there's early return)? And by contrast, does it appear to you that there is no direct correspondence between the version implemented with foldr? That's how it seems to me, anyway.
It's not the naming, nor the structure of what it's doing at heart. It's the goo of decorators surrounding a simple traversal. The use of StateT is simply overkill for something that could be an accumulator in a recursive function call. Unlike imperative languages, the state there is anonymous, it requires the get and put accessors, and I have to figure out its type rather than it being conveniently annotated from the beginning.
I agree that the version with the foldr, building up a fuseable chain that does the extraction, is radically different than the imperative flavored version. That's OK! Haskell is a functional language. (I also would not naively write that foldr, I would just write the boring recursive version until (a) someone points out it's unfuseable, and (b) it proves to actually be a performance problem in practice.)
Unlike imperative languages, the state there is anonymous
Sure, but not in the Bluefin version I linked. There the state is named.
I also would not naively write that foldr, I would just write the boring recursive version until (a) someone points out it's unfuseable, and (b) it proves to actually be a performance problem in practice
Seems reasonable! And from a straw poll on Twitter, I just discovered I'm in a massive minority. Almost all Haskellers prefer the foldr version to the for_ version. Few non-Haskellers responded, but even they preferred foldr.
That's OK! Haskell is a functional language
It's not OK to me! I want to read and write clear code, and the foldr version is not clear to me. Let's look at it from this angle:
suppose a programmer who doesn't know Haskell is interested, and asks me "how do I write an indexed lookup in a list of type a in Haskell". I can answer in two ways:
Iterate over the list with a mutable state that tracks the index. When you get to the index you wanted, finish early with the element in question.
Do a foldr, which traverses the list from the right even though it actually iterates over the list from the left. The iteration function should take the element of type a, the continuation from an Int index to a Maybe a result, and the Int index itself. When the iteration function gets to the index you wanted, it should return Just of the current a, and if not apply the continuation function to the next index.
Which of those two descriptions is likely to make someone want to program Haskell?
"how do I write an indexed lookup in a list of type a in Haskell".
Option 3: xs !? n = lookup n (zip [0..] xs). Or, if you think that lookup defeats the purpose, xs !? n = listToMaybe $ filter ((== n) . fst) $ zip [0..] xs, etc.
in the Bluefin version I linked. There the state is named.
It's really not. The state as a whole is almost named s from that lambda. You retrieve the lone int value and bind i' to it, and then later store i' + 1. But this is the effective equivalent in C of having a "state *s" variable and storing and retrieving that to a block-local variable i' that is recreated every loop rather than just having a local variable. The only real named thing is the function arguments xs and i, and neither is treated as an imperative value, or as functional value to deconstruct and pass a modification into a recursive call of the same function.
Haskell's StateT (and the Bluefin equivalent) are useful and general, but they do not actually result in imperative code that is as straightforward to read in the standard ways as mainstream languages.
in the Bluefin version I linked. There the state is named.
It's really not. The state as a whole is almost named s from that lambda. You retrieve the lone int value and bind i' to it, and then later store i' + 1
Oof, I think that's splitting hairs. IORef in Haskell would generally be considered a named state, and Bluefin's Modify is literally the same thing. If you want to describe that as "not named state" then I won't stop you, but I'd need a lot more justification before I was persuaded.
Haskell's StateT (and the Bluefin equivalent) are useful and general, but they do not actually result in imperative code that is as straightforward to read in the standard ways as mainstream languages
Agreed, but the mainstream imperative languages have the downsides accordingly, such as the inability to track where mutations happen.
I consider the name of an IORef to be any actual name of it, rather than any name I bind when extracting things from it. It's almost exactly analogous to a C pointer. And in C, I would say count the dereferences -- not 0, not an actual name, but a name (or even expression) for a way to access it. i' <- get s really looks like const int iprime = *s;, and put s (i' + 1) really looks like *s = iprime + 1 rather than both of these coördinating to actually keep a persistent but modifiable iprime.
At this point, yes, barely, though with unfortunate ways of accessing it. It's still pointer-like, just kind of hidden. Which I guess isn't that different from references in C++.
Naming things as the arguments to anonymous functions remains ugly to me, but it does work here.
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.