My grand purely-functional web application architecture project continues, and today I’d like to talk about a dictionary webapp. It’s very simple, having only two types of inputs, one of which creates words and one of which creates definitions.

type Word = String
type Definition = String
data Input = NewWord Word | NewDefinition Word Definition

The system state is a list of words, where each word is accompanied by a list of definitions (using some unsurprising helper functions, defined at the bottom of this post):

state :: [Input] -> [(Word, [Definition])]
state inputs = map word (filter isNewWord inputs)
  where word w = (w, definitions w)
        definitions w = definitionsFor w inputs
definitionsFor w = (map definitonFrom) .
                     (filter $ (==w) . wordFrom) .
                     (filter isNewDefinition)

That is, for each word-creating input, make a word entry. Gather all of the relevant definition entries into that word entry.

And from this I want to produce an implementation that does the minimum necessary to update the state when the inputs change. For an implementation to be practical, a NewDefinition input for a word should only impact on values that are directly related to that word. From that perspective, our state function is trouble. In particular, that list of (Word, [Definition]) is trouble.

Here’s why: The simplest thing that I can think of to produce a state-updating version of the function is to use a nice simple top-down algorithm. So from a regular map function,

map f [] = []
map f (x:xs) = (f x):(map f xs)

We produce something like this (where f’ is a state-updating version of f):

map' f' [] = []
map' f' (x:xs) = (f' x):(map' f' xs)

This implementation has an unpleasant implication. For any (f x) to change, every value in the initial x:xs has to be looked at. This is bad news from a practical-implementation point of view, because it means that adding a definition for word w actually has to touch the list elements for all of the words created prior to (or after, which one it is doesn’t matter all that much) w. It is quite possible to make an implementation like this that actually works [1], if you are not worried about the inevitable failure to scale.

At the same time, this bad news is no news at all, since immutable-everything value semantics demand that changing a value within a list also changes all of the lists that contain that value. That is, if we have a list (1:(2:(3:[]))), an update to 3 can only be made by making an update to the cons cell with value 2, and that update in turn can only be made by making an update to the cons cell with value 1. Those are the rules of the game.

Changing the Game

Why do implementations of the map-reduce framework not have this problem? After all, they are all about having a huge pile of input and generating some number – possibly a similarly huge pile – of outputs. How do the inputs find their way into the relevant outputs? When we say map-reduce, we are omitting the middle step, that of shuffling. The result of the computation is not `reduce (map input)’ but rather `reduce (shuffle (map input))’. The Map stage produces a pile of (key, value) pairs, the shuffle stage arranges those by key so you have a pile of (key, [value]) pairs, then each of those (key, [value]) pairs is reduced. The shuffle stage is all about sending values off to where they will have an effect. So inspired, we can introduce a function shuffle:

shuffle :: (Ord k) -> [a] -> (a -> k) -> ([a] -> v) -> Map k v
-- the type signature kind of says it all for me, but 
-- here's an implementation anyway
shuffle is fk fv = foldr (\i m -> addAtKey i (fk i) m) Map.empty is
  where addAtKey i = Map.alter (Just . maybe [i] (i:))

That is, for some collection of things `[a]’ we have a function that says which bucket they should go in, and a function that says how to produce a value from the members of a bucket, and from all those things we produce a map of buckets to values. This idea is so simple and so obvious that it took me a month to think of it.

The point of all that is of course that we can implement shuffle’:

shuffle' (\is -> i:is) fk fv fv' = Map.alter f (fk i) v
  where f Nothing = Just $ fv [i]
        f (Just v) = Just $ fv' (\is -> i:is) v

So when we have an as-yet empty bucket (the `f Nothing’) case we just compute fv on the single element. When we have a bucket with something in it, we compute the effect of the bucket input’s change on the bucket’s output, apply that change to the bucket’s output, and just like that your uncle’s name is Robert. Probably. This is implementable too, and we can rework our dictionary app to use it quite readily:

definitions inputs = Map.mapWithKey definitionsFromInputsFor
                                    (shuffle wordFrom inputs)
  where definitionsFromInputsFor w inputs
            = map definitionFrom (definitionInputsFor w inputs)

We have lost something on the way, though. At the start of this post, we could write any function we liked to express our program’s state. Now, the set of functions we can write to do that is severely curtailed. On the other hand, they are efficiently implementable[2]. Will that severe curtailment turn out to be a problem?

It raises another question. Is `shuffle’ actually giving us much, or is the win coming from some special privileges being given to the Map data structure? Maybe representing system state as a list is just a stupid thing to do (exhibit A, the vastly simpler shuffleized implementation).

On both of these questions, further work (as the academics like to say) is required.

---

Oh, right. Here’s those unsurprising helpers I was talking about. They’re, like, totes boredom:

isNewWord (NewWord _) = True
isNewWord _ = False
isNewDefinition (NewDefinition _ _) = True
isNewDefinition _ = False
wordFrom (NewWord w) = w
wordFrom (NewDefinition w _) = w
definitionFrom (NewDefinition _ d) = d
definitionFrom _ = undefined

[1] Beware, the README is something of an unreliable narrator.
[2] Unverified claim.[3]
[3] STFU.

• Uncategorized