Domain Modelling with Haskell: Factoring Out Recursion
In the final part of the “Domain Modelling with Haskell” series we factor out recursion from the Project data type, and use Fixplate to traverse the tree and accumulate reports. Although a highly flexible and powerful technique, it should not be employed prematurely due to its more advanced nature.
Welcome to Haskell at Work, a screencast focused on practical Haskell programming. You’re watching the fourth and final part of Domain Modelling with Haskell.
In the last video, we used explicit recursion and the WriterT monad transformer to accumulate reports on all project levels. We had to add new slots to the
Project data structure to add the additional reporting information. In a way, we have a strange coupling going on, where the
Project module knows how the
Reporting module extends the data structure.
If you only have a couple of these cases in your project, I think you should keep it that way. On the other hand, if you do a lot of transformation and processing based on a core data structure, like our
Project data type, you might want to make it even more generic. Let’s explore one way of doing that.
Factoring Out Recursion
Instead of factoring out specific slots in the
ProjectGroup data constructors, we will factor out the entire recursion of the data type. We will use a library called Fixplate, whose name is a combination of the term “fixed-point type,” and “Uniplate,” the name of a Haskell package for generic traversals and transformations.
To use Fixplate, and specifcally its fixed-point type, we need to factor out the recursion from our data type. We see that the
ProjectGroup constructor has a list of projects. We will not have that explicit recursion, and instead embed a field of type
f. This technique is also the basis for free monads. If you are interested, check out Gabrial Gonzalez blog post Why free monads matter.
data Project f = Project ProjectId Text | ProjectGroup Text [f] deriving (Show, Eq, Functor, Foldable, Traversable)
Note that we can have the
ProjectId in the
Project constructor again.
ProjectF, by convention, and define a type alias
data ProjectF f = ... type Project = Mu ProjectF
We also need to import
Mu and its
import Data.Generics.Fixplate.Base (Mu (Fix))
Mu is the fixed point type. We can have a look in the REPL:
$ stack repl *Project> import Data.Generics.Fixplate.Base *Project Data.Generics.Fixplate.Base> :t Fix Fix :: f (Mu f) -> Mu f
I’m not going to explain in great detail how this works in this quick screencast, so do have a look at Gonzalez’ blog post. But you can see that the
Fix constructor takes a functor
f, parameterized by the fixed point type
Mu itself, and returns a
Mu is responsible for recursively injecting
f itself, wrapped by the
Mu type at each level.
I know, this is a mind bender at first.
We create two helpers for constructing projects and project groups in the fixed-point type.
project :: ProjectId -> Text -> Project project p = Fix . Project p projectGroup :: Text -> [Project] -> Project projectGroup name = Fix . ProjectGroup name
Calculating and Accumulating Reports
Now here comes the first kicker. We want to annotate each level in the tree with the corresponding report. We can do that using Fixplate’s
Attr type (or attribute.) First, we import
fold and the
import Data.Foldable (fold) import Data.Generics.Fixplate.Base (Attr)
We define a type alias
type ProjectReport = Attr ProjectF Report
Then, we rewrite
calculateProjectReports to use a function called
import Data.Generics.Fixplate.Attributes (synthetiseM)
synthetiseM traverses our data structure bottom-up, and uses the function we supply to wrap and annotate each project level with a
Report. The function we supply,
calc, calculates a report for leaf projects. Given a project group, and it folds the underlying reports into a single one.
calculateProjectReports :: Project -> IO ProjectReport calculateProjectReports = synthetiseM calc where calc (Project p _) = calculateReport <$> DB.getBudget p <*> DB.getTransactions p calc (ProjectGroup _ reports) = pure (fold reports)
Notice how the second field of
ProjectGroup is a list of reports, the reports below the group that have already been calculated. This, and many other powerful transformations and traversals, are possible thanks to our data type having recursion factored out.
In the end, we get back the full tree, with it’s structure preserved, but with reports on all levels. Before we can try it out, we need to adapt the pretty printing code.
Pretty-Printing with Fixplate
Another big win is that because the recursion is factored out, Fixplate can take care of building the pretty-printable tree for us.
import Data.Generics.Fixplate.Base (Ann (Ann))
All we need to do is to tell it how to print project nodes.
prettyResult is a function from a project annotated with a report, to a string. The
Ann constructor holds the project and the report. A single project is printed as its name, the project ID, and the report. A project group is printed as its name and its report.
prettyResult :: Ann ProjectF Report a -> String prettyResult (Ann report project') = case project' of Project (ProjectId p) name -> printf "%s (%d): %s" name p (prettyReport report) ProjectGroup name _ -> printf "%s: %s" name (prettyReport report)
The project group children are values of the
Hole type, which is used to mark the absence of something to print. Remember, we don’t have to do recursion explicitly.
Trying It Out
We need to change our
Demo data as well. First, we import the
Draw module from Fixplate.
Then, we will use the helper functions to create projects and project groups. The order of fields has changed, so let’s fix that.
someProject :: Project someProject = projectGroup "Sweden" [stockholm, göteborg, malmö] where stockholm = project 1 "Stockholm" göteborg = project 2 "Gothenburg" malmö = projectGroup "Malmö" [city, limhamn] city = project 3 "Malmö City" limhamn = project 4 "Limhamn"
Now let’s try it out!
We open the REPL, load the
Demo module, calculate a project tree of reports, and draw the tree of reports using
$ stack repl ...> :l Demo *Demo> :l Demo *Demo> pr <- calculateProjectReports someProject *Demo> drawTreeWith prettyResult pr \-- Sweden: Budget: -16682.99, Net: -1996.02, difference: +14686.97 |-- Stockholm (1): Budget: -2275.58, Net: -1816.54, difference: +459.04 |-- Gothenburg (2): Budget: -7492.88, Net: +1354.37, difference: +8847.25 \-- Malmö: Budget: -6914.53, Net: -1533.85, difference: +5380.68 |-- Malmö City (3): Budget: -1436.63, Net: +567.36, difference: +2003.99 \-- Limhamn (4): Budget: -5477.90, Net: -2101.21, difference: +3376.69
Same nice results as before, but using a different technique.
With Fixplate, we have raised the abstraction level, and made our project data type highly extensible and reusable. This does, however, come with a cost, at least in terms of cognitive load for programmers.
I want to warn you of picking this technique up prematurely. Make sure you and your colleagues are comfortable with explicit recursion and monad transformers before considering recursion schemes. I would be careful about introducing this in a work project. The tradeoff is one you have to make yourself. If you are working a lot with similar data structures, recursion schemes, or one of the Uniplate-like libraries, might be a good choice for you.
And that is all for today!
The source code for the full series is available at github.com/haskell-at-work/domain-modelling-with-haskell.