I think the iteration combinators are part of the Haskell family vocab (PureScript and Elm etc re-use them), I prefer thinking in terms of names than explicit loops. I don’t mind efforts to abstract a few names with a broader concept, but I don’t see it inherently as an improvement always all the time.
The lens package also replaces a bunch of standard functions with various types of traversals and prisms and whatnot. So you’re not the first or the last to propose abstracting all the combinators.
Thanks for the benchmark! I’m very surprised that the streaming version of mapMaybe would be slower than the list version. They ought to optimize to the same code. Perhaps streaming is missing some fold/build rewrite optimization rules.
Looking at the generated Core, this is unfortunately very much not the case. I’m honestly a little surprised that (*>) is seemingly not inlined. Might be the recursion in its definition?.
Core for mapMaybe using Streaming (slightly reordered for clarity)
mapMaybe
= \ @a @b f as ->
letrec {
go1
= \ ds ->
case ds of {
[] -> mapMaybe1;
: y ys ->
case f y of {
Nothing ->
$fApplicativeStream_$c*>
$fFunctorOf $fMonadIdentity mapMaybe1 (go1 ys);
Just x ->
case x of conrep { __DEFAULT ->
$fApplicativeStream_$c*>
$fFunctorOf
$fMonadIdentity
($fApplicativeStream_$c*>
$fFunctorOf $fMonadIdentity (Step (:> conrep mapMaybe1)) mapMaybe1)
(go1 ys)
}
}
}; } in
toList (go1 as)
mapMaybe1 = \ @b -> Return ()
Rec {
toList
= \ @a @r s ->
case (poly_loop s) `cast` <Co:9> :: ... of {
Nothing -> [];
Just ds -> case ds of { (h, rest) -> : h (toList rest) }
}
end Rec }
Rec {
poly_loop
= \ @r @a stream ->
case stream of {
Step ds ->
case ds of { :> a1 rest ->
(Just (a1, rest)) `cast` <Co:10> :: ...
};
Effect m1 -> poly_loop (m1 `cast` <Co:6> :: ...);
Return ds -> Nothing `cast` <Co:10> :: ...
}
end Rec }
By contrast, the list version pretty much optimizes to itself, since this is about as efficient as any mapMaybe operation can be (without anything extra fancy like reuse analysis). E.g. mapMaybe shouldn’t even allocate more than the equivalent C code.
Core for Data.Maybe's mapMaybe
Rec {
mapMaybe
= \ @a @b ds ds1 ->
case ds1 of {
[] -> [];
: x xs ->
case ds x of {
Nothing -> mapMaybe ds xs;
Just r -> : r (mapMaybe ds xs)
}
}
end Rec }
Fusion rules do make a difference, but even without them, the list implementation is (unsurprisingly) still ~6x faster than the streaming one.
This is interesting! Thanks for looking. I’m not surprised that *> doesn’t optimize too well, but I am surprised that *> specialized to Identity doesn’t, since it is basically list cons. Once you have that, mapMaybe Just really ought to optimize to the identity function.
Some have already brought up the rule of least power and how polymorphism making things harder to read, but I want to add that having names is useful! If I see a name that I do not recognize, I can look it up, see what it does, and understand its role as a building block in the larger program. With nested for-loops, there is no visible separation of such blocks in the program. Of course it is still possible to understand the code and maybe identify the logical pieces, but it requires more effort.
When we use for_, we need an Applicative f but we throw away the a in f a. This means that we never needed an Applicative, only a Monoid. In other words, it’s a fold. Consider foldlM, which takes s -> a -> m s, but when we involve StateT it becomes a -> StateT s m b or equivalently a -> s -> m (b, s) where the b is entirely unnecessary. So StateT is overpowered here.
Note: This doesn’t mean that one should never use for_, because sometimes the Applicative is not avoidable. A simple example is traverse_ print xs. In other cases, I will choose to use a fold instead of for_.
Another example of using overpowered constructs is the loopM example. I’ve never used this combinator, but let’s say I need this behavior so I decide to write it inline. It would look something like
fooLoop :: Bar -> M Quux
fooLoop x = do
r <- ... do something with x ...
case r of
Left x -> fooLoop x
Right y -> pure y
Now compare it with
fooLoop' :: Bar -> M Quux
fooLoop' s0 =
runEarlyReturnT $
flip evalStateT s0 $
forever $ do
s <- get
fs <- (lift . lift) (... do something with s ...)
s' <- lift (except fs)
put s'
To understand this, one needs to first understand 1. how ExceptT works, 2. how StateT works, 3. how forever works. These are powerful constructs but none of them are necessary here. I find it far easier to both write and read the version that does not use them.
I suppose so, but barely. It’s “overpowered” in a way that >> pure () restore to be exactly-correctly-powered. For Applicative f, f () is a Monoid (witnessed by Ap) and for Monoid m, Writer m () is isomorphic to it, so there’s really not much daylight between these concepts.
I prefer to use the Applicative form because writing loop bodies using Monoid is actually quite a pain.
To understand this, one needs to first understand 1. how ExceptT works, 2. how StateT works, 3. how forever works
Yes, three simple concepts that can be understood in isolation and composed freely. Your proposed alternative is to understand not only recursion, which already seems too challenging for many programmers, but tail recursion, to guarantee we don’t use more space than intended!
A point I’ve seen made is that saying “for_ generalises other iteration combinators” misses their point.
Goto generalises for, while, and subroutines, but nobody uses goto. Because the point is not to use the thing with the most power, but to use the thing with the least power that’s still up to the task. That way we can more easily grasp the structure of what’s going on.
It’s similar to the way we use static types to restrict the programs that the compiler will accept, in order to gain greater understanding of what the program actually does.
I agree that it’s annoying to have to memorise a menagerie of different combinators, but it’s not a tradeoff we make for no reason.
To use, definitely! I have several non-Haskellers (perhaps not even “programmers” from the point of view of software developers – they “program” hardware instead, in System Verilog) happily writing for and for_ loops (admittedly over Bluefin Eff rather than monad transformer per se, but syntactically they’re very similar). I don’t believe I could get them to write recursive definitions. Furthermore, the for and for_ versions look a lot like what Pythonistas are used to writing every day. So yes, I think “monad transformers” are easier to use than recursion.
Ah, well I agree with this! So I’ve clearly explained myself badly. This is a paragraph from the article:
The final version of extend is the same as the original version, not just in the sense that it calculates the same result, nor even just in the sense that it calculates the same result in the same way, but that it is a transformation of exactly the same code. This implies all the same benefits we expect from pure functional code when it comes to maintenance and refactoring. For example, if extend had been written in Python or Java then the type system wouldn’t catch it if I slipped in a call to delete files from disk, make network connections or launch the missiles; in the “imperative” extend written in Haskell it would: I can only do “State effects on a PPreAssignment”, and “Either effects on a Conflict”.
Hopefully it resolves your complaint, even if it doesn’t do so very clearly. The point is that foldl' restricts power along two dimensions:
It processes the list sequentially one element at at time
It can do at most state effects
for_ of a State action restricts power to exactly the same extent (but compositionally):
for_ processes the list sequentially one element at at time
State can do at most state effects
@TeofilC objected that the latter restriction requires “type checking in one’s head”. My counter is that for_ @_ (State _) achieves the same end without requiring a mental type checker.
(Naturally one can further object that this is messy, but perhaps let’s reserve judgements on syntax until a body of knowledge has been built up around the new style.)
Exactly! And in the style I’m proposing it is actually an explicit use of static types: the choice of the type of the inner applicative/monad. Moreover, those types are composable. When we use foldl', on the other hand, the choice is invisible, implicit and non-composable.
Well then, what’s the reason? When it comes to foldl', mapAccumL, loop etc. my suggestions really do have the “same power”. (I concede that filter and mapMaybe have a non-trivial property not captured in the choice of applicative/monad.)
And I also don’t actually believe Haskellers take “least power” as seriously as you’re suggesting. I can imagine a Haskeller writing the following, and believing they’re using “least power”:
f a b c = g . foldl' p z
where
g = ...
p = ...
z = ...
But they’re not actually holding to “least power” (even though they’re writing foldl' instead of for_) because they haven’t restricted the scopes of a, b, c, g, p and z. Does p really need a, b, c, g and z in scope (and itself, recursively?). Probably not! So it’s written in a “more powerful” way than it could be. That’s no different from using a “too powerful” inner monad/applicative in the body of a for_ (this became obvious to me after using Bluefin for a while, because available effects really are the same thing as “in scope values”).
Ah, I see what you’re saying, that makes sense. That’s my fault for skimming. From here I’d retreat to saying that I find editing long type signatures, as I frequently find myself needing to do to comprehend/write effectful code, to be a bit of a pain in the ass. Particularly when I’m just trying to get some sub-function in a where clause to compile.
Compared to your examples, I would have to be extracting more stuff into local bindings with type signatures to confirm to myself what the types of the subexpressions are. I’m just not smart enough to keep them in my head at once.
Another complaint is that we’re sort of swapping one proliferation of combinators for another, you have to memorise evalState and runState and execState and the corresponding transformer versions. And all the other runWhatevers and for the other effects you want to use. And flipping them to make the syntax work out. And all of that stuff feels like boilerplate to me.
I think it’s possible but difficult for an effect tracking language to be ergonomic enough for me to find this sort of thing pleasant. Eg. Unison’s implementation of algebraic effects (“abilities”) seems pretty nice. I think it’s sort of inevitable that all Haskell effect system libraries are going to feel a bit bolted-on compared to languages that have one built in. I’m developing a bit of a distaste for monads honestly.
Yeah, this is what witherable is for, right?
Sure, as with many techniques, there are diminishing returns when you starting getting too zealous with it.
I think that’s fair enough. My experience with this style is such that I actually ended up preferring it to “standard iteration combinator style”, so I’m confident at least some others will too.
Yes, sort of, but a decent effect system makes this much easier. effectful decided to flip the args of its run/eval/execState so the user doesn’t have to flip. I think that’s the right decision. Bluefin followed suit.
Regarding the choice between run/eval/execState, I just always use evalState (mnemonic: “evalState is invaluable”) because it’s simplest one that generalizes the others.
Regarding runWhatevers, well, that’s just the natural way of using effect systems (and Bluefin makes it even easier I would say, because the runWhatevers are the only way of getting the effect handle in scope in the first place!).
Yes, that’s right.
Bluefin is giving more a better taste for monads. I invite you (and anyone) to try it and see if you feel the same. If you do, drop me a line with any questions or comments!
