2m: Ordered Maps

+mop

Ordered map mold builder

Constructs and validates an ordered map based on key type, value type and a comparator gate.

Ordinary +maps are always ordered by the +mug hash of their keys, while +mops are ordered by a comparator gate of your choosing.

Accepts

+mop has two layers, the first is a wet gate that takes two molds:

• key is a $mold, the type of the map key.

• value is a $mold, the type of the map value.

The wet gate produces a dry gate that takes:

• ord is a binary comparator $gate of $-([key key] ?) used to determine item ordering. It produces %.y if the first key should be first, and %.n if it should be second.

Warning:

Ordered maps will not work properly if two keys can be unequal under noun equality but equal via the compare gate.

Produces

A $mold.

Source

++  mop
  |*  [key=mold value=mold]
  |=  ord=$-([key key] ?)
  |=  a=*
  =/  b  ;;((tree [key=key val=value]) a)
  ?>  (apt:((on key value) ord) b)
  b

Examples

> *((mop @ @) gth)
{}

Descending order:

> (gas:((on @ @) gth) *((mop @ @) gth) 1^1 2^2 3^3 ~)
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

Ascending order:

> (gas:((on @ @) lth) *((mop @ @) lth) 1^1 2^2 3^3 ~)
{[key=1 val=1] [key=2 val=2] [key=3 val=3]}

Molding a correctly ordered mop

> =a (gas:((on @ @) gth) *((mop @ @) gth) 1^1 2^2 3^3 ~)

> (((mop @ @) gth) a)
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

Molding an incorrectly ordered mop:

> =a (malt 1^1 2^2 3^3 4^4 5^5 ~)

> (((mop @ @) gth) a)
dojo: hoon expression failed

Note you can't use ordinary +map constructors like +malt to make a +mop as it'll be in the wrong order.

---

+ordered-map

A synonym for +on.

Source

++  ordered-map  on

---

+on

Ordered map operations

Container arm for +mop operation arms. A +mop is an ordered set of key-value pairs.

Accepts

+on has two layers, the first is a wet gate that takes two molds:

• key is a $mold, the type of the map keys.

• val is a $mold, the type of the map values.

The wet gate produces a dry gate that takes:

• compare is a binary comparator $gate of $-([key key] ?) used to determine item ordering. It produces %.y if the first key should be first, and %.n if it should be second.

Produces

A +core whose arms perform the various +mop operations.

Source

++  on
  ~/  %on
  |*  [key=mold val=mold]
  =>  |%
      +$  item  [key=key val=val]
      --
  ~%  %comp  +>+  ~
  |=  compare=$-([key key] ?)
  ~%  %core    +  ~
  |%

Examples

> *((on @ @) gth)
< 20.htd
  1.ogd
  [ compare=<1|xpg [[@ @] [@ @] ?(%.y %.n)]>
    < 1.twi
      1.wlm
      [ [ key=<1.vde [* [our=@p now=@da eny=@uvJ] <17.ayh 34.ygp 14.usy 54.fbg 77.kga 232.mmf 51.qbt 123.ppa 46.hgz 1.pnw %140>]>
          val=<1.vde [* [our=@p now=@da eny=@uvJ] <17.ayh 34.ygp 14.usy 54.fbg 77.kga 232.mmf 51.qbt 123.ppa 46.hgz 1.pnw %140>]>
        ]
        <17.ayh 34.ygp 14.usy 54.fbg 77.kga 232.mmf 51.qbt 123.ppa 46.hgz 1.pnw %140>
      ]
    >
  ]
>

Here are the core's arms:

> (sloe -:!>(((on @ @) gth)))
~[
  %run
  %del
  %get
  %apt
  %dip
  %has
  %all
  %gas
  %pry
  %nip
  %lot
  %tab
  %tap
  %bap
  %ram
  %got
  %any
  %pop
  %uni
  %put
]

---

+all:on

Apply logical AND boolean test on all items.

Accepts

.a is a +mop.

.b is a $gate of the type $-([key val] ?), where the type of key and val match those of the +mop.

Produces

A ?.

Source

++  all
  ~/  %all
  |=  [a=(tree item) b=$-(item ?)]
  ^-  ?
  |-
  ?~  a
    &
  ?&((b n.a) $(a l.a) $(a r.a))

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> (all:myon mymop |=([key=@ val=@] (gte 3 val)))
%.y

> (all:myon mymop |=([key=@ val=@] (gte 2 val)))
%.n

---

+any:on

Apply logical OR boolean test on all items.

Accepts

.a is a +mop.

.b is a $gate of the type $-([key val] ?), where the type of key and val match those of the +mop.

Produces

A ?.

Source

++  any
  ~/  %any
  |=  [a=(tree item) b=$-(item ?)]
  |-  ^-  ?
  ?~  a
    |
  ?|((b n.a) $(a l.a) $(a r.a))

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> (any:myon mymop |=([key=@ val=@] =(1 val)))
%.y

> (any:myon mymop |=([key=@ val=@] =(4 val)))
%.n

---

+apt:on

Verify horizontal and vertical orderings.

Accepts

.a is a +mop.

Produces

A ?.

Source

++  apt
  ~/  %apt
  |=  a=(tree item)
  =|  [l=(unit key) r=(unit key)]
  |-  ^-  ?
  ?~  a  %.y
  ?&  ?~(l %.y (compare key.n.a u.l))
      ?~(r %.y (compare u.r key.n.a))
      ?~(l.a %.y &((mor key.n.a key.n.l.a) $(a l.a, l `key.n.a)))
      ?~(r.a %.y &((mor key.n.a key.n.r.a) $(a r.a, r `key.n.a)))
  ==

Examples

Incorrect order:

> =mymap (malt 1^1 2^2 3^3 ~)
> =myon ((on @ @) gth)
> (apt:myon mymap)
%.n

Correct order:

> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)
> (apt:myon mymop)
%.y

---

+bap:on

Convert to list, right to left

Accepts

.a is a +mop.

Produces

A (list [key val]), where key and val are the types of the keys and values in the +mop.

Source

++  bap
  ~/  %bap
  |=  a=(tree item)
  ^-  (list item)
  =|  b=(list item)
  |-  ^+  b
  ?~  a  b
  $(a r.a, b [n.a $(a l.a)])

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> mymop
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

> (bap:myon mymop)
~[[key=1 val=1] [key=2 val=2] [key=3 val=3]]

---

+del:on

Delete an item from a +mop if it exists, producing its value if it's deleted, and a new +mop.

Accepts

.a is a +mop.

.b is a noun, the type of the keys in .a.

Produces

A cell of a (unit val) and a +mop.

Source

++  del
  ~/  %del
  |=  [a=(tree item) =key]
  ^-  [(unit val) (tree item)]
  ?~  a  [~ ~]
  ?:  =(key key.n.a)
    [`val.n.a (nip a)]
  ?:  (compare key key.n.a)
    =+  [found lef]=$(a l.a)
    [found a(l lef)]
  =+  [found rig]=$(a r.a)
  [found a(r rig)]

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> (del:myon mymop 2)
[[~ 2] {[key=3 val=3] [key=1 val=1]}]

> (del:myon mymop 4)
[~ {[key=3 val=3] [key=2 val=2] [key=1 val=1]}]

---

+dip:on

Stateful partial inorder traversal

Mutates $state on each run of gate .f. Traverses from left to right. Stops when .f produces stop=%.y, or else runs all the way to the end. Each run of .f can replace an item's value or delete the item.

Accepts

+dip is a wet gate that takes .state, which is a $mold. The wet gate produces a dry gate that takes:

• .a is a +mop.

• .state is the initial value for the state.

• .f is a gate of the type $-([state item] [(unit val) stop=? state]). It takes a pair of the current state and a key-value pair from the +mop. It produces a triple of:

  • (unit val) a new value for the current item. If it is null, the item is deleted. If you don't want to modify the value, you just give it back the same one you received.

  • .stop is %.y if traversal should end here, and %.n if it should continue.

  • .state is a new value for the .state.

Produces

A cell of the final .state and the new, possibly modified, +mop.

Source

++  dip
  ~/  %dip
  |*  state=mold
  |=  $:  a=(tree item)
          =state
          f=$-([state item] [(unit val) ? state])
      ==
  ^+  [state a]
  =/  acc  [stop=`?`%.n state=state]
  =<  abet  =<  main
  |%
  ++  this  .
  ++  abet  [state.acc a]
  ++  main
    ^+  this
    ?:  =(~ a)  this
    ?:  stop.acc  this
    =.  this  left
    ?:  stop.acc  this
    =^  del  this  node
    =?  this  !stop.acc  right
    =?  a  del  (nip a)
    this
  ++  node
    ^+  [del=*? this]
    ?>  ?=(^ a)
    =^  res  acc  (f state.acc n.a)
    ?~  res
      [del=& this]
    [del=| this(val.n.a u.res)]
  ++  left
    ^+  this
    ?~  a  this
    =/  lef  main(a l.a)
    lef(a a(l a.lef))
  ++  right
    ^+  this
    ?~  a  this
    =/  rig  main(a r.a)
    rig(a a(r a.rig))
  --

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)

Add them all up:

> ((dip:myon @) mymop 0 |=([stat=@ k=@ v=@] [`v .n (add stat v)]))
[15 {[key=5 val=5] [key=4 val=4] [key=3 val=3] [key=2 val=2] [key=1 val=1]}]

Add them up, stopping when the key is less than 3:

> ((dip:myon @) mymop 0 |=([stat=@ k=@ v=@] [`v (lth 3 k) (add stat v)]))
[5 {[key=5 val=5] [key=4 val=4] [key=3 val=3] [key=2 val=2] [key=1 val=1]}]

Delete items less than three:

> ((dip:myon @) mymop 0 |=([stat=@ k=@ v=@] [?:((lth k 3) ~ `v) .n (add stat v)]))
[15 {[key=5 val=5] [key=4 val=4] [key=3 val=3]}]

---

+gas:on

Put a list of key-value pairs in a +mop.

Accepts

.a is a +mop.

.b is a list of key-value pairs, whose types match those of the +mop.

Source

++  gas
  ~/  %gas
  |=  [a=(tree item) b=(list item)]
  ^-  (tree item)
  ?~  b  a
  $(b t.b, a (put a i.b))

Examples

> =myon ((on @ @) gth)

> (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)
{[key=5 val=5] [key=4 val=4] [key=3 val=3] [key=2 val=2] [key=1 val=1]}

---

+get:on

Get a value at a key or null

Accepts

.a is a +mop.

.b is a noun whose type matches that of the mop's keys.

Produces

A (unit val), where +val is the type of the values of the +mop.

Source

++  get
  ~/  %get
  |=  [a=(tree item) b=key]
  ^-  (unit val)
  ?~  a  ~
  ?:  =(b key.n.a)
    `val.n.a
  ?:  (compare b key.n.a)
    $(a l.a)
  $(a r.a)

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)

> (get:myon mymop 3)
[~ 3]

> (get:myon mymop 7)
~

---

+got:on

Get a value at a key, crashing if it doesn't exist

Accepts

.a is a +mop.

.b is a noun whose type matches that of the mop's keys.

Produces

A noun of the type of the values of the +mop, crashing if the key doesn't exist.

Source

++  got
  |=  [a=(tree item) b=key]
  ^-  val
  (need (get a b))

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)

> (got:myon mymop 3)
3

> (got:myon mymop 7)
dojo: hoon expression failed

---

+has:on

Check for key existence

Accepts

.a is a +mop.

.b is a noun whose type matches that of the mop's keys.

Produces

A ?.

Source

++  has
  ~/  %has
  |=  [a=(tree item) b=key]
  ^-  ?
  !=(~ (get a b))

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)

> (has:myon mymop 3)
%.y

> (has:myon mymop 7)
%.n

---

+lot:on

Take a subset range excluding +start and/or +end, and all elements outside the range.

Accepts

tre is a +mop.

+start is a (unit key), where key is a noun whose type matches the type of the +mop keys. If non-null, this item and all those previous will be excluded.

+end is a (unit key), where key is a noun whose type matches the type of the +mop keys. If non-null, this item and all those after will be excluded.

Produces

A +mop.

Source

++  lot
  ~/  %lot
  |=  $:  tre=(tree item)
          start=(unit key)
          end=(unit key)
      ==
  ^-  (tree item)
  |^
  ?:  ?&(?=(~ start) ?=(~ end))
    tre
  ?~  start
    (del-span tre %end end)
  ?~  end
    (del-span tre %start start)
  ?>  (compare u.start u.end)
  =.  tre  (del-span tre %start start)
  (del-span tre %end end)
  ::
  ++  del-span
    |=  [a=(tree item) b=?(%start %end) c=(unit key)]
    ^-  (tree item)
    ?~  a  a
    ?~  c  a
    ?-  b
        %start
      ?:  =(key.n.a u.c)
        (nip a(l ~))
      ?:  (compare key.n.a u.c)
        $(a (nip a(l ~)))
      a(l $(a l.a))
    ::
        %end
      ?:  =(u.c key.n.a)
        (nip a(r ~))
      ?:  (compare key.n.a u.c)
        a(r $(a r.a))
      $(a (nip a(r ~)))
    ==
  --

Examples

> =myon ((on @ @) lth)
> =mymop (gas:myon *((mop @ @) lth) 2^2 4^4 6^6 8^8 10^10 ~)

> mymop
{[key=2 val=2] [key=4 val=4] [key=6 val=6] [key=8 val=8] [key=10 val=10]}

> (lot:myon mymop `3 ~)
{[key=4 val=4] [key=6 val=6] [key=8 val=8] [key=10 val=10]}

> (lot:myon mymop `4 ~)
{[key=6 val=6] [key=8 val=8] [key=10 val=10]}

> (lot:myon mymop ~ `8)
{[key=2 val=2] [key=4 val=4] [key=6 val=6]}

> (lot:myon mymop `3 `7)
{[key=4 val=4] [key=6 val=6]}

> (lot:myon mymop ~ ~)
{[key=2 val=2] [key=4 val=4] [key=6 val=6] [key=8 val=8] [key=10 val=10]}

> (lot:myon mymop `0 `100)
{[key=2 val=2] [key=4 val=4] [key=6 val=6] [key=8 val=8] [key=10 val=10]}

---

+nip:on

Remove root (for internal use)

Accepts

.a is a +mop.

Produces

A +mop.

Source

++  nip
  ~/  %nip
  |=  a=(tree item)
  ^-  (tree item)
  ?>  ?=(^ a)
  |-  ^-  (tree item)
  ?~  l.a  r.a
  ?~  r.a  l.a
  ?:  (mor key.n.l.a key.n.r.a)
    l.a(r $(l.a r.l.a))
  r.a(l $(r.a l.r.a))

Examples

Note this is for internal use, you would not normally use +nip.

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> mymop
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

> (nip:myon mymop)
{[key=3 val=3] [key=1 val=1]}

---

+pop:on

Produce +head (the leftmost item) and +rest or crash if empty

Accepts

.a is a +mop.

Produces

A cell of +head, the leftmost item, and +rest, the +mop sans its leftmost item. If the +mop was empty, it'll crash.

Source

++  pop
  ~/  %pop
  |=  a=(tree item)
  ^-  [head=item rest=(tree item)]
  ?~  a    !!
  ?~  l.a  [n.a r.a]
  =/  l  $(a l.a)
  :-  head.l
  ?:  |(?=(~ rest.l) (mor key.n.a key.n.rest.l))
    a(l rest.l)
  rest.l(r a(r r.rest.l))

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> mymop
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

> (pop:myon mymop)
[head=[key=3 val=3] rest={[key=2 val=2] [key=1 val=1]}]

> (pop:myon *((mop @ @) gth))
dojo: hoon expression failed

---

+pry:on

Produce the head (leftmost item) or null

Accepts

.a is a +mop.

Produces

A (unit item), where $item is a key-value pair. The unit is null if the mop was empty.

Source

++  pry
  ~/  %pry
  |=  a=(tree item)
  ^-  (unit item)
  ?~  a    ~
  |-
  ?~  l.a  `n.a
  $(a l.a)

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> (pry:myon mymop)
[~ [key=3 val=3]]

> (pry:myon *((mop @ @) gth))
~

---

+put:on

Insert an item

Accepts

.a is a +mop.

key is a noun whose type matches the keys in .a.

val is a noun whose type matches the values in .a.

Produces

A +mop.

Source

++  put
  ~/  %put
  |=  [a=(tree item) =key =val]
  ^-  (tree item)
  ?~  a  [n=[key val] l=~ r=~]
  ?:  =(key.n.a key)  a(val.n val)
  ?:  (compare key key.n.a)
    =/  l  $(a l.a)
    ?>  ?=(^ l)
    ?:  (mor key.n.a key.n.l)
      a(l l)
    l(r a(l r.l))
  =/  r  $(a r.a)
  ?>  ?=(^ r)
  ?:  (mor key.n.a key.n.r)
    a(r r)
  r(l a(r l.r))

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> (put:myon mymop 7 7)
{[key=7 val=7] [key=3 val=3] [key=2 val=2] [key=1 val=1]}

---

+ram:on

Produce tail (rightmost item) or null

Accepts

.a is a +mop.

Produces

A (unit item) where $item is a key-value pair whose type is that of the keys and values in the +mop.

Source

++  ram
  ~/  %ram
  |=  a=(tree item)
  ^-  (unit item)
  ?~  a    ~
  |-
  ?~  r.a  `n.a
  $(a r.a)

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> mymop
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

> (ram:myon mymop)
[~ [key=1 val=1]]

> (ram:myon *((mop @ @) gth))
~

---

+run:on

Apply gate to transform all values in place

Accepts

.a is a +mop.

.b is a gate of $-(val *), where +val is the type of the values in the +mop.

Produces

A +mop.

Source

++  run
  ~/  %run
  |*  [a=(tree item) b=$-(val *)]
  |-
  ?~  a  a
  [n=[key.n.a (b val.n.a)] l=$(a l.a) r=$(a r.a)]

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 ~)

> mymop
{[key=3 val=3] [key=2 val=2] [key=1 val=1]}

> `((mop @ @) gth)`(run:myon mymop succ)
{[key=3 val=4] [key=2 val=3] [key=1 val=2]}

> `((mop @ @t) gth)`(run:myon mymop (cury add 'a'))
{[key=3 val='d'] [key=2 val='c'] [key=1 val='b']}

---

+tab:on

Tabulate a subset with a max count, maybe starting after a certain element.

Accepts

.a is a +mop.

.b is a (unit key). The type of key matches the type of keys in the +mop. This specifies where to start if non-null.

.c is a @ specifying the maximum number of items to return.

Produces

A (list item), where $item is a key-value matching the type of the +mop.

Source

++  tab
  ~/  %tab
  |=  [a=(tree item) b=(unit key) c=@]
  ^-  (list item)
  |^
  (flop e:(tabulate (del-span a b) b c))
  ::
  ++  tabulate
    |=  [a=(tree item) b=(unit key) c=@]
    ^-  [d=@ e=(list item)]
    ?:  ?&(?=(~ b) =(c 0))
      [0 ~]
    =|  f=[d=@ e=(list item)]
    |-  ^+  f
    ?:  ?|(?=(~ a) =(d.f c))  f
    =.  f  $(a l.a)
    ?:  =(d.f c)  f
    =.  f  [+(d.f) [n.a e.f]]
    ?:(=(d.f c) f $(a r.a))
  ::
  ++  del-span
    |=  [a=(tree item) b=(unit key)]
    ^-  (tree item)
    ?~  a  a
    ?~  b  a
    ?:  =(key.n.a u.b)
      r.a
    ?:  (compare key.n.a u.b)
      $(a r.a)
    a(l $(a l.a))
  --

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)

> mymop
{[key=5 val=5] [key=4 val=4] [key=3 val=3] [key=2 val=2] [key=1 val=1]}

> (tab:myon mymop ~ 2)
~[[key=5 val=5] [key=4 val=4]]

> (tab:myon mymop `4 2)
~[[key=3 val=3] [key=2 val=2]]

> (tab:myon mymop `4 100)
~[[key=3 val=3] [key=2 val=2] [key=1 val=1]]

---

+tap:on

Convert to list, left to right

Accepts

.a is a +mop.

Produces

A (list item), where $item is a key-value pair whose type matches those of the +mop.

Source

++  tap
  ~/  %tap
  |=  a=(tree item)
  ^-  (list item)
  =|  b=(list item)
  |-  ^+  b
  ?~  a  b
  $(a l.a, b [n.a $(a r.a)])

Examples

> =myon ((on @ @) gth)
> =mymop (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)

> mymop
{[key=5 val=5] [key=4 val=4] [key=3 val=3] [key=2 val=2] [key=1 val=1]}

> (tap:myon mymop)
~[[key=5 val=5] [key=4 val=4] [key=3 val=3] [key=2 val=2] [key=1 val=1]]

+uni:on

Unify two ordered maps

If the keys overlap and the values are different, the value in mop .b take precedence over the value in mop .a.

Accepts

.a is a +mop.

.b is a +mop.

Produces

A +mop.

Source

++  uni
  ~/  %uni
  |=  [a=(tree item) b=(tree item)]
  ^-  (tree item)
  ?~  b  a
  ?~  a  b
  ?:  =(key.n.a key.n.b)
    [n=n.b l=$(a l.a, b l.b) r=$(a r.a, b r.b)]
  ?:  (mor key.n.a key.n.b)
    ?:  (compare key.n.b key.n.a)
      $(l.a $(a l.a, r.b ~), b r.b)
    $(r.a $(a r.a, l.b ~), b l.b)
  ?:  (compare key.n.a key.n.b)
    $(l.b $(b l.b, r.a ~), a r.a)
  $(r.b $(b r.b, l.a ~), a l.a)
--

Examples

> =myon ((on @ @) gth)
> =a (gas:myon *((mop @ @) gth) 1^1 2^2 3^3 4^4 5^5 ~)
> =b (gas:myon *((mop @ @) gth) 2^20 4^40 6^60 ~)

> (uni:myon a b)
{[key=6 val=60] [key=5 val=5] [key=4 val=40] [key=3 val=3] [key=2 val=20] [key=1 val=1]}

---