git.iko.soy/elk
on 32ff950 help sign in
elk/docs/hints/recursive-alias.md
161 lines 4.4 kB history raw
1# Hints for Recursive Type Aliases
3At the root of this issue is the distinction between a `type` and a `type alias`.
6## What is a type alias?
8When you create a type alias, you are just creating a shorthand to refer to an existing type. So when you say the following:
10```elm
11type alias Time = Float
13type alias Degree = Float
15type alias Weight = Float
16```
18You have not created any *new* types, you just made some alternate names for `Float`. You can write down things like this and it'll work fine:
20```elm
21add : Time -> Degree -> Weight
22add time degree =
23 time + degree
24```
26This is kind of a weird way to use type aliases though. The typical usage would be for records, where you do not want to write out the whole thing every time. Stuff like this:
28```elm
29type alias Person =
30 { name : String
31 , age : Int
32 , height : Float
33 }
34```
36It is much easier to write down `Person` in a type, and then it will just expand out to the underlying type when the compiler checks the program.
39## Recursive type aliases?
41Okay, so lets say you have some type that may contain itself. In Elm, a common example of this is a comment that might have subcomments:
43```elm
44type alias Comment =
45 { message : String
46 , upvotes : Int
47 , downvotes : Int
48 , responses : List Comment
49 }
50```
52Now remember that type *aliases* are just alternate names for the real type. So to make `Comment` into a concrete type, the compiler would start expanding it out.
54```elm
55 { message : String
56 , upvotes : Int
57 , downvotes : Int
58 , responses :
59 List
60 { message : String
61 , upvotes : Int
62 , downvotes : Int
63 , responses :
64 List
65 { message : String
66 , upvotes : Int
67 , downvotes : Int
68 , responses : List ...
69 }
70 }
71 }
72```
74The compiler cannot deal with values like this. It would just keep expanding forever.
77## Recursive types!
79In cases where you want a recursive type, you need to actually create a brand new type. This is what the `type` keyword is for. A simple example of this can be seen when defining a linked list:
81```elm
82type List
83 = Empty
84 | Node Int List
85```
87No matter what, the type of `Node n xs` is going to be `List`. There is no expansion to be done. This means you can represent recursive structures with types that do not explode into infinity.
89So let's return to wanting to represent a `Comment` that may have responses. There are a couple ways to do this:
92### Obvious, but kind of annoying
94```elm
95type Comment =
96 Comment
97 { message : String
98 , upvotes : Int
99 , downvotes : Int
100 , responses : List Comment
101 }
102```
104Now lets say you want to register an upvote on a comment:
106```elm
107upvote : Comment -> Comment
108upvote (Comment comment) =
109 Comment { comment | upvotes = 1 + comment.upvotes }
110```
112It is kind of annoying that we now have to unwrap and wrap the record to do anything with it.
115### Less obvious, but nicer
117```elm
118type alias Comment =
119 { message : String
120 , upvotes : Int
121 , downvotes : Int
122 , responses : Responses
123 }
125type Responses = Responses (List Comment)
126```
128In this world, we introduce the `Responses` type to capture the recursion, but `Comment` is still an alias for a record. This means the `upvote` function looks nice again:
130```elm
131upvote : Comment -> Comment
132upvote comment =
133 { comment | upvotes = 1 + comment.upvotes }
134```
136So rather than having to unwrap a `Comment` to do *anything* to it, you only have to do some unwrapping in the cases where you are doing something recursive. In practice, this means you will do less unwrapping which is nice.
139## Mutually recursive type aliases
141It is also possible to build type aliases that are *mutually* recursive. That might be something like this:
143```elm
144type alias Comment =
145 { message : String
146 , upvotes : Int
147 , downvotes : Int
148 , responses : Responses
149 }
151type alias Responses =
152 { sortBy : SortBy
153 , responses : List Comment
154 }
156type SortBy = Time | Score | MostResponses
157```
159When you try to expand `Comment` you have to expand `Responses` which needs to expand `Comment` which needs to expand `Responses`, etc.
161So this is just a fancy case of a self-recursive type alias. The solution is the same. Somewhere in that cycle, you need to define an actual `type` to end the infinite expansion.