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

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

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

16 Comments

  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> :m Control.Monad.Instances
    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 [...]

Leave a comment