Conal Elliott » Semantic editor combinators (original) (raw)

While working on Eros, I encountered a function programming pattern I hadn’t known. I was struck by the simplicity and power of this pattern, and I wondered why I hadn’t run into it before. I call this idea “semantic editor combinators”, because it’s a composable way to create transformations on rich values. I’m writing this post in order to share this simple idea, which is perhaps “almost obvious”, but not quite, due to two interfering habits:

What I enjoy most about these (semantic) editor combinators is that their use is type-directed and so doesn’t require much imagination. When I have the type of a complex value, and I want to edit some piece buried inside, I just read off the path in the containing type, on the way to the buried value.

I started writing this post last year and put it aside. Recent threads on the Reactive mailing list (including a dandy explanation by Peter Verswyvelen) and on David Sankel’s blog reminded me of my unfinished post, so I picked it up again.

Edits:

Example

Suppose we have a value defined as follows.

v0 :: (Int, Char -> (String,Bool))
v0 = (3,  c -> ([c,'q',c,'r'], isDigit c))

Now, how can one edit this value? By “edit”, I simply mean to produce a value that resembles v0 but has alterations made.

For concreteness, let’s say I want to reverse the string. A programmer might answer by firing up vim, Emacs, or yi (whee!), and change the definition to

v0 = (3,  c -> (['r',c,'q',c], isDigit c))

But this answer doesn’t really fit the question, which was to edit the value. I want a way to edit the semantics, not the syntax, i.e., the value rather than the expression.

Similarly, I might want to

Semantic editor combinators makes these tasks easy, using the following recipe, writing from left to right:

In our string-reversal example, these steps look like

So the value editing is accomplished by

v1 = (second.result.first) reverse v0

Let’s see if the editing worked. First, inspect v0, using GHCi:

> fst v0
3
> (snd v0) 'z'
("zqzr",False)

and then v1:

> :ty v1
v1 :: (Int, Char -> (String, Bool))
> fst v1
3
> (snd v1) 'z'
("rzqz",False)

The other four editings listed above are just as easy

double x   = x+x
swap (x,y) = (y,x)

-- negate the boolean,
v2 = (second.result.second) not v0

-- double the Int,
v3 = first double v0

-- swap the inner pair, or
v4 = (second.result) swap v0

-- swap the outer pair
v5 = swap v0

Testing in GHCi:

> :ty v2
v2 :: (Int, Char -> (String, Bool))
> fst v2
3
> (snd v2) 'z'
("zqzr",True)

> :ty v3
v3 :: (Int, Char -> (String, Bool))
> fst v3
6
> (snd v3) 'z'
("zqzr",False)

> :ty v4
v4 :: (Int, Char -> (Bool, String))
> fst v4
3
> (snd v4) 'z'
(False,"zqzr")

> :ty v5
v5 :: (Char -> (String, Bool), Int)
> fst v5
<interactive>:1:0: No instance for (Show (Char -> (String, Bool))) ...
> snd v5
3
> fst v5 'z'
("zqzr",False)

Since String is a synonym for [Char], the type of v0 has even more structure we can delve into:

v0 :: (Int, Char -> ([Char],Bool))

Add a fourth path component, element, for entering elements of lists. Now we can edit the characters:

-- previous character
v6 = (second.result.first.element) pred v0

-- character value
v7 = (second.result.first.element) ord v0

Testing:

> :ty v6
v6 :: (Int, Char -> ([Char], Bool))
> fst v6
3
> (snd v6) 'z'
("ypyq",False)

> :ty v7
v7 :: (Int, Char -> ([Int], Bool))
> fst v7
3
> (snd v7) 'z'
([122,113,122,114],False)

What’s going on here?

You may be familiar with the functions first and second. They’re methods on the Arrow class, so they’re pretty general. When operating on functions, they have the following types and definitions:

first  :: (a -> a') -> ((a,b) -> (a',b))
second :: (b -> b') -> ((a,b) -> (a,b'))

first  f =  (a,b) -> (f a, b)
second g =  (a,b) -> (a, g b)

Note that, as needed, first and second apply given functions to part of a pair value, carrying along the other half of the pair.

When working syntactically, we often apply functions under lambdas. The corresponding value-level, embedding combinator is just function composition. I’ll use the name result as a synonym for (.), for consistency with first and second and, more importantly, for later generalization.

result :: (b -> b') -> ((a -> b) -> (a -> b'))
result =  (.)

As with first and second, I’ve used parentheses in the type signatures to emphasize the path components as being unary, not binary. It’s this unusual unary view that makes first, second, and result (or (.)) composable and guides us toward composable generalizations.

Similarly, the element component is synonym for fmap:

element :: (a -> b) -> ([a] -> [b])
element = fmap

However, using fmap directly is very useful, since it encompasses all Functor types. Since functions from any given type is a functor, I often use fmap in place of result, just to avoid having to define result. Thanks to the Functor instance of pairing, we can also use fmap in place second. (The two, however, are not quite the same.) An advantage of names like result, element and second is that they’re more specifically descriptive. Hence they are easier for people to read, and they lead to more helpful error messages.

Found in the wild

The examples above are toys I contrived to give you the basic idea. Now I’d like to show you how very useful this technique can be in practice.

Reactive represents events via two types, Future and Reactive:

newtype EventG t a = Event (FutureG t (ReactiveG t a))

The Functor instance uses the functor instances of FutureG and ReactiveG:

instance Functor (EventG t) where fmap = inEvent.fmap.fmap

The inEvent functional is also a semantic editor combinator, though not so obvious from the types. It applies a given function inside the representation of an event.

One pattern I use quite a lot is applying a function to the result of a curried-style multi-argument function. For instance, Reactive has a countE function to count event occurrences. Each occurrence value get paired with the number of occurrences so far.

countE :: Num n => Event b -> Event (b,n)
countE = stateE 0 (+1)

Quite often, I use a forgetful form, countE_, which discards the original values. Looking at the type of countE, I know to direct snd into the result and then into the values of the event. The definition follows robomatically from the type.

countE_ :: Num n => Event b -> Event n
countE_ = (result.fmap) snd countE

You can play this game with any number of arguments. For instance, Reactive has a function for snaphotting behaviors on each occurrence of an event, taking an initial state, state transition function, and an input event.

snapshot :: Event a -> Reactive b -> Event (a,b)

The forgetful version descends into two results and one event, to edit the pair found there:

snapshot_ :: Event a -> Reactive b -> Event b
snapshot_ = (result.result.fmap) snd snapshot

I could have written the following pointful version instead:

snapshot_ e b = fmap snd (snapshot e b)

As a more varied example, consider these two functions:

withRestE :: Event a -> Event (a, Event a)

firstE :: Event a -> a

The function withNextE directs firstE into the inner event of withRestE.

withNextE :: Event a -> Event (a,a)
withNextE = (result.fmap.second) firstE withRestE

Who’s missing?

We have first second to edit the first and second part of a pair. We also have result to edit result part of a function. We can also edit the argument part:

argument :: (a' -> a) -> ((a -> b) -> (a' -> b))

This editor combinator has a different flavor from the others, in that it is contravariant. (Note the primes.) Its definition is simple:

argument = flip (.)

Higher arity

The combinators above direct unary functions into single structures. A similar game works for n-ary functions, using the applicative functor lifters. For instance,

liftA2 :: (Applicative f) =>
          (a -> b -> c) -> (f a -> f b -> f c)

Since liftA2 promotes arbitrary binary functions to binary functions, it can be applied again & again.

*Main Control.Applicative> :ty liftA2.liftA2.liftA2
liftA2.liftA2.liftA2 ::
  (Applicative f, Applicative g , Applicative h) =>
  (a -> b -> c) -> f (g (h a)) -> f (g (h b)) -> f (g (h c))

Similarly for liftA3 etc.

Now an in-the-wild higher-arity example, taken from the TypeCompose library.

Here’s a very handy way to compose two type constructors:

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

We can apply n-ary function within O constructors:

inO :: (g (f a) -> g' (f' a')) -> ((g :. f) a -> (g' :. f') a')
inO h (O gfa) = O (h gfa)

inO2 :: ( g (f a)   ->  g' (f' a')   ->  g'' (f'' a''))
     -> ((g :. f) a -> (g' :. f') a' -> (g'' :. f'') a'')
inO2 h (O gfa) (O gfa') = O (h gfa gfa')

...

Less pointedly,

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

Functors compose into functors, and applicatives compose into applicatives. (See Applicative Programming with Effects.) The semantic-editor-combinator programming style makes these for very simple instance definitions:

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) (<*>)

What’s ahead?

Two of our semantic editor combinators (path components) have more general types than we’ve used so far:

first  :: Arrow (~>) => (a ~> a') -> ((a,b) ~> (a',b))
second :: Arrow (~>) => (b ~> b') -> ((a,b) ~> (a,b'))

I’ve simply replaced some of the (->)‘s in the function-specific types with an arbitrary arrow type (~>).

Another post will similarly generalize result and then will give some nifty uses of this generalization for applying combinator-based semantic editing beyond simple values to

While working on Eros, I encountered a function programming pattern I hadn’t known. I was struck by the simplicity and power of this pattern, and I wondered why I hadn’t...