2,954
edits
Unique: Difference between revisions
Jump to navigation
Jump to search
Simpler fix for length-1 case
m (Text replacement - "</source>" to "</syntaxhighlight>") Tags: Mobile edit Mobile web edit |
(Simpler fix for length-1 case) |
||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 45: | Line 45: | ||
=== Tolerant comparison === | === Tolerant comparison === | ||
The following example shows why we must be careful about how cells are matched when tolerant comparison is involved. Here we produce a vector in which the first and second elements match, as do the second and third, but the first and third elements do not! Unique produces an array | The following example shows why we must be careful about how cells are matched when tolerant comparison is involved. Here we produce a vector in which the first and second elements match, as do the second and third, but the first and third elements do not! Unique produces an array Z such that each element of the original array matches at least one element of Z, but a less careful definition (for example, excluding every element which matches an earlier one) would fail to satisfy this property. | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
⎕CT←1e¯14 | ⎕CT←1e¯14 | ||
| Line 64: | Line 64: | ||
== History == | == History == | ||
The function Nub was proposed in | The function Nub was proposed in [[Ken Iverson|Iverson]]'s 1978 [[Operators and Functions]] along with other set functions including [[Union]], [[Intersection]], and [[Difference]]. There it had the symbol <syntaxhighlight lang=apl inline>∪</syntaxhighlight> and definition <syntaxhighlight lang=apl inline>∪w</syntaxhighlight> {{←→}} <syntaxhighlight lang=apl inline>((⍳⍴w)=w⍳w)/w←,w</syntaxhighlight>. It was implemented as part of [[STSC]]'s [[NARS]] in 1981 with the name Unique and the same definition, except that the argument was restricted to be a vector or scalar.<ref>Cheney, Carl. ''APL*PLUS Nested Arrays Reference Manual. [[STSC]] Inc. 1981.</ref> Later APLs such as [[Dyalog APL]] generally adopted this version of the primitive, and it is featured in the [[ISO/IEC 13751:2001]] standard. Dyalog extended Unique to higher-rank arrays in [[Dyalog APL 17.0]], following the much earlier extension made by [[J]]. | ||
Iverson continued to refine his definition of Nub. He included it in his [[Rationalized APL]] specification with no changes in 1983, but modified it to work on [[major cell]]s (thus aligning it with [[leading axis theory]]) in his 1987 [[A Dictionary of APL]]. Iverson's dictionary also changed the symbol for Nub to <syntaxhighlight lang=apl inline>↑</syntaxhighlight>, added the functions [[Nub Sieve]] (<syntaxhighlight lang=apl inline>≠</syntaxhighlight>) and [[Nub in]] (<syntaxhighlight lang=apl inline>=</syntaxhighlight>), and defined Nub in terms of Nub Sieve. These definitions were adopted by [[IPSA]] in the [[SHARP APL]] successor [[SAX]]. [[J]] uses similar definitions: its Nub-related functions are Nub (<syntaxhighlight lang=j inline>~.</syntaxhighlight>), [[Nub Sieve]] (<syntaxhighlight lang=j inline>~:</syntaxhighlight>), and [[Self-classify]] (<syntaxhighlight lang=j inline>=</syntaxhighlight>). However, Self-classify is indicated as deprecated in J's NuVoc because its result can be much larger than its argument. | Iverson continued to refine his definition of Nub. He included it in his [[Rationalized APL]] specification with no changes in 1983, but modified it to work on [[major cell]]s (thus aligning it with [[leading axis theory]]) in his 1987 [[A Dictionary of APL]]. Iverson's dictionary also changed the symbol for Nub to <syntaxhighlight lang=apl inline>↑</syntaxhighlight>, added the functions [[Nub Sieve]] (<syntaxhighlight lang=apl inline>≠</syntaxhighlight>) and [[Nub in]] (<syntaxhighlight lang=apl inline>=</syntaxhighlight>), and defined Nub in terms of Nub Sieve. These definitions were adopted by [[IPSA]] in the [[SHARP APL]] successor [[SAX]]. [[J]] uses similar definitions: its Nub-related functions are Nub (<syntaxhighlight lang=j inline>~.</syntaxhighlight>), [[Nub Sieve]] (<syntaxhighlight lang=j inline>~:</syntaxhighlight>), and [[Self-classify]] (<syntaxhighlight lang=j inline>=</syntaxhighlight>). However, Self-classify is indicated as deprecated in J's NuVoc because its result can be much larger than its argument. | ||
| Line 80: | Line 80: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]]}} | {{Works in|[[Dyalog APL]]}} | ||
The accumulation above resembles a [[reduction]]—in fact, it is a reverse [[insertion]]. The following implementation written with Reduce works for [[simple]] vectors in [[Nested array model|nested]] APLs because reduction is equivalent to insertion followed by [[Enclose]] on such vectors: | The accumulation above resembles a [[reduction]]—in fact, it is a reverse [[insertion]] (reversing is necessary when using tolerant comparison as cells need to be added in order). The following implementation written with Reduce works for non-empty [[simple]] vectors in [[Nested array model|nested]] APLs because reduction is equivalent to insertion followed by [[Enclose]] on such vectors: | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
VecUnique ← {⊃∪⍨/⌽⍵} | VecUnique ← {⊃∪⍨/⌽⍵} | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]],[[ngn/apl]]}} | {{Works in|[[Dyalog APL]],[[ngn/apl]]}} | ||
It | It is extended to empty, nested, and arbitrary rank inputs as follows: | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
m ← {0=≢⍵:⍵ ⋄ ↑,⊃∪⍨/⌽⊂¨⊂⍤¯1⊢⍵} | |||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]]}} | {{Works in|[[Dyalog APL]]}} | ||
The guard checks for length zero because <syntaxhighlight lang=apl inline>∪⍨</syntaxhighlight> lacks an [[identity element]]. The [[Replicate]] call <syntaxhighlight lang=apl inline>1/⍵</syntaxhighlight> converts a scalar to a vector, and the encloses ensure that the array added by Union is always a scalar. | |||
While the model <syntaxhighlight lang=apl inline>{((⍳≢⍵)=(⍵⍳⍵))⌿⍵}</syntaxhighlight>, based on [[Nub Sieve]], is often described as an implementation of Unique, it does not correctly handle [[tolerant comparison]].<ref>Hui, Roger. [https://dyalog.tv/Dyalog17/?v=fPWky9IOG40 Tolerant Unique]. [[Dyalog '17]].</ref> A correct implementation of Nub Sieve could be used to implement Unique, but writing such an implementation is no easier than implementing Unique directly. | If modelling the primitive via Union is not desirable due to how similar these two primitives are, it is possible to replace this particular usage of union (not generally, as it relies on the right argument being scalar) as follows: | ||
<syntaxhighlight lang=apl> | |||
m ← {0=≢⍵:⍵ ⋄ ↑,⊃{⍺,(∧/⍺≢¨⍵)/⍵}⍨/⌽⊂¨⊂⍤¯1⊢⍵} | |||
</syntaxhighlight> | |||
{{Works in|[[Dyalog APL]]}} | |||
While the model <syntaxhighlight lang=apl inline>{((⍳≢⍵)=(⍵⍳⍵))⌿⍵}</syntaxhighlight> for vector arguments, based on [[Nub Sieve]], is often described as an implementation of Unique, it does not correctly handle [[tolerant comparison]].<ref>Hui, Roger. [https://dyalog.tv/Dyalog17/?v=fPWky9IOG40 Tolerant Unique]. [[Dyalog '17]].</ref> A correct implementation of Nub Sieve could be used to implement Unique, but writing such an implementation is no easier than implementing Unique directly. | |||
== Properties == | == Properties == | ||