Created
July 31, 2017 20:24
-
-
Save zwilias/ccd72ee7925b27e8c41176ebe7d33564 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| module AvlTree exposing (..) | |
| {- Using these definitions, it is impossible to construct an imbalanced binary tree -} | |
| {- a Node encodes a single Node: | |
| - holding a value of type `a` | |
| - with the type of a tree of (height - 1) `t1` | |
| - and the type of a tree of (height - 2) `t2` | |
| -} | |
| type Node a t1 t2 | |
| = Left t1 a t2 | |
| | Even t1 a t1 | |
| | Right t2 a t1 | |
| {- A tree encodes a tree of arbitrary height, based again on the | |
| type of a tree of height - 1 `t1` and height - 2 `h2 | |
| -} | |
| type Tree a t1 t2 | |
| = Zero t1 | |
| | Succ (Tree a (Node a t1 t2) t1) | |
| {- an Avl tree, finally, points to an entrypoint of a `Tree` which has no parents, | |
| so the height of its parent and grandparents is simply the unit type | |
| -} | |
| type alias AvlTree a = | |
| Tree a () () | |
| emptyTree : AvlTree Int | |
| emptyTree = | |
| Zero () | |
| singleEntry : AvlTree Int | |
| singleEntry = | |
| Succ <| Zero <| Even () 1 () | |
| twoEntries : AvlTree Int | |
| twoEntries = | |
| Succ <| Succ <| Zero <| Left (Even () 2 ()) 1 () | |
| twoEntriesRight : AvlTree Int | |
| twoEntriesRight = | |
| Succ <| Succ <| Zero <| Right () 1 (Even () 2 ()) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment