AvlTree.elm

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 ())