Compile-time checks on values in a list with phantom types
2020-05-18

Recently, Jeroen Engels wrote a post about using phantom types to single out an element of a type in order to implement compile-time constraints.

I was curious to see how this technique could be applied to a specific API design problem. In packages like elm/html and mdgriffith/elm-ui, we have functions that take lists of attributes:

div [ Attr.class "header" ]
    [ input [ Attr.class "menu-btn", Attr.type_ "checkbox", Attr.id "menu-btn" ] [] ]
layout [ width <| px 600, height fill, padding 20 ] someElement

However, not all attributes are applicable to any kind of function. For example, attaching Attr.type_ "checkbox" to a div doesn’t make sense.

In practice, they just get ignored, but sometimes that can lead to confusion.

Could Jeroen’s phantom type technique be used to disallow these kinds of situations at compile time?

Let’s suppose that I’m writing some kind of package which allows the user to create shapes with attributes:

rect [ width 100, height 50, color 0xFF0000 ]

circle [ diameter 100, color 0x00FF00 ]

I’m going to have some generic attributes which can be applied to any shape (like color), and I’m also going to have shape-specific attributes. For example, a diameter only makes sense for a circle, and conversely it’s not appropriate to set width and height for a circle.

At the same time, I want to have lists of attributes, which means that all the attribute functions have to return the same type. I have to have something like this type:

type Attr 
    = Width Int
    | Height Int
    | Diameter Int
    | Color String

Then the attribute functions will return this type:

width : Int -> Attr
width w =
    -- omitting checks for negative values etc.
    Width w

Putting it together into a minimal program:

type Shape
    = Rect
    | Circle


type Attr
    = Diameter Int
    | Height Int
    | Width Int
    | Color Int


diameter =
    Diameter


height =
    Height


width =
    Width


color =
    Color


circle : List Attr -> Shape
circle attrs =
    Circle


rect : List Attr -> Shape
rect attrs =
    Rect


main =
    Html.text <|
        Debug.toString
            [ circle [ diameter 100 ]
            , rect [ width 100, height 50 ]
            ]

As there are generic attributes like color, I can’t define a separate attribute type for each shape, and as a result of having one type for all attributes I can also write undesirable things like this:

rect [ diameter 100 ]  -- still compiles

Phantom types to the rescue?

Perhaps it’s possible to distinguish attributes via phantom types. First of all, Attr needs to have a type tag, and let’s define a couple of tags to use:

type Attr tag 
    = Diameter Int
    | Height Int
    | Width Int
    | Color Int

type Circle = CircleTag 
type Rect = RectTag

Next, I need to change the types of some functions. circle and rect will take lists of attributes tagged with the appropriate tag:

circle : List (Attr Circle) -> Shape
circle attrs =
    Circle


rect : List (Attr Rect) -> Shape
rect attrs =
    Rect

Let’s also define a type signature for diameter that makes it return an attribute tagged with Circle:

diameter : Int -> Attr Circle
diameter =
    Diameter

This is enough to make rect [ diameter 100 ] produce a compiler error:

The 1st argument to `rect` is not what I expect:

52|             , rect [ diameter 100, color 0xFF0000 ]
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This argument is a list of type:

    List (Attr Circle)

But `rect` needs the 1st argument to be:

    List (Attr Rect)

Here is a complete program that only allows width and height attributes to be used with a rect, and diameter to be used only with circle:

type Shape
    = Rect
    | Circle


type Attr tag 
    = Diameter Int
    | Height Int
    | Width Int
    | Color Int


type Circle = CircleTag 
type Rect = RectTag 

diameter : Int -> Attr Circle
diameter =
    Diameter


height : Int -> Attr Rect
height =
    Height


width : Int -> Attr Rect
width =
    Width


color : Int -> Attr any 
color =
    Color


circle : List (Attr Circle) -> Shape
circle attrs =
    Circle


rect : List (Attr Rect) -> Shape
rect attrs =
    Rect


main =
    Html.text <|
        Debug.toString
            [ circle [ diameter 100 ]
            , rect [ color 0xFF0000 ]
            ]

Note that because the type signature of color is Int -> Attr any, it can appear in the same list as Attr Rect or Attr Circle. You can read the return type as “attribute for any shape”.

So far, so good. Let’s introduce another shape:

ellipse : List (Attr Ellipse) -> Shape 
ellipse attrs =
    Ellipse

The tricky thing is that I want to be able to write ellipse [ width 100, height 50 ], just like a rect. However, that’s not going to compile because width and height produce Attr Rect which is a different type from Attr Ellipse.

At this point, I only have two options for the specificity of an attribute:

  • Attr Rect works with one kind of shape
  • Attr any works with any shape

However, I really want to have an attribute that works with subset of shapes.

The only way to introduce more categorisation between “one” and “any” seems to be to tag the tag:

type WithTwoDimensions a
    = WithTwoDimensionsTag

height : Int -> Attr (WithTwoDimensions a)
height =
    Height

The idea here is to say “height can be applied to any shape that has two dimensions”.

The type signatures of ellipse and rect have to change to incorporate this, but conveniently, the type signature of circle does not require changes:

circle : List (Attr Circle) -> Shape
circle attrs =
    Circle


ellipse : List (Attr (WithTwoDimensions Ellipse)) -> Shape 
ellipse attrs =
    Ellipse


rect : List (Attr (WithTwoDimensions Rect)) -> Shape
rect attrs =
    Rect

main =
    Html.text <|
        Debug.toString
            [ circle [ diameter 100 ]  -- OK
            , rect [ width 100, height 50, color 0xFF0000 ]  -- OK
            , ellipse [ width 100, height 50, color 0xFF0000 ]  -- OK
            , circle [ width 100 ]  -- compile-time error
            , ellipse [ diameter 100 ]  -- compile-time error
            ]

Can I take this further? What if I have another subset of shapes which can be filled with a color, one of which is ellipse? That is, I want to be able to write ellipse [ fill 0x0, width 100, height 50 ] but not circle [ fill 0x0 ].

Let’s add another tag and define the fill attribute:

type WithFill a 
    = WithFillTag a

fill : Int -> Attr (WithFill a) 
fill =
    Color

Let’s also add another layer of tagging to ellipse to allow for the fill attribute:

ellipse : List (Attr (WithFill (WithTwoDimensions Ellipse))) -> Shape 
ellipse attrs =
    Ellipse

Here, I start running into trouble. If I try to use this attribute, I get an error:

ellipse [ fill 0x0, width 100, height 50, color 0xFF0000 ]
The 2nd element of this list does not match all the previous elements:

77|             , ellipse [ fill 0x0, width 100, height 50, color 0xFF0000 ]  -- OK
                                      ^^^^^^^^^
This `width` call produces:

    Attr (WithTwoDimensions a)

But all the previous elements in the list are:

    Attr (WithFill a)

This error exposes a limitation of this technique: it only works for a linear hierarchy of shape types:

Shape 
  |- Circle 
  +- WithTwoDimensions
      |- Rect 
      +- WithFill
          +- Ellipse

To adhere to this limitation, I have to modify the type signature of fill like this:

fill : Int -> Attr (WithTwoDimensions (WithFill a)) 
fill =
    Color

In other words, this attribute can only be applied to shapes which also take width and height. I cannot let circle also have a fill attribute without making fill a generic attribute applicable to any shape.

main =
    Html.text <|
        Debug.toString
            [ rect [ fill 0x0, width 100, height 50, color 0xFF0000 ]  -- compiler error
            , ellipse [ fill 0x0, width 100, height 50, color 0xFF0000 ]  -- OK
            ]

This technique provides quite a nice developer experience for working with lists of attributes or even lists of child elements – basically any situation where a function takes a list of values of a custom type. However, it can only be applied in a narrow scenario where the functions can be arranged into a strictly linear hierarchy.

A better alternative

Luckily, there is a more flexible solution. Instead of nesting tags, I can use extensible records as tags, as records are types too!

The idea is similar to nested tags: the argument type for attributes taken by shape functions is specific, while the return type of attribute functions is generic (but with constraints). Let’s see what that looks like, first for attribute functions:

type Supported = SupportedTag

height : Int -> Attr { compatible | twoDimensions : Supported }
height =
    Height


width : Int -> Attr { compatible | twoDimensions : Supported }
width =
    Width


diameter : Int -> Attr { compatible | diameter : Supported }
diameter =
    Diameter


color : Int -> Attr any
color =
    Color


fill : Int -> Attr { compatible | fill : Supported } 
fill =
    Color

And then for the shape functions:

circle : List (Attr { diameter : Supported }) -> Shape
circle attrs =
    Circle


ellipse : List (Attr { twoDimensions : Supported, fill : Supported }) -> Shape 
ellipse attrs =
    Ellipse


rect : List (Attr { twoDimensions : Supported }) -> Shape
rect attrs =
    Rect

Note that the type signatures for attribute functions contain extensible records or, in case of color, simply a for any type because it’s applicable to all shapes.
On the other hand, the type signatures for shape functions have regular records.

With these functions, I can get the same level of compiler checking that I could get with nested type tags:

main =
    Html.text <|
        Debug.toString
            [ circle [ height 50, diameter 100, color 0xFF0000 ]  -- compiler error
            , rect [ diameter 100, width 100, height 50 ]  -- compiler error
            , rect [ fill 0x0, width 100, height 50 ]  -- compiler error
            ]

However, there is a significant advantage to this approach compared to nested type tags. The shapes no longer have to form a linear hierarchy. For example, I can easily allow circle to take a fill attribute by adding fill : Supported into the Attr tag:

circle : List (Attr { diameter : Supported, fill : Supported }) -> Shape
circle attrs =
    Circle

circle [ fill 0x001100, diameter 100, color 0xFF0000 ]  -- OK

Potentially, I could apply tags for every attribute so this approach can be very granular, although the type signatures would get rather unwieldy.

The compiler errors given for misapplied tags are quite informative, as long as you know why extensible records appear in type signatures:

The 1st argument to `rect` is not what I expect:

71|             , rect [ fill 0x0, width 100, height 50 ]  -- OK
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This argument is a list of type:

    List (Attr { a | fill : Supported, twoDimensions : Supported })

But `rect` needs the 1st argument to be:

    List (Attr { twoDimensions : Supported })

This approach is used in a number of packages, for example:

The benefit of enhancing your API with this technique is that you can potentially prevent invalid states, and also prevent confusion arising from misapplying attributes (or passing some other type of list with unwanted values to a function).

This approach also has limitations, however. Going back to the shape example,
I may not only want to prevent the wrong attributes being passed, but also to require that certain attributes are given to certain shapes. For instance, I may want a rect to always be given width and height instead of merely allowing those attributes.

It’s possible to implement such constraints with the phantom builder pattern, but that’s a different kind of API (with pipelines instead of lists). So far, I haven’t found a way to combine the approach above with enforcing any kind of required attributes.

I’m hoping that more explorations in this area will make it possible to create more sophisticated compile-time constraints.

Thanks to Jeroen Engels for reviewing this post and suggesting improvements.

Comments or questions? I’m @alexkorban on Twitter.

Looking for the nuts-and-bolts guide to creating non-trivial real world apps in Elm?

My book, Practical Elm for a Busy Developer, skips the basics and gets right into explaining how to do practical stuff. Things like building out the UI, communicating with servers, parsing JSON, structuring the application as it grows, testing, and so on. No handholding — the focus is on giving you more substance.

It’s up to date with Elm 0.19.

Pop in your email to get a sample chapter.

(You will also get notifications of new posts along with other mailing list only freebies.)

Book cover