Conal Elliott

The post Semantic editor combinators gave an example of a pattern that comes up a lot for me in Haskell programming. I want to apply functions inside of a newtype without cumbersome unwrapping and wrapping of the representation insides.

While chatting with Daniel Peebles in #haskell today, the realization hit me that these “higher-order wrappers” can not only make other code pretty, but can themselves be expressed more beautifully and clearly, using two of the combinators given in that post.

The example I gave was type composition, taken from the TypeCompose library:

newtype (g :. f) a = O { unO :: g (f a) }

The convenient higher-order wrappers apply n-ary function within O constructors:

inO  h (O gfa) = O (h gfa)
inO2 h (O gfa) (O gfa') = O (h gfa gfa')
...

Then I get to implement Functor and Applicative instances in the style of semantic editor combinators.

instance (Functor g, Functor f) => Functor (g :. f) where
  fmap  = inO . fmap . fmap
 
instance (Applicative g, Applicative f) => Applicative (g :. f) where
  pure  = O . pure . pure
  (<*>) = (inO2 . liftA2) (<*>)

The point-free definitions I gave before are pretty cryptic if you’re not used to the style:

inO  = (  O  .) . (. unO)
inO2 = (inO  .) . (. unO)
inO3 = (inO2 .) . (. unO)
...

What dawned on me today is that I can instead say what I mean plainly: inO applies unO to the argument and O to the result.

inO  = result   O  . argument unO

Similarly, inO2 applies unO to the (first) argument and inO to the resulting function. Similarly for inO3:

inO2 = result inO  . argument unO
inO3 = result inO2 . argument unO
...

The unwrapping and wrapping don’t interact, so, we can write equivalent definitions, swapping the compositions:

inO2 = argument unO  . result inO

Equivalence follows from associativity of function composition.