Semantic editor combinators

[masaeedu]

Conal Elliott has a pretty cool article on how just fmap and (generalized) flip are sufficient for doing complex transformations of functions of values of functions of ..., etc, simply by virtue of how many things are naturally functors of differing variance.

As an example, let's look at the signature for a foldl:

Prelude Data.Functor> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Let's say for whatever reason I wanted a slightly different foldl' that adds 2 to all of the as in that b -> a -> b expression, or something arbitrary like that.

Now I could sit down and start expending some mental effort to actually work out a transformation, but I could also just use Conal's totally mechanized, no-brain required approach. Given the original foldl, I want to take the argument's return's argument, and apply +2 to it. How do I express this with semantic editor combinators?

Prelude Data.Functor> arg = flip fmap
Prelude Data.Functor> ret = fmap
Prelude Data.Functor> foldl' = (arg . ret . arg) (+ 2) foldl
Prelude Data.Functor> foldl (+) 0 [1, 2, 3, 4]
10
Prelude Data.Functor> foldl' (+) 0 [1, 2, 3, 4]
18

I think a language of similar "semantic combinators" comprised of meaningful aliases could be useful in Sanctuary as well. The problem is that we don't have the convenient infix (.) operator, so our applications of S.map have to be on the left hand side. This makes things not nearly as convenient. I was hoping someone would be able to figure out an equivalent encoding in Sanctuary that is just as readable.

[masaeedu]

Another interesting example, motivated by recent discussion in the Gitter:

foldMap' f = ((arg . ret . arg) f foldl) mappend mempty

i.e. we can make a foldMap by simply editing foldl and applying the (Monoid a) => x -> a transformation to the second argument in the reducer, then applying away the reducer and seed with mappend and mempty.

[davidchambers]

This is new to me, but I can at least provide the Sanctuary translation of the Haskell code:

const arg = S.flip (S.map);
const ret = S.map;
const reduce$ = S.pipe ([arg, ret, arg]) (S.add (2)) (S.reduce);

S.reduce (S.add) (0) ([1, 2, 3, 4]);  // => 10
reduce$ (S.add) (0) ([1, 2, 3, 4]);  // => 18