base has (essentially)
newtype Endo a = Endo (a -> a)
Endo f <> Endo g = Endo (f . g)
But is there a strict equivalent? That is, something that does
newtype StrictEndo a = StrictEndo (a -> a)
StrictEndo f <> StrictEndo g = StrictEndo (\a -> f $! g a)
I don’t recall seeing it. (I also realize that I’ve never seen strict composition, although it does exist in “pointless-fun”.)
I feel like it’s worth considering why you want a strict Endo in the first place. I feel like that will help determine what it should look like. With something like this, there are a surprising amount of candidates for a strict version.
The definition you gave makes sure that the function that is constructed is strict, and additionally is also strict in intermediary results.
Another possibility in that vein is something like:
newtype StrictEndo' a = StrictEndo' (a -> a)
runStrictEndo' :: StrictEndo' a -> a -> a
runStrictEndo' (StrictEndo' f) !x = f x
StrictEndo' f <> StrictEndo' g = StrictEndo' (f . g)
This variant would create a function that is only strict in the initial argument.
Yet another possibility is something like this:
newtype StrictEndo'' a = StrictEndo'' (a -> a)
StrictEndo'' !f <> StrictEndo'' !g = StrictEndo'' (f . g)
While this doesn’t necessarily construct a strict function, it does ensure that the constituent functions are evaluated to whnf.
I don’t actually want it, per se, but I do want to refer to it in an article I’m writing about folds. You’re right: its purpose determines what its implementation should be. In this case, its purpose is to define foldl' in terms of foldr. foldl can be defined in terms of foldr as
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
and that is, in fact, its implementation in base. Unless I’m much mistaken, foldl' can be implemented as
foldl' f z t = appStrictEndo (getDual (foldMap (Dual . StrictEndo . flip f) t)) z
Regarding the other candidates, I’m not sure StrictEndo' is particularly useful, because runStrictEndo' s x is just appEndo s $! x. You can get its behaviour just from Endo.
By contrast, I don’t think EDIT: This was nonsense.StrictEndo'' does anything at all. The field of a newtype is already strict. But even if it was a data type and not a newtype, you could recover its behaviour from Endo by using Endo $! f in place of StrictEndo'' f.
Ah I see that sounds right to me as well, though I haven’t looked at it in detail.
FWIW StrictEndo and StrictEndo'' will differ in cases such as:
evaluate $ (StrictEndo'' (const [])) <> (StrictEndo'' undefined)
Stuff like this is admittedly niche though, but might have space usage implications when using StrictEndo'' as a builder.
But yeah you can enforce a lot of these things manually by using seq, etc manually.
Sorry, I made a couple of typos/thinkos in my final paragraph and I’ve just corrected them. What I meant to say was that StrictEndo'' doesn’t differ from Endo.
No worries. I think the example I gave should differentiate between Endo and StrictEndo'' too.
Here’s a GHCi log:
GHCi, version 9.8.1: https://www.haskell.org/ghc/ :? for help
ghci> newtype StrictEndo'' a = StrictEndo'' (a -> a)
ghci> instance Semigroup (StrictEndo'' a) where (StrictEndo'' !f) <> (StrictEndo'' !g) = StrictEndo'' (f . g)
ghci> import Data.Monoid
ghci> import Control.Exception
ghci> evaluate $ (StrictEndo'' (const [])) <> (StrictEndo'' undefined)
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
undefined, called at <interactive>:6:55 in interactive:Ghci5
ghci> evaluate $ (Endo (const [])) <> (Endo undefined)
ghci>
ghci> evaluate $ (Endo $! (const [])) <> (Endo $! undefined)
ghci>
Ah yes, thanks. I got confused about what it means to bang a field of a newtype pattern match.