Hi all! I wrote a post on a real-world use case for mutually recursive types:
I work on the team at Blissfully, where we use Elm in production. Recently a project led me to a use case for an unusual technique called mutually recursive types . I’ll explain what that means, and when this technique might help you. Let’s start with how I got there:
We’ve been building better controls for filtering data in our web app, ones that offer more powerful options than the simple controls that we’d been building per page until now.
We chose a pattern that can describe lists of conditions (called
Where in our API). A
Where can represent one of two things:
- A condition that applies to a thing (like a
- A condition that applies to a relation (like a
This is a general-purpose solution that can be applied to many different parts of the app. So, having built it, we’d be able to filter for
Person s on the People page and
Team s on the Teams page, to name a couple possibilities.
Here’s a simplified example of how it could be modeled using Elm types, where a
Filter is parameterized with a type that describes conditions that satisfy the filter:
type Filter where_ = Filter (List where_) type StringCondition = Is String | IsNot String | IsOneOf (List String) | IsNotOneOf (List String) | StartsWith String | EndsWith String | Contains String type PersonWhere = PersonName StringCondition type TeamWhere = TeamName StringCondition
Using the example above, a
Filter PersonWhere can specify conditions for a person’s name, and a
Filter TeamWhere can specify conditions for a team’s name:
myPersonFilter : Filter PersonWhere myPersonFilter = Filter [PersonName (StartsWith "Matt")] myTeamFilter : Filter TeamWhere myTeamFilter = Filter [TeamName (Is "Engineering")]
This is a good start, but what about filters that specify conditions for related things, like we described earlier? For example, how would we model a filter that answers this crucial question: “How many people have a person named Matt on their team?” ?
We’d want to do the following:
- Add a
Filter TeamWhereto a variant of
PersonWhere, representing a sub-filter on
- Add a
Filter PersonWhereto a variant of
TeamWhere, representing a sub-filter on a
So not only do
TeamWhere need to be able to contain sub-filters that reference each other, but those relationships can also form cycles.
Luckily, in Elm, multiple types can be defined in terms of each other:
type Chicken = Chicken Egg type Egg = Egg Chicken
(Note: this particular example has a problem, which we’ll cover in a moment.)
This is valid in Elm. It’s called mutually recursive definition, and it’s helpful in cases like this: when two types need to be able to contain instances of each other.
Taking advantage of this property of the Elm type system, we can update
TeamWhere to each include sub-filter conditions for the other:
type PersonWhere = PersonName StringCondition | PersonIsMemberOfTeams (Filter TeamWhere) type TeamWhere = TeamName StringCondition | TeamHasMembers (Filter PersonWhere)
Now we can model a filter for all people on a team that includes a person named Matt :
hasATeammateNamedMatt : Filter PersonWhere hasATeammateNamedMatt = Filter [ PersonIsMemberOfTeams (Filter [ TeamHasMembers (Filter [ PersonName (StartsWith "Matt") ] ) ] ) ]
Questions to ask before using this technique
Like a lot of clever type tricks, mutually recursive definition is one to use only when it’s well justified. These questions can help you decide whether you’ll be able to apply it successfully:
Do the types need to be distinct?
Maybe it’s clear to you that some type will need a recursive definition. But if you’re able to model your domain concept with a single recursive type, you probably should. For example:
type TreeA = SubtreeA (TreeB) | LeafA SomeTypeA type TreeB = SubtreeB (TreeA) | LeafB SomeTypeB
These trees mutually recurse, but they have the same variants, so neither offers anything unique. It would be simpler to use a single
Tree type that could be parameterized with
type Tree a = Subtree (Tree a) | Leaf a
Can I actually construct instances of these types?
You might have noticed, as I mentioned before, that the
Egg example defines types that lead to a problem—neither can ever be successfully constructed:
aProblem : Chicken aProblem = Chicken (Egg (Chicken (Egg (Chicken (Egg (Chicken (Egg ...
To prevent this problem, as in any recursive situation, you’ll need to make sure your mutually recursive types have a base case (that is, a non-recursive case) that can end the sequence. In the filter example,
TeamWhere both have non-recursive variants
TeamName that allow instantiations to end.
Can I keep these types in the same file?
One potential issue with mutually recursive types is that they can’t be defined in separate modules, which would require mutual imports and cause a cyclical dependency. Although it depends on the structure of your project, this may not be a practical issue in the short term. But keep in mind you won’t be able to separate these types into separate modules, which may be a problem if they take on other modeling concerns.
One more point: if you’ve used recursive type definitions in Elm, you may already be aware that recursive definition only works with types , and not with type aliases .
Because we were able to use mutually recursive definition for the
Where types our filters use, we’re able to recursively nest our filters to any depth. If we hadn’t been able to use this technique, we might have had to model sub-filters as explicit combinations down to an arbitrary depth, and duplicate our definitions to implement them.
Mutually recursive definition is a technique I don’t often see, but in the cases where it’s appropriate, it’s a concise solution that provides some unique behavior.
Originally posted at dmalashock.com/using-mutually-recursive-types-elm