ezyang’s blog

the arc of software bends towards understanding

A pattern for increasing sharing

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]

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.

8 Responses to “A pattern for increasing sharing”

  1. Chung-chieh Shan says:

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

  2. Anonymous says:

    Doesn’t CL already do this since ages?

  3. Anonymous: What do you mean by “this”?

  4. Quentin Moser says:

    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.

  5. gasche says:

    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:

    let rec map f li =
      match li with
        | [] -> li
        | x::xs ->
          let x' = f x in
          let xs' = map f xs in
          if x == x' && xs == xs' then li
          else x' :: xs'

    “==” 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?

  6. Chris Kuklewicz says:

    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:

        instance Transhare [] where
            transR t = let tL x@((:) v vs) = fromO x $ (:)  t v  transR t vs
                             tL x = Original x
                       in tL
        instance Transhare Tree where
            transR t = \ a@(Node value children) -> fromO a $ Node  t value  transR (transR t) children

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

  7. Twan van Laarhoven says:

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

        fix :: (a -> Maybe a) -> a -> a
        fix f x = case f x of
          Nothing -> x
          Just x' -> f x'

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

    Now for some combinators:

        same :: Maybe a
        mapSame :: (a -> b) -> (a -> Maybe a) -> a -> Maybe b
        mapSame2 :: (a -> b -> c) -> (a -> Maybe a) -> a -> (b -> Maybe b) -> b -> Maybe c
        sharingMap f [] = same
        sharingMap f (x : xs) = mapSame2 (:) f x (sharingMap f) xs

    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:

        data Change a = Same a | Change a
        instance Applicative Change where {
            pure = Same -- ??
            Same f  Same x = Same (f x)
            Change f  Same x = Change (f x)
            -- etc, you get the point
        ifSame :: a -> Change a -> Change a
        ifSame x (Same _) = Same x
        ifSame _ change = change
        sharingMap f [] = Same []
        sharingMap f xxs@(x:xs) = ifSame xxs $ (:)  f x  sharingMap f xs

    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,

        ($?) :: (a -> Maybe a) -> (a -> Change a)
        change :: Change a -> Maybe a
        sharingMap f [] = Nothing
        sharingMap f xxs@(x:xs) = change $ (:)  f $? x  sharingMap f $? xs

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

  8. Chris Kuklewicz says:

    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

Leave a Comment