# Using mutually recursive types in practice

**URL:** <https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066>\
**Category:** Show and Tell\
**Created:** [July 21, 2020, 3:14pm UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066 "2020-07-21T15:14:37Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![duncanmalashock](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/duncanmalashock/32/3408_2.png) [@duncanmalashock](https://discourse.elm-lang.org/u/duncanmalashock)\
**Post date:** [July 21, 2020, 3:14pm UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066/1 "2020-07-21T15:14:37Z")

</div>

Hi all! I wrote a [post](https://dmalashock.com/using-mutually-recursive-types-elm/) on a real-world use case for mutually recursive types:

* * *

I work on the team at [Blissfully](https://www.blissfully.com/), where we use [Elm](https://dmalashock.com/using-mutually-recursive-types-elm/elm-lang.org) 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:

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

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

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

```auto
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_ :

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

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

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

```auto
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](https://dmalashock.com/using-mutually-recursive-types-elm/)

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [July 21, 2020, 4:08pm UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066/2 "2020-07-21T16:08:48Z")

</div>

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 alias`es:

> <https://github.com/elm/compiler/blob/master/hints/recursive-alias.md>

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](https://package.elm-lang.org/packages/elm/json/latest/Json-Decode#lazy)

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [July 21, 2020, 4:21pm UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066/3 "2020-07-21T16:21:26Z")

</div>

> [@duncanmalashock](#):
>
> 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_ .

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:

```auto
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 `Maybe`s 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 `Maybe`s. 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.

---

<div class="post-metadata">

**Author:** ![duncanmalashock](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/duncanmalashock/32/3408_2.png) [@duncanmalashock](https://discourse.elm-lang.org/u/duncanmalashock)\
**Post date:** [July 22, 2020, 6:37pm UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066/4 "2020-07-22T18:37:53Z")

</div>

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:

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

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [July 23, 2020, 11:47am UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066/5 "2020-07-23T11:47:38Z")

</div>

> [@duncanmalashock](#):
>
> ```auto
> type SomeType
> = WithOtherType Int String OtherType
> | JustSomeType Int String
> 
> ```

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

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

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

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/50a05e53677a2c3b47776d7abd0f113eb50193a1.png) [@system](https://discourse.elm-lang.org/u/system)\
**Post date:** [August 2, 2020, 11:47am UTC](https://discourse.elm-lang.org/t/using-mutually-recursive-types-in-practice/6066/6 "2020-08-02T11:47:41Z")

</div>

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