# Is there a strict `Endo`?

`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`”.)

2 Likes

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.

2 Likes

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 `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`. EDIT: This was nonsense.

1 Like

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.

1 Like

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>
``````
1 Like

Ah yes, thanks. I got confused about what it means to bang a field of a `newtype` pattern match.

1 Like

Interestingly `lens` uses `Endo (Endo s)` rather than `Dual (StrictEndo s)`: Control.Lens.Combinators