cmp ← ⍺ (relat ##.lex) ⍵        ⍝ Lexicographical comparison of arrays ⍺ and ⍵.

Comparison of arrays ⍺ and ⍵ using relational function < ≤ = ≥ > ≠. Result [cmp]
is a boolean scalar 0 or 1.

Lex  imposes an ordering on the set of all arrays in the sense that if ⍺≢⍵, then
either  (⍺<lex ⍵)  or (⍺>lex ⍵) but not both. Compare this with a more naïve ap-
proach, which compared the enlist of each of its arguments; in this case neither
(1<cmp,1) nor (1>cmp,1) so the strong ordering property would not hold.

Lexicographical  comparison might be useful, for example, when storing arrays on
file in a binary tree.

Bug: Lex can not compare (arrays containing) namespace refs or ⎕OR objects. Such
comparisons generate NONCE and DOMAIN ERROR, respectively.

The criteria for considering one array "greater" or "less than" another are open
to  debate. The following rules are intended to provide an intuitive ordering on
arrays of arbitrary shape and depth.

In the following:

    << means "is lexicographically less than" and
    <= means "because"  (c.f. => "implies).

- Numeric scalars are compared on magnitude in the usual way.

    ¯3.4 << 2

- Character scalars are compared using their positions in ⎕AV.

    ⎕av[⎕io] << ' '

- Numeric  scalars  are deemed less than character scalars. This is a completely
  arbitrary  choice,  although  it  seems to be supported by Taxi companies, who
  favour names such as "1st Aardvark".

    3 << '2'                    ⍝ numbers sort before characters.

If  either argument is of rank greater than 1, the comparison is applied recurs-
ively between the vectors formed by enclosing trailing axes of each of them.

Otherwise,  if  either array is a scalar, the comparison is applied to its ravel
and the original rank used as a tie-breaker.

     2 << ,3                    ⍝ value overrides rank.
    ,2 <<  3                    ⍝   ..     ..      ..
     4 << ,4                    ⍝ rank used as tie-breaker.

Otherwise, we are comparing (possibly nested) vectors. If both vectors are null,
the  comparison  is  applied  recursively  between their respective prototypical
items.

    ⍬ << ''                     ⍝ <=    0 << ' '

Otherwise,  if  all items in the shorter vector match corresponding items in the
longer, the shorter one is deemed the lesser.

    3↑⎕av << 4↑⎕av

    ⍬ << 1 2 3

Otherwise, the first non-matching items are compared recursively.

    1 2 3 << 1 4 5              ⍝ <=    2 << 4

    1 (2 3) 4  << 1 4 5         ⍝ <=    2 3 << 4        <=  2 << 4

(muse:
    Placing an ordering on arrays raises the question of the cardinality of (how
    big is) the set of all APL arrays ignoring the limitations of any particular
    implementation.  We can simplify this by noting that the number of (possibly
    nested)  arrays is the same as the number of _simple_vectors_ because we can
    define  a unique mapping from any array to a unique simple vector by design-
    ing a transfer form such as ⎕TF. Given that each item of a simple vector may
    be  any real number or one of a finite number of characters, we wind up with
    a cardinality of |R×R×...×R|. As the number of Rs is countable, this set has
    the  same  cardinality  as R. Note that implementations that support complex
    numbers  don't  increase  this  number,  as the number of complex numbers is
    |R×R|, which is the same as |R|.
)

Examples:

    'hello' <lex 'world'
1
    'hello' 'world' >lex 'hello' 'sailor'
1
    3 <lex ,3
1
    ⎕a <lex ⊂⎕a
1
    1(2 3) =lex ⊃,∘⊂/⍳3
1
    '' >lex ⍬
1

Back to: contents

Back to: Dyalog APL

Trouble seeing APL font?