precedes ← this ##.le that ⍝ Total array ordering (TAO) comparison.
Inspired by Roger Hui, [le] "less than or equal" defines a Total Order on APL
arrays. For any arrays A, B and C:
(A le B) ∧ (B le A) : A eq B ⍝ antisymmetry
(A le B) ∧ (B le C) : A le C ⍝ transitivity
(A le B) ∨ (B le A) ⍝ totality.
See: http://en.wikipedia.org/wiki/Total_order
See: http://www.jsoftware.com/jwiki/Essays/The_TAO_of_J
Given any two arrays, [le] tells us which "precedes or is equal to" the other.
In particular it may be used to compare arrays of:
differing type: '6' le 6
differing rank: 3 le ,3
differing shape: 5 4 le 5 4 3
differing depth: (⊂⍳2)le ⊂⊂⍳2
complex numbers: 7j8 le 8j7
namespaces: # le ⎕SE
objects: le/{⎕new'Form'(⊂'Caption'⍵)}¨'Hello' 'World'
The comparison proceeds in the following order:
- If the ranks differ, the lesser array is extended with leading 1-axes.
If the resulting arrays match, the original ranks are used as a tie-breaker.
¯¯¯¯¯
- If the shapes differ, the arrays are extended to conform with (⎕UCS 0) items.
If the resulting arrays match, the original shapes are used as a tie-breaker.
¯¯¯¯¯¯
- The resulting arrays are compared item-wise in ravel order. Empty arrays are
compared on their prototypical items.
- "Atomic" items are compared by type: <char> le <number> le <ref> le <⎕OR>,
where "atomic" implies having depth=0 or being the ⎕OR of a function, operator
or namespace, which has depth=1 (and rank=0).
- Otherwise, if the types match:
Characters are compared using ⍋,
Numbers are compared on their real part, followed by their imaginary part,
Namespaces are compared recursively in order of their:
Type property,
Vector of symbol table (name class value) triples, where:
the value of an array is itself,
the value of a function or operator is its ⎕NR,
the value of the ⎕OR of a function or operator is its ⎕NR∘⎕FX,
the value of the ⎕OR of a namespace is its ⎕NS,
The values of namespace-scope system variables,
Property names and values.
Regarding the antisymmetry condition:
(A le B) ∧ (B le A) : A eq B ⍝ antisymmetry
When comparing refs, "eq" is not the same as primitive function match (≡): two
refs match _only_ if they reference the _same_ namespace, while [le] would judge
them equal if their contents and properties match:
A B ← ⎕ns¨ '' '' ⍝ two namespaces.
(A le B) ∧ (B le A) ⍝ A eq B
1
A ≡ B ⍝ A ≢ B
0
Rationale:
The order that [le] imposes on arrays is to some extent arbitrary but is intend-
ed to be intuitive. Here are the choices implicit in the coding:
[1] Item value is more significant than shape. For example:
'abc ' le 'xyz' ⍝ even though (⍴⍺)>⍴⍵
'abc' le 'z' ⍝ even though (⍴⍴⍺)>⍴⍴⍵
(1 3⍴'abc') le 'xyz' ⍝ .. .. ..
[2] Characters sort before
numbers, which sort before
refs, which sort before
⎕ORs.
[3] When comparing complex numbers, real part is more significant than imaginary
part.
[4] Within a namespace,
user-specified names and values are more significant than
system variable values, which are more significant than
property values.
[5] Within a namespace, (name class value) triples are compared with each other,
rather than having names, classes and values compared consecutively:
x y←⎕ns¨'' '' ⍝ new namespaces
x.a←8 ⍝ variables in x
y.a←3 ⋄ y.b←4 ⍝ and y
x le y ⍝ because (⊂'a'2 8) (~le) ('a'2 3)('b'2 4)
0
x.(⎕nl 2) le y.(⎕nl 2) ⍝ notwithstanding the order of namelists.
1
Namespace Reference Cycles
--------------------------
Namespaces structures may contain reference cycles as in x.p←x or (x y).q←(y x).
Apart from avoiding infinite recursion problems when processing such structures,
we need to bestow a relative order upon them. What is (x le y) in the second ex-
ample above? The approach taken in [le] comes from a suggestion by Nick Nikolov.
The depth-first search [acmp] of left and right argument graphs keeps a note (in
⍺⍺) of namespaces already visited. The search continues to follow any cycles un-
til [a], a "regular" difference is discovered between the two arguments or [b],
previously visited vertices are encountered in both graphs. In the latter case,
the one with the shorter cycle (∇ ⍺⍺⍳¨⍺⍺) is deemed the lesser.
⍝ ┌x────┐←┐
(x←⎕ns ⍬).(x←⎕ns ⍬).(x←##) ⍝ │┌x──┐│ │
⍝ ││ x→───┘
⍝ │└───┘│
⍝ └─────┘
⍝ ┌y──────┐←┐
(y←⎕ns ⍬).(y←⎕ns ⍬).(y←⎕ns ⍬).(y←##.##) ⍝ │┌y────┐│ │
⍝ ││┌y──┐││ │
⍝ │││ y→────┘
⍝ ││└───┘││
⍝ │└─────┘│
⍝ └───────┘
x y ≡ x.x.x y.y.y.y ⍝ 3- and 4-cycles
1
x y ∘.le x y ⍝ Total ordering
1 1
0 1
Examples:
4 le 5 ⍝ simple scalar comparison: 4≤5.
1
'ab' le 'abc' ⍝ differing shape: prefix precedes suffix (AB)
1
3 le ,2 ⍝ differing rank: compare items.
0
(,3) le 3 ⍝ matching items: compare rank.
0
'3' le 3 ⍝ chars precede numbers.
1
3j4 le 4j3 ⍝ real-part trumps imaginary-part
1
# le ⎕se ⍝ #.Type ≤ ⎕se.Type
1
'xy'⎕ns¨⊂'' ⍝ two namespaces.
x.(a c)←1 3 ⍝ with names a c
y.(a b)←1 4 ⍝ ... and a b
x le y ⍝ (a c ...) supersedes (a b ...)
0
x.b←2 ⍝ new name b in x
x le y ⍝ (a:1 b:2 ...) precedes (a:1 b:4 ...)
1
Q ← {1≥≢⍵:⍵ ⋄ s←⍵ ⍺⍺ ⍵⌷⍨⊂?≢⍵ ⋄ (∇ ⍵⌿⍨0>s)⍪(⍵⌿⍨0=s)⍪(∇ ⍵⌿⍨0<s)} ⍝ (RKWH)
qsort ← {⍺⍺{(⍵ ⍺⍺ ⍺)-(⍺ ⍺⍺ ⍵)}⍤¯1 999 Q ⍵}
display le qsort 3(,3)'3'(,'3') ⍝ char << num; scalar << vector
┌→────────────┐
│ ┌→┐ ┌→┐ │
│ 3 │3│ 3 │3│ │
│ - └─┘ └~┘ │
└∊────────────┘
ip←+.× ⍝ named function.
stuff ← ⎕SE ⍬ # (⎕or'ip') '' ⍬ ⍝ assorted stuff.
display le qsort stuff ⍝ sorted stuff.
┌→────────────────────────┐
│ ┌⊖┐ ┌⊖┐ ┌⊖┐ ┌───┐ │
│ │ │ │0│ │0│ # ⎕SE │+.×│ │
│ └─┘ └~┘ └~┘ └∇──┘ │
└∊────────────────────────┘
⍝ Other relationships can be derived from le:
cmp ← {⍺⍺/le/¨1 0⌽¨⊂⍺ ⍵} ⍝ comparison
ge ← ≥cmp ⍝ greater or equal
eq ← =cmp ⍝ equal
ne ← ≠cmp ⍝ not equal
lt ← <cmp ⍝ less than
gt ← >cmp ⍝ greater than
(⎕ns'') ≡ ⎕ns'' ⍝ distinct spaces don't match.
0
(⎕ns'') eq ⎕ns'' ⍝ distinct spaces deemed equal.
1
0 1 ∘.ge 0 1 ⍝ truth-table for ge.
1 0
1 1
grade←{| ⊢/↑ ⍺⍺ qsort ⍵ {⍺ ⍵}¨ ⍵⍵ ⍳⍴⍵} ⍝ grade up/down.
gu ← le grade + ⍝ grade-up ⍋
gd ← ge grade - ⍝ grade-down ⍒
gu 3 1 4 1 5 ⍝ grade-up of numeric vector.
2 4 1 3 5
gd 3 1 4 1 5 ⍝ grade-down of numeric vector.
5 3 1 2 4
gu 3j5 3j4 4j3 3j4 ⍝ complex number grade-up.
2 4 1 3
display stuff ⍝ assorted stuff.
┌→────────────────────────┐
│ ┌⊖┐ ┌───┐ ┌⊖┐ ┌⊖┐ │
│ ⎕SE │0│ # │+.×│ │ │ │0│ │
│ └~┘ └∇──┘ └─┘ └~┘ │
└∊────────────────────────┘
gu stuff ⍝ grade-up of stuff.
5 2 6 3 1 4
gd stuff ⍝ grade-down of stuff.
4 1 3 2 6 5
q ← 'to' 'be' 'or' 'not' 'to' 'be' ⍝ that is the question.
gu q ⍝ grade-up of char vectors ...
2 6 4 3 1 5
⍋∘↑ q ⍝ ... concurs with ⍋∘↑
2 6 4 3 1 5
nvs ← (1 1) (2 3 4) (1 1) (3 1) (1 2) ⍝ numeric vectors.
gd nvs ⍝ grade-down ...
4 2 5 1 3
⍒∘↑ nvs ⍝ ... concurs with ⍒∘↑
4 2 5 1 3
See also: refmatch logic truth_tables
Back to: contents
Back to: Workspaces