## Semantic editor combinators

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:

• thinking of function composition as binary instead of unary, and
• seeing the functions `first` and `second` as about arrows, and therefore esoteric.

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:

• 2008-11-29: added type of `v6` example. Tweaked `inO2` alignment.

### 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

• negate the boolean,
• double the Int,
• swap the inner pair, or
• swap the outer pair.

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

• Read out the path in the type of the value being edited (`v0` here), from the outside to the part to edit, naming each step, according to part of the type being entered, using the names “first” and “second” for pairs, and “result” for functions.
• Write down that path as its part names, separated by periods. If the path has at least two components, surrounded by parentheses.
• Next write the alteration function to be applied.
• Finally, the value being edited.

In our string-reversal example, these steps look like

• `(second.result.first)`second of the pair, result of that function, and first of that pair
• `reverse`
• `v0`

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

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

• Type representations
• Code
• Graphical user interfaces
• Combinations of all of the above (including values)

1. #### bluestorm:

It seems that all your functions are map, and that you don’t really use the Arrow part (wich makes sense, as “map” in a functor is really like editing a part of it) :

```Prelude> let v0 = (3, \ c -> (['r',c,'q',c], c == '0'))
Prelude> snd v0 '0'
("r0q0",True)
Prelude Control.Monad.Instances> let v1 = (fmap.fmap.fmap) not v0
Prelude Control.Monad.Instances> snd v1 '0'
("r0q0",False)```
2. #### conal:

bluestorm:

Some of the examples above can be done with just `fmap`, though not all of them. If you try replacing all of the path components with `fmap`, you’ll soon see why.

There’s a deeper reason that `fmap` is inadequate for what I’m doing, which will become clear in my follow-up post. The type of `fmap` limits the editors being manipulated (by the editor combinators) to being functions. The `Arrow` framework generalizes from functions to arbitrary arrows, which gave me enough flexibility to handle the examples listed at the end of the post.

3. #### Conal Elliott » Blog Archive » Prettier functions for wrapping and wrapping:

[...] post Semantic editor combinators gave an example of a pattern that comes up a lot for me in Haskell programming. I want to apply [...]

4. #### Conal Elliott » Blog Archive » Sequences, segments, and signals:

[...] Or, in the style of Semantic editor combinators, [...]

5. #### Michael:

“Less pointedly …”

Hahahahahahaha! wipes tears away Too much…

6. #### Conal Elliott » Blog Archive » Trimming inputs in functional reactive programming:

[...] In the style of Semantic editor combinators, [...]

7. #### Conal Elliott » Blog Archive » Smarter termination for thread racing:

[...] Or, in the style of Semantic editor combinators, [...]

8. #### Martijn:

Can I also go into record fields with this?

9. #### conal:

@Martijn — Record fields are no problem. You can make functions analogous to `first` and `second` that operate on your structures, applying a given function to one field and carrying the other fields along, unchanged.

10. #### Conal Elliott » Blog Archive » Another angle on functional future values:

[...] These helpers make for some easy definitions in the style of Semantic editor combinators: [...]

11. #### Conal Elliott » Blog Archive » 3D rendering as functional reactive programming:

[...] or, with Semantic editor combinators: [...]

12. #### Less Sugar/More Meat » Blog Archive » Semantic Editor Combinators - one of my favorite blog posts:

[...] Semantic Editor Combinators – Conal Elliott [link] [...]

13. #### Frederick Ross:

Long, long after the fact, I’ll chime in with an odd observation. Your editor combinators in effect form a sort of groupoid (the “sort of” indicates that my brain is tired and uncertain rather than any mathematical fact). If we have a group with an action on a space, and we have a representation of this action of dimension equal to that of the space, and add a single point of the space as an origin (the point left untouched by the identity), then the group plus the point represent a coordinate system. Similarly, your editor combinators, given a root of a piece of structured data, represent a coordinate system on data.

And I wrote a version of these in Erlang. This demonstrates two points: my Erlang style is becoming peculiar, and I miss Haskell.

14. #### Conal Elliott » Blog Archive » Another angle on zippers:

[...] Semantic editor combinators for an explanation of (fmap.first) friends. Continuing, apply the definition of Der on [...]

15. #### Conal Elliott » Blog Archive » Memoizing polymorphic functions via unmemoization:

[...] to make it much easier. I’ve tinkered with making this process much more elegant by applying Semantic editor combinators in their generalized form (as in the paper Tangible Functional Programming), using bijections as [...]

16. #### Conal Elliott » Blog Archive » Adding numbers:

[...] Elliott » Blog Archive » Memoizing polymorphic functions via unmemoization on Semantic editor combinatorsConal Elliott » Blog Archive » Memoizing polymorphic functions via unmemoization on [...]