2f: Noun Ordering

++aor

Alphabetical order

Computes whether a and b are in alphabetical order, producing a flag. Orders atoms before cells, and atoms in ascending LSB order.

Accepts

a is a noun.

b is a noun.

Produces

A flag.

Source

++  aor
  ~/  %aor
  |=  [a=* b=*]
  ^-  ?
  ?:  =(a b)  &
  ?.  ?=(@ a)
    ?:  ?=(@ b)  |
    ?:  =(-.a -.b)
      $(a +.a, b +.b)
    $(a -.a, b -.b)
  ?.  ?=(@ b)  &
  |-
  =+  [c=(end 3 a) d=(end 3 b)]
  ?:  =(c d)
    $(a (rsh 3 a), b (rsh 3 b))
  (lth c d)

Examples

> (aor 'a' 'b')
%.y
> (aor 'b' 'a')
%.n
> (aor 'a' 'a')
%.y

> (aor 1 2)
%.y
> (aor 2 1)
%.n

> (aor ['a' ~] 'b')
%.n
> (aor 'b' ['a' ~])
%.y

> (aor ['a' ~] ['b' ~])
%.y
> (aor ['b' ~] ['a' ~])
%.n

> (aor "abca" "abcz")
%.y
> (aor "abcz" "abca")
%.n

> (aor 0b1011 0b1010)
%.n
> (aor 0b1010 0b1011)
%.y

> (aor [1 2] [2 1])
%.y
> (aor [2 1] [1 2])
%.n

Note the possible differences with +dor due to comparing one byte at a time:

> (aor 0b1001.0000.0000 0b1000.1000.0000)
%.y
> (dor 0b1001.0000.0000 0b1000.1000.0000)
%.n

Discussion

This is different than +dor in that it compares atoms one byte at a time, while +dor compares whole atoms at once. Note that because it simply compares bytes, it doesn't account for multi-byte UTF-8 characters and the like.

++dor

Depth order

Computes whether a and b are in ascending tree depth order, producing a flag. Orders atoms before cells, and atoms in ascending numerical order.

Accepts

a is a noun.

b is a noun.

Produces

A flag.

Source

++  dor
  ~/  %dor
  |=  [a=* b=*]
  ^-  ?
  ?:  =(a b)  &
  ?.  ?=(@ a)
    ?:  ?=(@ b)  |
    ?:  =(-.a -.b)
      $(a +.a, b +.b)
    $(a -.a, b -.b)
  ?.  ?=(@ b)  &
  (lth a b)

Examples

> (dor 1 2)
%.y

> (dor 2 1)
%.n

> (dor ~[1 2 3] ~[1 2 4])
%.y

> (dor ~[1 2 4] ~[1 2 3])
%.n

> (dor `(list @)`~[99 100 10.000] ~[99 101 10.000])
%.y

> (dor ~[99 101 10.999] `(list @)`~[99 100 10.000])
%.n

Note the possible difference with +aor due to comparing whole atoms rather than one byte at a time:

> (aor 0b1001.0000.0000 0b1000.1000.0000)
%.y
> (dor 0b1001.0000.0000 0b1000.1000.0000)
%.n

Discussion

If a and b are both atoms, dor is equivalent to lte. If they're cells, dor recurses on the heads, and then if the heads are the same it checks the tails.

If one sample is a cell and the other is an atom, the cell sample is treated as "greater."

++gor

Mug order

Computes whether of (mug a) and (mug b) are in ascending numeric order, producing a flag. If the mug hashes are equal, a and b are compared by dor instead.

mug is the the 31-bit nonzero FNV-1a hash algorithm.

Accepts

a is a noun.

b is a noun.

Produces

A flag.

Source

++  gor
  ~/  %gor
  |=  [a=* b=*]
  ^-  ?
  =+  [c=(mug a) d=(mug b)]
  ?:  =(c d)
    (dor a b)
  (lth c d)

Examples

> (gor 'd' 'c')
%.y

> 'd'
'd'
> 'c'
'c'

> `@ud`'d'
100
> `@ud`'c'
99

> (mug 'd')
1.628.185.714
> (mug 'c')
1.712.073.811

> (gor 'd' 'c')
%.y
> (gor 'c' 'd')
%.n

> (gor "foo" "bar")
%.n

> (gor (some 10) `(list @)`[1 2 3 ~])
%.n

Discussion

maps use gor on the key for horizontal ordering and mor for vertical order. maps only look at the keys (the head of the key-value pair elements) for ordering.

++mor

(more) mug order

Computes whether the double-hashes (mug (mug a)) and (mug (mug b)) are in ascending numeric order, producing a flag. If the double-mug hashes are equal, a and b are compared by dor instead.

mug is the the 31-bit nonzero FNV-1a hash algorithm.

Accepts

a is a noun

b is a noun

Produces

A flag.

Source

++  mor
  ~/  %mor
  |=  [a=* b=*]
  ^-  ?
  =+  [c=(mug (mug a)) d=(mug (mug b))]
  ?:  =(c d)
    (dor a b)
  (lth c d)

Examples

    > (mor 'f' 'g')
    %.y

    > [(mug 'f') (mug 'g')]
    [1.661.740.952 1.644.963.335]

    > [(mug (mug 'f')) (mug (mug 'g'))]
    [261.421.509 1.861.258.547]

    > (mor 'a' 'z')
    %.n

    > (mor 43.326 41.106)
    %.n

Discussion

Maps, sets, and queues all use mor to check for vertical ordering. Maps and sets also use gor for horizontal order, but queues use vertical ordering alone.

Since hashing removes correlation, double-mugging with mor removes correlation with single-mugged gor. Vertical order becomes uncorrelated with horizontal order.