## Composing memo tries

The post *Elegant memoization with functional memo tries* showed a simple type of search tries and their use for functional memoization of functions.
This post provides some composition tools for memo tries, whose definitions are *inevitable*, in that they are determined by the principle presented in *Simplifying semantics with type class morphisms*.

### Compositional semantics and type class morphisms

The discipline of denotational semantics defines meaning functions *compositionally*, i.e., the meaning of a construct must be some function of the meanings of its components.

Type class morphisms make the denotational discipline even more specific:

The meaning of each method corresponds to the same method for the meaning.

For instance,

```
meaning (a `mappend` b) == meaning a `mappend` meaning b
```

### Memo tries, semantics, and morphisms

The semantic function for a memo trie is `untrie`

, which converts a trie (back) to a function:

```
untrie :: (a :->: b) -> (a -> b)
```

Let’s look at the consequences of requiring that `untrie`

be a morphism over `Monoid`

, `Functor`

, `Applicative`

, `Monad`

, `Category`

, and `Arrow`

, i.e.,

```
untrie mempty == mempty
untrie (s `mappend` t) == untrie s `mappend` untrie t
untrie (fmap f t) == fmap f (untrie t)
untrie (pure a) == pure a
untrie (tf <*> tx) == untrie tf <*> untrie tx
untrie (return a) == return a
untrie (u >>= k) == untrie u >>= untrie . k
untrie id == id
untrie (s . t) == untrie s . untrie t
untrie (arr f) == arr f
untrie (first t) == first (untrie t)
```

These morphism properties imply that all of the expected laws hold, assuming that we interpret equality semantically (or observationally). For instance,

```
untrie (mempty `mappend` a)
== untrie mempty `mappend` untrie a
== mempty `mappend` untrie a
== untrie a
untrie (fmap f (fmap g a))
== fmap f (untrie (fmap g a))
== fmap f (fmap g (untrie a))
== fmap (f.g) (untrie a)
== untrie (fmap (f.g) a)
```

### Deriving instances

The implementation instances follow from applying `trie`

to both sides of each of these morphism laws, using the property `trie . untrie == id`

.

```
instance (HasTrie a, Monoid b) => Monoid (a :->: b) where
mempty = trie mempty
s `mappend` t = trie (untrie s `mappend` untrie t)
instance HasTrie a => Functor ((:->:) a) where
fmap f t = trie (fmap f (untrie t))
instance HasTrie a => Applicative ((:->:) a) where
pure b = trie (pure b)
tf <*> tx = trie (untrie tf <*> untrie tx)
instance HasTrie a => Monad ((:->:) a) where
return a = trie (return a)
u >>= k = trie (untrie u >>= untrie . k)
instance Category (:->:) where
id = trie id
s . t = trie (untrie s . untrie t)
instance Arrow (:->:) where
arr f = trie (arr f)
first t = trie (first (untrie t))
```

Correctness of these instances follows by applying `untrie`

to each side of each definition and using the property `untrie . trie == id`

.

The `Category`

and `Arrow`

instances don’t quite work, however, because of necessary but disallowed `HasTrie`

constraints on the domain type.
John Hughes pointed out a similar problem near the end of *Generalising Monads to Arrows*, saying “I consider this to be a defect of the Haskell type system, which hopefully can be corrected in a future version of the language.”

## Conal Elliott » Blog Archive » Simpler, more efficient, functional linear maps:

[…] build up linear maps conveniently and efficiently by using the operations on memo tries shown in Composing memo tries. For instance, suppose that h is a linear function of two arguments (linear in both, not it each) […]

23 January 2009, 9:56 pm