120
edits
Unique: Difference between revisions
Jump to navigation
Jump to search
m
12 revisions imported: Migrate from miraheze
Miraheze>Adám Brudzewsky No edit summary |
m (12 revisions imported: Migrate from miraheze) |
||
| (10 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{ | {{Built-in|Unique|∪}}, or '''Nub''', is a [[monadic]] [[set function]] which removes duplicate [[major cells]] from an array. It returns only the distinct cells (those which do not [[match]] an earlier distinct cell) in the order they appeared in the array. | ||
== Examples == | == Examples == | ||
When called on the [[string]] "Mississippi", Unique keeps the first three letters and a later "p", but removes all subsequent occurrences. | When called on the [[string]] "Mississippi", Unique keeps the first three letters and a later "p", but removes all subsequent occurrences. | ||
<source | <source lang=apl> | ||
∪ 'Mississippi' | ∪ 'Mississippi' | ||
Misp | Misp | ||
</source> | </source> | ||
It works on nested arrays as well: | It works on nested arrays as well: | ||
<source | <source lang=apl> | ||
∪ v←'CAT' 'DOG' 'CAT' 'DUCK' 'DOG' 'DUCK' | ∪ v←'CAT' 'DOG' 'CAT' 'DUCK' 'DOG' 'DUCK' | ||
┌───┬───┬────┐ | ┌───┬───┬────┐ | ||
| Line 15: | Line 15: | ||
└───┴───┴────┘ | └───┴───┴────┘ | ||
</source> | </source> | ||
In some languages, such as [[ | In some languages, such as [[J]] and [[Dyalog APL 17.0]] and later, Unique applies to the [[major cells]] of an array, including those with rank greater than 1: | ||
<source | <source lang=apl> | ||
⊢x ← (⍳10)∘.∨2 3 6 | ⊢x ← (⍳10)∘.∨2 3 6 | ||
1 1 1 | 1 1 1 | ||
| Line 41: | Line 41: | ||
To construct the Unique of an array, the major cells are considered in order of increasing [[index]]. Each cell is included if it does not [[match]] any cell which was already included. | To construct the Unique of an array, the major cells are considered in order of increasing [[index]]. Each cell is included if it does not [[match]] any cell which was already included. | ||
The array matching is subject to [[tolerant comparison]]. In the intolerant case, that is, when equality is [ | The array matching is subject to [[tolerant comparison]]. In the intolerant case, that is, when equality is [[wikipedia:Transitive_relation|transitive]], a cell is included if and only if it does not match any other cell which appears earlier in the array. That's because all the discarded duplicate cells must have matched an earlier included cell; if equality is transitive then a cell which matches the duplicate would also match the earlier cell. | ||
=== 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 which contains an element matching every element of the original array, but a less careful definition (for example, excluding every element which matches an earlier one) would fail to satisfy this property. | 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 which contains an element matching every element of the original array, but a less careful definition (for example, excluding every element which matches an earlier one) would fail to satisfy this property. | ||
<source | <source lang=apl> | ||
⎕CT←1e¯14 | ⎕CT←1e¯14 | ||
⎕PP←18 ⍝ Print all digits | ⎕PP←18 ⍝ Print all digits | ||
| Line 64: | Line 64: | ||
== APL model == | == APL model == | ||
For [[Vector|vectors]] the following implementation based on [[Union]] can be used. It repeatedly adds cells of the argument to an accumulated unique vector < | For [[Vector|vectors]] the following implementation based on [[Union]] can be used. It repeatedly adds cells of the argument to an accumulated unique vector <source lang=apl inline>u</source>, using Union so that duplicate cells are never added. | ||
<source | <source lang=apl> | ||
VecUnique ← { | VecUnique ← { | ||
u ← 0↑⍵ | u ← 0↑⍵ | ||
| Line 73: | Line 73: | ||
{{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]]. 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: | ||
<source | <source lang=apl> | ||
VecUnique ← {⊃∪⍨/⌽⍵} | VecUnique ← {⊃∪⍨/⌽⍵} | ||
</source> | </source> | ||
{{Works in|[[Dyalog APL]],[[ngn/apl]]}} | {{Works in|[[Dyalog APL]],[[ngn/apl]]}} | ||
It can be modified to obtain a full model for Unique by enclosing enough times, and converting scalars to vectors with [[Replicate]] at the end: | It can be modified to obtain a full model for Unique by enclosing enough times, and converting scalars to vectors with [[Replicate]] at the end: | ||
<source | <source lang=apl> | ||
Unique ← {1/↑↑⌽∪/⌽⊂∘⊂⍤¯1⊢⍵} | Unique ← {1/↑↑⌽∪/⌽⊂∘⊂⍤¯1⊢⍵} | ||
</source> | </source> | ||
{{Works in|[[Dyalog APL]]}} | {{Works in|[[Dyalog APL]]}} | ||
While the model < | While the model <source lang=apl inline>{((⍳≢⍵)=(⍵⍳⍵))⌿⍵}</source>, based on [[Nub Sieve]], is often described as an implementation of Unique, it does not correctly handle [[tolerant comparison]]. 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 == | ||
| Line 91: | Line 91: | ||
Every major cell in the argument to Unique matches at least one cell in its result: if a cell didn't match any cells in the Unique, then it would have been included itself. A cell may match multiple cells if it matches both but they do not match each other. | Every major cell in the argument to Unique matches at least one cell in its result: if a cell didn't match any cells in the Unique, then it would have been included itself. A cell may match multiple cells if it matches both but they do not match each other. | ||
== | == External links == | ||
=== Documentation === | |||
* [http://help.dyalog.com/latest/index.htm#Language/Primitive%20Functions/Unique.htm Dyalog] | |||
* [http://microapl.com/apl_help/ch_020_020_392.htm APLX] | |||
* [https://www.jsoftware.com/help/dictionary/d221.htm J Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/tildedot J NuVoc] (as <source lang=apl inline>~.</source>) | |||
{{APL built-ins}} | {{APL built-ins}} | ||