# 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.## Show Notes

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 `Project`

and `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.

We’ll rename `Project`

to `ProjectF`

, by convention, and define a type alias `Project`

for `Mu ProjectF`

.

We also need to import `Mu`

and its `Fix`

constructor:

`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`

. So `Mu`

is responsible for recursively injecting `f`

into `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 `Attr`

type.

We define a type alias `ProjectReport`

.

Then, we rewrite `calculateProjectReports`

to use a function called `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.

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 `prettyResult`

.

```
$ 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.

### Summary

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!

## Source Code

The source code for the full series is available at github.com/haskell-at-work/domain-modelling-with-haskell.