### A pattern for increasing sharing

#### by Edward Z. Yang

I recently encountered the following pattern while writing some Haskell code, and was surprised to find there was not really any support for it in the standard libraries. I don’t know what it’s called (neither did Simon Peyton-Jones, when I mentioned it to him), so if someone does know, please shout out. The pattern is this: many times an endomorphic map (the map function is `a -> a`) will not make very many changes to the underlying data structure. If we implement the map straight-forwardly, we will have to reconstruct the entire spine of the recursive data structure. However, if we use instead the function `a -> Maybe a`, we can reuse old pieces of the map if there were no changes to it. (Regular readers of my blog may recognize this situation from this post.) So what is such an alternative map `(a -> Maybe a) -> f a -> Maybe (f a)` called?

One guess it might be the `traverse` function in Data.Traversable: it certainly has a very similar type signature: `Applicative f => (a -> f b) -> t a -> f (t b)`. However, the semantics are subtly different, as you can see from this example:

Data.Traversable> traverse (\x -> if x == 2 then Just 3 else Nothing) [1,2,3] Nothing

Recall that our function only returns `Nothing` in the event of no change. Thus, we *should* have gotten the result `Just [1,3,3]`: the first and third elements of the list unchanged, and the second element of the list with its new value.

How would we implement such a function for lists? Here’s a simple implementation:

nonSharingMap :: (a -> Maybe a) -> [a] -> Maybe [a] nonSharingMap f xs = let (b, r) = foldr g (False, []) (zip xs (map f xs)) in if b then Just r else Nothing where g (y, Nothing) (b, ys) = (b, y:ys) g (_, Just y) (_, ys) = (True, y:ys)

But we can do better than this. Consider a situation where all elements of the list except the head stay the same:

We would like to share the tail of the list between the old and new versions. With a little head-scratching, and the realization that `tails` shares, we can write this version:

sharingMap :: (a -> Maybe a) -> [a] -> Maybe [a] sharingMap f xs = let (b, r) = foldr g (False, []) (zip3 (tails xs) xs (map f xs)) in if b then Just r else Nothing where g (_, y, Nothing) (True, ys) = (True, y:ys) g (_, _, Just y) (True, ys) = (True, y:ys) g (ys', _, Nothing) (False, _) = (False, ys') g (_, _, Just y) (False, ys) = (True, y:ys)

Open questions: what is this pattern called? Why doesn’t it follow the usual applicative structure? Does it fulfill some higher order pattern? Also, this scheme isn’t fully compositional: if I pass you a `Nothing`, you have no access to the original version in case there was a change elsewhere in the structure: `(Bool, a)` might be a little more compositional. Does this mean this is an example of the state monad? What about sharing?

*Update.* Anders Kaseorg writes in with a much more straight-forward, directly recursive version of the function:

sharingMap f [] = Nothing sharingMap f (x : xs) = case (f x, sharingMap f xs) of (Nothing, Nothing) -> Nothing (y, ys) -> Just (fromMaybe x y : fromMaybe xs ys)

I haven't checked, but one hope of expressing the function in terms of `foldr` and `zip3` is that one may be able to get it to fuse. Of course, for actual recursive spine-strict data types, you usually won't be able to fuse, and so a more straightforward presentation is more normal.

Did you enjoy this post? Please subscribe to my feed!

Another instance (“to preserve sharing and save memory”)

Doesn’t CL already do this since ages?

Anonymous: What do you mean by “this”?

I think I’ve seen a function like this called “update” before, but I can’t remember where. At least it does sound like a good name.

This is also a widely known folklore trick in the ML communities. In OCaml there is an (ugly) (==) : ‘a -> ‘a -> bool operator that is not the usual (=) comparison but test for “physical equality” (pointer equality) instead, and allow to reason about sharing in the code. Below is an example which is not the most efficient (it keeps testing for == after the test failed once) but illustrates the use:

“==” is very bad from a semantics point of view : it forces you to reason about pointer identity, and may break encapsulation of existential types. Using Maybe here is cleaner, however the code logic (which does reason about sharing) stays the same.

I have found an example using this technique in the (otherwise not-really-related) paper “Multi-Return Function Calls” by Olin Shivers and David Fisher (2004). They talk about a “parsimonious filter function” that preserves sharing on the longest suffix of elements all retained. They use the novel control-flow structure presented in their paper, but for your purposes it is equivalent to using Maybe (it’s “1 + a” as structured control-flow rather than data). Maybe “parsimonious” is a good name for this idea?

I just uploaded a new package Transhare to hackage. It is my abstracted solution to the sharing pattern for (a -> Maybe a) transformers, inspired by your post. I doubt the formatting will survive in this comment, but the list and tree instances are modified uses of applicative:

[1] http://hackage.haskell.org/package/Transhare-0.9

Another thing these Maybe returns are good for is fixed points,

This is the same semantics as you use: Nothing means that the output is the same as the input.

Now for some combinators:

I don’t really like this, there are too many parameters. An alternative is to also return the value if it is the same, since you might need it later on:

The problem is that here you could lie about being the same, or you could forget to check. But the latter only matters for sharing. You can even convert between the two forms,

But I don’t think this buys you anything compared to just sticking with Change.

Twan van Laarhove: your post is substantially identical to the Transhare [1] I just uploaded last night. The names are slightly different, and I went slightly further and defined a class Transhare to lift (a -> Maybe a) or (a -> Change a) to containers.

[1] http://hackage.haskell.org/packages/archive/Transhare/0.9/doc/html/Data-Transhare.html