2f: Noun Ordering • Documentation • urbit.org

2f: Noun Ordering

`++aor`

Alphabetical order

Computes whether a and b are in alphabetical order, producing a flag.

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 1 a) d=(end 3 1 b)]
      ?:  =(c d)
        $(a (rsh 3 1 a), b (rsh 3 1 b))
      (lth c d)

Examples

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

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

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

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

    > (aor "bar" "foo")
    %.y

    > (aor "abcdefz" "abcdefa")
    %.n

    > (aor "abcdefa" "abcdefz")
    %.y

    > (aor 10.000 17.000)
    %.y

    > (aor 10 9)
    %.n

`++dor`

Numeric order

Computes whether a and b are in ascending numeric order, producing a flag.

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

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`

Hash 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 vor for vertical order. maps only look at the keys (the head of the key-value pair elements) for ordering.

`++hor`

Horizontal hash order

If a and b are atoms, they are computed as samples of gor, producing a flag.

If a and b are cells, hor checks to see if their heads are equal. If their heads are equal, gor is computed on their tails, producing a flag. If their heads are not equal, gor is computed on their heads, producing a flag.

If a is an atom and b is not, then %.y is produced. If b is an atom and a is not, %.n is produced.

Accepts

a is a noun.

b is a noun.

Produces

A flag.

Source

++  hor
      ~/  %hor
      |=  [a=* b=*]
      ^-  ?
      ?:  ?=(@ a)
        ?.  ?=(@ b)  &
        (gor a b)
      ?:  ?=(@ b)  |
      ?:  =(-.a -.b)
        (gor +.a +.b)
      (gor -.a -.b)

Examples

    > (hor . 1)
    %.n

    > (hor 1 2)
    %.y

    > (hor "abc" "cba")
    %.y

    > (hor 'c' 'd')
    %.n

    > (hor 100 [1 1])
    %.y

    > (hor [1 1] 100)
    %.n

    > (hor 500.000.000 "foo")
    %.y

    > (hor "foo" 500.000.000)
    %.n

    > (hor 0 "foo")
    %.y

    > (gor `(list @)`[0 ~] 1)
    %.n

    > (hor `(list @)`[50 500 5.000 ~] 1)
    %.n

Discussion

Sets (+set, +in) use hor for their horizontal order and vor for their vertical order. See apt:in to see how a set verifies its correctness. vor is used to verify.

`++lor`

Leg order

Computes whether the corresponding legs of a and b are in ascending numeric order, producing a flag.

Accepts

a is a noun.

b is a noun.

Accepts

A flag.

Source

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

Examples

    > (lor 1 2)
    %.y

    > (lor 2 1)
    %.n

    > (lor 9 [1 2])
    %.y

    > (lor `(list @)`[1 2 3 ~] `(list @)`[1 2 3 4 ~])
    %.y

    > (lor `(list @)`[1 2 3 ~] `(list @)`[1 2 2 ~])
    %.n

    > (lor `(list @)`[1 2 3 ~] `(list @)`[2 2 ~])
    %.y

    > (lor [2 2 5] [1 5 9 8])
    %.n

    > (lor [1 5 8] [1 5 9 8])
    %.y

    > (lor [1 2 3] [1 2])
    !! exit

Discussion

lor is no longer used internally.

`++vor`

Vertical 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

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

Examples

    > (vor '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]

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

    > (vor 43.326 41.106)
    %.n

Discussion

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

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

2e: Insecure Hashing

2g: Unsigned Powers