git.iko.soy/elk
on 267f708 help sign in
elk/hints/infinite-type.md
116 lines 4.8 kB history raw
1# Hints for Infinite Types
3Infinite types are probably the trickiest kind of bugs to track down. Usually it means you are working on a relatively sophisticated recursive function and something is very subtly off.
5I am just going to show a couple examples of infinite types that have been reported and how they were resolved to illustrate the kinds of things you may be running into.
8## Nested Record Types
10(From issue [#987](https://github.com/elm-lang/elm-compiler/issues/987))
12Someone was working with records, and wanted to do something kind of tricky with type aliases. In this case, they created a `Persisted` type alias that would say "whatever record you have, well I'm talking about one where there is an additional `id` field."
14```elm
15type alias Persisted record =
16 { record | id : Int }
18type alias Update record =
19 record -> Int -> record
21type Updatable record =
22 Updatable (Update record) (Persisted record)
24newRecord (Updatable myUpdate myRecord) =
25 let
26 updateThisRecord =
27 myUpdate myRecord
28 in
29 "foo"
30```
32Now just looking at the code, it seems fine. You can create `Persisted` records, you can have a record `Update`, and you can bundle them together with `Updatable`. In our `newRecord` function we are partially applying the `myUpdate` function. Everything *seems* fine, but something is causing an infinite type.
34The best thing to do is start writing down as many types for yourself as possible:
36```elm
37myUpdate : Update record -- record -> Int -> record
38myRecord : Persisted record -- { record | id : Int }
39```
41The trouble is that it's the same `record` in both of these types! The `myUpdate` function wants t take a `record` and produce a `record`, but it is being given `{ record | id : Int }`. Type checking is going to say, "well, if `record` is actually an infinite sequence of `{ { ... | id : Int } | id : Int }` then they *can* be equal!" While that is true and very clever, it is not the intent of this code.
43So the fix for this person was to add one thing into the `Updatable` type:
45```elm
46type Updatable record =
47 Updatable (Update (Persisted record)) (Persisted record)
48```
50Notice the new `Persisted` in the `Update` part. That was the fix!
53## Exploding Either
55(From issue [#707](https://github.com/elm-lang/elm-compiler/issues/707))
57There is a relatively obscure package called `evancz/automaton` that captures state and functionality using callbacks. So far, it does not seem to be extremely useful idea given its downsides, but it did lead to quite a tough infinite type.
59Here is a snippet of code that combines two bacic automatons into one. The resulting automaton takes in either a `Left` or `Right` value. If it is a `Left` we will use the left automaton, if it is a `Right` we will use the right one.
61```elm
62type Either a b = Left a | Right b
64type Automaton a b =
65 Step (a -> (Automaton a b, b))
67(+++) : Automaton a b -> Automaton c d -> Automaton (Either a c) (Either b d)
68(+++) (Step leftStep) (Step rightStep) =
69 Step <| \either ->
70 case either of
71 Left a ->
72 let (newLeft, b) = leftStep a
73 in (newLeft, Left b)
75 Right c ->
76 let (newRight, d) = rightStep c
77 in (newRight, Right d)
78```
80This triggers a relatively confusing error message. The right thing to do in these scenarios is try to figure out the type of literally every piece of the definition. If you can, break parts out into other top-level declarations with type annotations so the compiler can check your work. So you might write down some notes to yourself like this:
82```elm
83left : Automaton a b
84leftStep : a -> (Automaton a b, b)
86right : Automaton c d
87rightStep : c -> (Automaton c d, d)
89either : Either a c
91newLeft : Automaton a b
92newRight : Automaton c d
93```
95Knowing that both branches of a `case` must end with the same type, it looks like `newLeft` and `newRight` are causing the issue here. So in the revised code we make it so both branches return the same type.
97```elm
98type Either a b = Left a | Right b
100type Automaton a b =
101 Step (a -> (Automaton a b, b))
103(+++) : Automaton a b -> Automaton c d -> Automaton (Either a c) (Either b d)
104(+++) (Step leftStep as left) (Step rightStep as right) =
105 Step <| \either ->
106 case either of
107 Left a ->
108 let (newLeft, b) = leftStep a
109 in (newLeft +++ right, Left b)
111 Right c ->
112 let (newRight, d) = rightStep c
113 in (left +++ newRight, Right d)
114```
116So yeah, if you are skimming this, you probably did not see the change immediately. My experience debugging these kinds of things is that my brain thinks what I wrote is correct so much that it becomes kind of blind to the issue. The best thing to do is slow down and break the problem apart. Or ask someone.