main.hvm

// Sort : Arr -> Arr
(Sort t) = (ToArr 0 (ToMap t))

// ToMap : Arr -> Map
(ToMap Null)       = Free
(ToMap (Leaf a))   = (Radix a)
(ToMap (Node a b)) = (Merge (ToMap a) (ToMap b))

// ToArr : Map -> Arr
(ToArr x Free) = Null
(ToArr x Used) = (Leaf x)
(ToArr x (Both a b)) =
  let a = (ToArr (+ (* x 2) 0) a)
  let b = (ToArr (+ (* x 2) 1) b)
  (Node a b)

// Merge : Map -> Map -> Map
(Merge Free       Free)       = Free
(Merge Free       Used)       = Used
(Merge Used       Free)       = Used
(Merge Used       Used)       = Used
(Merge Free       (Both c d)) = (Both c d)
(Merge (Both a b) Free)       = (Both a b)
(Merge (Both a b) (Both c d)) = (BOTH (Merge a c) (Merge b d))

// Radix : U60 -> Map
(Radix n) =
  let r = Used
  let r = (U60.swap (& n 1) r Free)
  let r = (U60.swap (& n 2) r Free)
  let r = (U60.swap (& n 4) r Free)
  let r = (U60.swap (& n 8) r Free)
  let r = (U60.swap (& n 16) r Free)
  let r = (U60.swap (& n 32) r Free)
  let r = (U60.swap (& n 64) r Free)
  let r = (U60.swap (& n 128) r Free)
  let r = (U60.swap (& n 256) r Free)
  let r = (U60.swap (& n 512) r Free)
  let r = (U60.swap (& n 1024) r Free)
  let r = (U60.swap (& n 2048) r Free)
  let r = (U60.swap (& n 4096) r Free)
  let r = (U60.swap (& n 8192) r Free)
  let r = (U60.swap (& n 16384) r Free)
  let r = (U60.swap (& n 32768) r Free)
  let r = (U60.swap (& n 65536) r Free)
  let r = (U60.swap (& n 131072) r Free)
  let r = (U60.swap (& n 262144) r Free)
  let r = (U60.swap (& n 524288) r Free)
  let r = (U60.swap (& n 1048576) r Free)
  let r = (U60.swap (& n 2097152) r Free)
  let r = (U60.swap (& n 4194304) r Free)
  let r = (U60.swap (& n 8388608) r Free)
  r

// Reverse : Arr -> Arr
(Reverse Null)       = Null
(Reverse (Leaf a))   = (Leaf a)
(Reverse (Node a b)) = (Node (Reverse b) (Reverse a))

// Sum : Arr -> U60
(Sum Null)       = 0
(Sum (Leaf x))   = x
(Sum (Node a b)) = (+ (Sum a) (Sum b))

// Gen : U60 -> Arr
(Gen n) = (Gen.go n 0)
  (Gen.go 0 x) = (Leaf x)
  (Gen.go n x) =
    let x = (<< x 1)
    let y = (| x 1)
    let n = (- n 1)
    (Node (Gen.go n x) (Gen.go n y))

// Strict constructors
(BOTH !a !b) = (Both a b)
//(NODE !a !b) = (Node a b)
//(LEAF !a)    = (Leaf a)

(Main n) = (Sum (Sort (Reverse (Gen n))))