Using mutually recursive types in practice

Show and Tell
1

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

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 TeamWhere to a variant of PersonWhere , representing a sub-filter on Team s 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)

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

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.

Originally posted at dmalashock.com/using-mutually-recursive-types-elm

13 Likes
2

That was interesting.

Some things you could link to in your article:

This compiler note, that you get when you try to define mutually recursive type aliases:

And the documentation for Json.Decode.lazy which explains how to write a decoder for a mutually recursive data structure:

https://package.elm-lang.org/packages/elm/json/latest/Json-Decode#lazy

1 Like
3

Right now I am trying to figure out a problem around this.

I have some data models with records that are mutually recursive. The simplest way in Elm to express those records is as a type alias to an Elm record type. Being mutually recursive I cannot do that, so I have to wrap them in a single constructor type, which can take the same name as the type itself:

type SomeRecord
    = SomeRecord { field1 : Int, field2 : String, field3 : Maybe OtherRecord }

I am wondering how best to do this. For example, if I have 3 record definitions that form a cycle, I probably only need to make 1 of them a type to break the cycle. Which one is the best one to pick? Or do I just make all of them into Elm types?

I also have to insert Maybes into the model, but the JSON descriptor I am interpreting to get my data model may not say that a value is optional. So do I turn your chicken and egg into

Chicken (Just (Egg (Chicken Nothing)))

OR

Chicken (Egg (Just (Chicken (Egg Nothing))))

OR

Chicken (Just (Egg (Just (Chicken Nothing))))

In the last one, both the recursive references are Maybes. I guess I need some heurisitcs around how to do this, based on what the data model spec does or does not say about fields being optional.

To know what to do with any possible data model, I think I need a search that scans over the data model and figures out if it is possible to build it - this would check that every possible branch can reach a base case. Branches that cannot need to be made into Maybes.

===

The actual problem I am working with is generating an Elm stub for AWS DynamoDb from its service descriptor. The service descriptor defines a mutually recursive data model.

4

Hi @rupert! Thanks for that link to the recursive-alias doc. I will include it.

As for your problem, I’m not totally sure, but my first inclination is that it sounds like it would be simpler to define SomeRecord as a type with multiple variants:

type SomeType
  = WithOtherType Int String OtherType
  | JustSomeType Int String

And then write separate decoders to pass into oneOf. But I haven’t sat down and tried, so I can’t tell whether that would make a difference.

5

Its a possiblity. Some of the record types I have, have a lot of Maybes in them. For example:

type alias CreateIdentityPoolInput =
    { allowUnauthenticatedIdentities : IdentityPoolUnauthenticated
    , cognitoIdentityProviders : Maybe CognitoIdentityProviderList
    , developerProviderName : Maybe DeveloperProviderName
    , identityPoolName : IdentityPoolName
    , identityPoolTags : Maybe IdentityPoolTagsType
    , openIdConnectProviderArns : Maybe OidcproviderList
    , samlProviderArns : Maybe SamlproviderList
    , supportedLoginProviders : Maybe IdentityProviders
    }

I really doubt that AWS will accept a request with all of these null in it (or give a response in other cases). The APIs there don’t do such a great job of eliminating the representation of illegal states. But I just have to go on what the spec says and work with that.

I would need a lot of constructors to cover all possible combinations of Just or Nothing. So its going to be easier just to keep them as Maybes. If the above record were part of mutually recursive loop, I would just convert it to:

type CreateIdentityPoolInput 
    = CreateIdentityPoolInput 
        { allowUnauthenticatedIdentities : IdentityPoolUnauthenticated
        , cognitoIdentityProviders : Maybe CognitoIdentityProviderList
        , developerProviderName : Maybe DeveloperProviderName
        , identityPoolName : IdentityPoolName
        , identityPoolTags : Maybe IdentityPoolTagsType
        , openIdConnectProviderArns : Maybe OidcproviderList
        , samlProviderArns : Maybe SamlproviderList
        , supportedLoginProviders : Maybe IdentityProviders
        }

The single constructor form is sufficient to allow it to be part of a recursive type or mutually recursive relationship of types/type aliases.

6

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.