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 Person)
  • A condition that applies to a relation (like a Person's Teams)

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 Persons on the People page and Teams 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
Filter type with two concrete examples of the where_ type parameter

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")]
Two possible Filter instances

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 TeamWhere to a variant of PersonWhere, representing a sub-filter on Teams the Person belongs to.
  • Add a Filter PersonWhere to a variant of TeamWhere, representing a sub-filter on a Team's members.

So not only do PersonWhere and 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 PersonWhere and TeamWhere to each include sub-filter conditions for the other:

type PersonWhere
    = PersonName StringCondition
    | PersonIsMemberOfTeams (Filter TeamWhere)


type TeamWhere
    = TeamName StringCondition
    | TeamHasMembers (Filter PersonWhere)
PersonWhere and TeamWhere mutually recurse to include each other

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 types are redundant

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 SomeTypeA or SomeTypeB:

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 Chicken and 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 ...
	
This instantiation can never end

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, PersonWhere and TeamWhere both have non-recursive variants PersonName and 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.