tricu

An interpreted language for exploring Tree Calculus
Log | Files | Refs | README | LICENSE

index.tri (1880B)

      1 !import prelude *
      2 !export sourceIndexBuild
      3 !export sourceIndexPut
      4 !export sourceIndexGet
      5 
      6 -- A prefix trie of the Leaf/Stem/Fork preorder of a key tree. Complete tree
      7 -- encodings are prefix-free. Empty = Leaf, terminal = Stem opaque-value,
      8 -- branch = Fork leaf-child (Fork stem-child fork-child).
      9 -- Build is lazy and first-binding-wins; put overrides one key. Values are
     10 -- never inspected. Compiler callers supply proper binding lists and finite keys.
     11 sourceIndexLeaf index = triage t (_ : t) (a bc : a) index
     12 sourceIndexStem index = triage t (_ : t) (a bc : fst bc) index
     13 sourceIndexFork index = triage t (_ : t) (a bc : snd bc) index
     14 
     15 sourceIndexPutPending pending value index = (lazyList
     16   (_ : just value)
     17   (key rest : triage
     18     (pair (sourceIndexPutPending rest value (sourceIndexLeaf index))
     19       (pair (sourceIndexStem index) (sourceIndexFork index)))
     20     (child : pair (sourceIndexLeaf index)
     21       (pair (sourceIndexPutPending (pair child rest) value (sourceIndexStem index))
     22         (sourceIndexFork index)))
     23     (left right : pair (sourceIndexLeaf index)
     24       (pair (sourceIndexStem index)
     25         (sourceIndexPutPending (pair left (pair right rest)) value (sourceIndexFork index))))
     26     key)
     27   pending)
     28 sourceIndexPut key value index = sourceIndexPutPending [key] value index
     29 sourceIndexBuild entries = (lazyList (_ : t)
     30   (entry rest : sourceIndexPut (fst entry) (snd entry) (sourceIndexBuild rest)) entries)
     31 sourceIndexGetPending pending index = (triage nothing
     32   (value : lazyList (_ : just value) (_ _ : nothing) pending)
     33   (a bc : lazyList (_ : nothing)
     34     (key rest : triage
     35       (sourceIndexGetPending rest a)
     36       (child : sourceIndexGetPending (pair child rest) (fst bc))
     37       (left right : sourceIndexGetPending (pair left (pair right rest)) (snd bc))
     38       key)
     39     pending)
     40   index)
     41 sourceIndexGet index key = sourceIndexGetPending [key] index