Having based the core of HStringTemplate on Monoids, I started looking for other places to apply them in my code. A natural choice was a string template group. Conceptually, I wanted a very open API — a group is anything you can query for a specific template, be it a data structure, or a wrapper for an unsafe function that accesses a directory, or something that makes a StringTemplate on the fly even. But how do we compose these? I.e., we have two groups, and wish to implement “inheritance” such that one group is queried and if the query fails, then we check for the “higher” group. And most importantly, how do we build this such that any combination of different types of groups can be composed with any other? The first obvious thing to do is to use types to whittle everything down to a basic interface.
From an OO mindset, we would tend to, thinking of an “interface,” use a typeclass with a query function: class Group where query :: Group -> String -> Maybe StringTemplate. But oy vey! Now we need a function addGroups :: (Group x, Group y) => x -> y -> ???. Well, to a new concrete group type, I suppose. data ComposedGroup x y => ComposedGroup x y. And: instance (Group x, Group y) -> Group (ComposedGroup x y) where query s = case query x s of Just a -> Just a; Nothing -> query y s. Well, this is fine, if a bit bulky. But compose a few groups and a few more and we can see that even if we don’t have to interact with them, the type signatures will be pretty huge. We could avoid this with existential types, but it hardly seems like that improves the elegance of our solution.
There’s a useful insight, however, that I’ve been able to apply at least 50% of the time that I’ve been tempted to reach for existentials — for all practical purposes, a single function typeclass is equivalent to a lambda expression. In fact, all you’re doing when you make such a substitution is rendering the dictionary passing explicit. So switching over to type STGroup = String -> (Maybe StringTemplate) we see immediate benefits. First, this directly represents what a group is — not even a newtype constructor to get in the way. Second, we can write addGroups x y s = case query x s of Just a -> Just a; Nothing -> query y s directly, without all the typeclass machinery getting in our way.
Ok, where I’m going with this should be howling obvious by now. We have a bunch of things which have an append operation that is associative, and an obvious zero (const Nothing) — we have a monoid! There’s actually a slight catch here — we have two monoids, depending on whether the append operation favors the left or right value passed in. And hence, the Data.Monoid library wraps Maybe as newtype First a = First { getFirst :: Maybe a }, and Last which gives you the last Just value instead of the first. (Side not here: I’d much prefer First was simply the default Monoid instance for Maybe, as Last is its dual [i.e. the same thing with the arguments to mappend reversed], and you as you can wrap any monoid in Dual to get its Dual for free.)
So now we have STGroup = String -> (First StringTemplate). And thanks to our old friend the reader monoid [instance Monoid b => Monoid (a -> b)], we again get the function we really wanted for free: addGroups becomes mappend!
Another side note: First and Last, absurdly don’t come with built-in functor instances, even though as wrappers for Maybe, the functor instance is obvious: instance Functor First where fmap f x = First . fmap f . getFirst $ x
Now we can “drill down” directly into our group, also for free. So say we have, and we do, a function optInsertTmpl that sets options (as a list of string pairs) for a single template. Now, let’s define a helper function () x y = (fmap . fmap) x y. [This function should be in everyone’s standard libs by the way. As a generalization from the “owl” which composes a function with two arguments into a function with one argument: o :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c; o = (.).(.), I end up using it all the time.] The reader monad (i.e. (String ->) ) is a functor. We’ve just defined First as a functor. So we can simply write:
optInsertGroup :: [(String, String)] -> Group -> Group optInsertGroup opts f = optInsertTmpl opts <$$> f
We can think of this as “reaching in” two levels deep (past the reader, past the first) and operating directly on every single possible template our group can generate, at once.
Different context than the last example, same conclusion: Get the types and classes right, and the rest of the code almost seems to melt away.
fmap fix return 
Max said
“Get the types and classes right, and the rest of the code almost seems to melt away.”
Amen, brother! :-). I’m constantly surprised at how often constructs from abstract algebra crop up during day to day programming tasks, as long as you look at those. tasks in the right way.
Thanks for the great post!
Justin said
I’m missing how STGroups lets you get away from the typeclass (or makes it simpler) in the third paragraph. Can you expand on how that type alias makes addGroups simpler and/or lets you write fewer Group instances?
sclv said
You don’t need the type alias at all, actually. That’s just a notational convenience. And you don’t need a typeclass either, and hence no instances.
What you do instead is write functions like the following, which takes an associative list of names and templates and produces a group such that they are able to call one another.
groupStringTemplates :: [(String,StringTemplate)] -> STGroup
groupStringTemplates xs = newGen
where newGen s = First (M.lookup s ng)
ng = M.fromList $ map (second $ sgInsert newGen) xs
You’ll notice I’m using a little circular programming hack here too, to set the group of each template as the new group we’re creating, even as we’re still creating the group. It makes the code a little more obscure than necessary, and looking back at it I’m not sure if its actually better or just cuter. Removing the setting of group context entirely, to keep things simple, we get something like (off the top of my head):
groupStringTemplates :: [(String, StringTemplate)] -> STGroupgroupStringTemplates xs = \s -> s = First (M.lookup s myNewMap)
where myNewMap = M.fromList xs
myNewMap is floated into a where clause so that it only gets evaluated once. We just return the function that wraps the results of its lookup into a First. That’s all there is to it — just return functions directly. addGroups doesn’t need to be written at all. no type instances need to be written at all (well, except for the Functor instance for First, but that’s something that really should be in the standard libs and just isn’t). To add groups g1 and g2 we just write g1 `mappend` g2. It’s hard to see in a way, because thanks to the predefined instances for monoids, everything else comes for free. If someone wants to write a “group” that takes a string and reverses it and then interprets it as perl and returns a StringTemplate built from the result, they just write a function to do just that, and stick First . Just in front of its result. No data declarations, no type declarations, no instances. That function they just wrote is already of the Group type, and for free it can be composed with any other groups of any other sort.
EDIT: Oh, and if you’re asking about what we get with the type before we switch from Maybe to First, the answer above still mainly applies, except we need to write addGroups by hand. However, without the ADTs and typeclasses, we still get away with not needing to write a product type for its result, and we still get away with not needing to write any instance declarations, and we still get away with not needing to write some sort of existential wrapper to avoid an exponential blowup in type signatures or to have multiple groups in a list, etc., and also the need for any class contexts on any functions taking groups as arguments, and suchforth.