Implement monadic ≠ (Unique Mask / Nub Sieve) #10

elcaro commented 2024年04月18日 10:51:42 +02:00

Per the APL Wiki article

Nub Sieve returns a 1 for each major cell in the argument that is unique, and a 0 if it's a duplicate

The article provides an implementation using other primitives, translated to Kap as follows

N ⇐ (2≠/ ̄1,⌈\∪«⍳»(1/⊢))

Which will be used for the following test case examples.

The unique mask on a vector is such that Replicating with the mask produces the same result as ∪

> a ← "abracadabra"
> a ⍪⍥< N a
┌→───────────────────────────────┐
↓@a @b @r @a @c @a @d @a @b @r @a│
│ 1 1 1 0 1 0 1 0 0 0 0│
└────────────────────────────────┘
> ((N a) ⫽ a) ≡ (∪ a)
1

At higher dimensions, such as matrices, I expect it to work on major cells.
Of note, ∪ does not work on a matrix without first converting to a vector of major cells

> ⊢ m ← ? 10 3 ⍴ 2
┌→────┐
↓1 1 1│
│1 0 0│
│1 1 0│
│1 0 0│
│1 0 1│
│1 0 0│
│1 0 1│
│1 0 1│
│0 0 0│
│0 0 1│
└─────┘
> ⊃ ∪ ,/ m
┌→────┐
↓1 1 1│
│1 0 0│
│1 1 0│
│1 0 1│
│0 0 0│
│0 0 1│
└─────┘

I'm not sure if this is a misunderstanding on my part.
In any case, I will demonstrate Unique Mask on a matrix in the same way

> m ,⍥⊂ ⍉< N ,/ m
┌→──────────┐
│┌→────┐ ┌→┐│
│↓1 1 1│ ↓1││
││1 0 0│ │1││
││1 1 0│ │1││
││1 0 0│ │0││
││1 0 1│ │1││
││1 0 0│ │0││
││1 0 1│ │0││
││1 0 1│ │0││
││0 0 0│ │1││
││0 0 1│ │1││
│└─────┘ └─┘│
└───────────┘
> ((N ,/ m) ⫽ ,/ m) ≡⍥⊃ (∪ ,/ m)
1

Per the [APL Wiki article](https://aplwiki.com/wiki/Nub_Sieve) > Nub Sieve returns a 1 for each major cell in the argument that is unique, and a 0 if it's a duplicate The article provides an implementation using other primitives, translated to Kap as follows ```apl N ⇐ (2≠/ ̄1,⌈\∪«⍳»(1/⊢)) ``` Which will be used for the following test case examples. The unique mask on a vector is such that Replicating with the mask produces the same result as `∪` ```apl > a ← "abracadabra" > a ⍪⍥< N a ┌→───────────────────────────────┐ ↓@a @b @r @a @c @a @d @a @b @r @a│ │ 1 1 1 0 1 0 1 0 0 0 0│ └────────────────────────────────┘ > ((N a) ⫽ a) ≡ (∪ a) 1 ``` At higher dimensions, such as matrices, I expect it to work on major cells. Of note, `∪` does not work on a matrix without first converting to a vector of major cells ```apl > ⊢ m ← ? 10 3 ⍴ 2 ┌→────┐ ↓1 1 1│ │1 0 0│ │1 1 0│ │1 0 0│ │1 0 1│ │1 0 0│ │1 0 1│ │1 0 1│ │0 0 0│ │0 0 1│ └─────┘ > ⊃ ∪ ,/ m ┌→────┐ ↓1 1 1│ │1 0 0│ │1 1 0│ │1 0 1│ │0 0 0│ │0 0 1│ └─────┘ ``` I'm not sure if this is a misunderstanding on my part. In any case, I will demonstrate Unique Mask on a matrix in the same way ```apl > m ,⍥⊂ ⍉< N ,/ m ┌→──────────┐ │┌→────┐ ┌→┐│ │↓1 1 1│ ↓1││ ││1 0 0│ │1││ ││1 1 0│ │1││ ││1 0 0│ │0││ ││1 0 1│ │1││ ││1 0 0│ │0││ ││1 0 1│ │0││ ││1 0 1│ │0││ ││0 0 0│ │1││ ││0 0 1│ │1││ │└─────┘ └─┘│ └───────────┘ > ((N ,/ m) ⫽ ,/ m) ≡⍥⊃ (∪ ,/ m) 1 ```

elcaro commented 2024年04月23日 02:16:07 +02:00

Although not the topic of this issue, I mentioned that ∪ did not work on matrices and higher dimensions.

I can confirm 516125711b resolves this issue with matrices, as well has higher dimensions.

⊢ ⍴ ∪ ? 20 2 2 ⍴ 2
┌→─────┐
│12 2 2│
└──────┘
⊢ ⍴ ∪ ? 200 2 2 2 ⍴ 2
┌→────────┐
│140 2 2 2│
└─────────┘

Although not the topic of this issue, I mentioned that `∪` did not work on matrices and higher dimensions. I can confirm 516125711b resolves this issue with matrices, as well has higher dimensions. ```apl ⊢ ⍴ ∪ ? 20 2 2 ⍴ 2 ┌→─────┐ │12 2 2│ └──────┘ ⊢ ⍴ ∪ ? 200 2 2 2 ⍴ 2 ┌→────────┐ │140 2 2 2│ └─────────┘ ```

loke commented 2025年04月24日 08:07:36 +02:00

This has already been implemented. Can you confirm if the implementation conforms to your expectation?

This has already been implemented. Can you confirm if the implementation conforms to your expectation?