Skew K-ary tree

skew.u

-- Structure: a buffer of Arity, then a list of complete trees of exponentially increasing size
type Skew a = Skew [a] [(Nat, [Skew.Tree a])]
type Skew.Tree a = Tree [a] [Skew.Tree a] 

Skew.Arity = 4

Skew.cons : a -> Skew a -> Skew a
Skew.cons a = cases Skew hd spine ->  
  hd' = a +: hd
  if List.size hd' < Arity then Skew hd' spine 
  else match spine with 
    [] -> Skew [] [(Arity, [Tree hd' []])]
    (sz, forest) +: tl 
      | List.size forest == Arity -> 
        sz' = sz * Arity + Arity
        t = Tree hd' forest
        match tl with 
          (sz2, forest2) +: tl | sz2 == sz' -> 
            forest2' = t +: forest2
            Skew [] ((sz', forest2') List.+: tl)
          _ -> Skew [] ((sz', [t]) +: tl)
      | sz == Arity -> Skew [] ((sz, Tree hd' [] +: forest) +: tl)
      | otherwise -> Skew [] ((Arity, [Tree hd' []]) +: spine)

> List.foldRight Skew.cons (Skew [] []) (range 0 64)

type Skew m a = 
  Skew 
    (a -> m)
    ([m] -> m)
    (Set a)
    [(Nat, [Skew.Tree m a])]

type Skew.Tree m a = Tree m (Set a) [Skew.Tree m a] 

-- Good point for the version that uses storage:
-- make sure to the minimal element of each subtree
-- at the parent, so that you can quickly and in memory
-- identify the child to descend into during search

Skew.empty f combine = Skew f combine [] []

Skew.cons : a -> Skew m a -> Skew m a
Skew.cons a = cases Skew fn combine buf spine ->  
  buf' = Set.insert a buf
  if Set.size buf' < Arity then Skew fn combine buf' spine 
  else match spine with 
    [] -> Skew [] [(Arity, [Tree buf' []])]
    (sz, forest) +: tl 
      | List.size forest == Arity -> 
        sz' = sz * Arity + Arity
        t = Tree buf' forest
        match tl with 
          (sz2, forest2) +: tl | sz2 == sz' -> 
            forest2' = t +: forest2
            Skew [] ((sz', forest2') List.+: tl)
          _ -> Skew [] ((sz', [t]) +: tl)
      | sz == Arity -> Skew [] ((sz, Tree buf' [] +: forest) +: tl)
      | otherwise -> Skew [] ((Arity, [Tree buf' []]) +: spine)

Doesn't compile yet.

    24 | > List.foldRight Skew.cons (Skew [] []) (range 0 64)
           ⧩
           Skew
             []
             [ (4, [Tree [0, 1, 2, 3] []])
             , ( 20
               , [ Tree
                     [4, 5, 6, 7]
                     [ Tree [8, 9, 10, 11] []
                     , Tree [12, 13, 14, 15] []
                     , Tree [16, 17, 18, 19] []
                     , Tree [20, 21, 22, 23] []
                     ]
                 , Tree
                     [24, 25, 26, 27]
                     [ Tree [28, 29, 30, 31] []
                     , Tree [32, 33, 34, 35] []
                     , Tree [36, 37, 38, 39] []
                     , Tree [40, 41, 42, 43] []
                     ]
                 , Tree
                     [44, 45, 46, 47]
                     [ Tree [48, 49, 50, 51] []
                     , Tree [52, 53, 54, 55] []
                     , Tree [56, 57, 58, 59] []
                     , Tree [60, 61, 62, 63] []
                     ]
                 ]
               )
             ]