Lesson 46 - unique mask ≠ and constant ⍨ – Conversation in The APL Orchard

Adám

Jul 14, 2020 14:30

Welcome to APL Cultivation! Today's lesson will be a continuation of the first season in that we'll catch up on new things added since then.

AviFS

@Adám How does that make it more first than second season?

Adám

@AviFS Because the first season was on core language features and usage, while the second went into depth on specific subjects.

AviFS

@Adám I see!

Adám

Much of this will be repeating things I've said in my webinar series, "Language Features of Dyalog version 18.0 in Depth", but this format gives people a text to search and reference, while at the same time being more interactive for those that are here.

AviFS

How many of these do you expect to do?

It's taking 4 webinars. How much of it are we doing today?

Adám

Jul 14, 2020 14:34

We'll see how much ground we can cover. The webinars are only 30-45 mins each, while this is 90. On the other hand, questions and discussions are more likely here.

So, without further ado. Let's have a second look at ≠ which is now monadic as well as dyadic.

The monadic function, which is called Unique Mask or Nub Sieve, isn't very connected to the dyadic form (unequal).

In the first season, we covered Unique, to which this very much relates.

Unique returns a subset of the major cells of its argument.

Unique mask returns a Boolean vector which, when used as left argument to ⌿ and with the original argument as right argument, returns the same as Unique would on the original argument:

      ∪'mississippi'
misp
      ≠'mississippi'
1 1 1 0 0 0 0 0 1 0 0
      {(≠⍵)⌿⍵}'mississippi'
misp

Why would we want such a function?

AviFS

If you could start all over with backward compatibility being a non-issue, would you replace both ∩∪ with their nub-seive style equivalents?

Adám

@AviFS The dyadic functions?

AviFS

@Adám Sorry, was midway typing about something else

@Adám No, monadic

Adám

@AviFS What is monadic ∩?

AviFS

What I was typing: Just like with sorting, one has to do the whole {⍵[⍋⍵]} idiom, which is then optimized of course, just to keep the larger more general functionality of ⍋⍒

@Adám True...

Sorry, I meant dyadic \embarassment

Hold on, no I really confused myself

Forget ∩

Adám

Jul 14, 2020 14:43

@AviFS There's no such thing as a mask replacement for the dyadic set functions, unless the mask would apply to the concatenation of the arguments. I guess that'd work.

But yes, you're alluding to a very important point.

AviFS

Let me retry: If you could restart, would you replace monadic ∪'s functionality with monadic ≠

Adám

Maybe. ≠Y gives you the necessary information to compute ∪Y just like ⍋Y gives you the necessary information to sort Y.

AviFS

Aka forcing the new union to be something like {⍵/⍨≠⍵} equivalent to sorting being {⍵[⍋⍵]} so as to extend ⍒⍋ functionality

Adám

However, you can also use this information to filter/sort other arrays, or indeed to do other computations.

It is as if ∪Y and and a potential Sort function already applied their implied information before you had a chance to use that info for what you wanted.

Bubbler

@AviFS Union x∪y is a different thing from Unique ∪y.

AviFS

Jul 14, 2020 14:46

@Adám Exactly, that was what I meant. Sorry for the confusion. And it's not even a new idea; you mentioned the analogy in the webinar.

Just curious if you wouldn't make monadic union, unique, into nubsieve, if you could. Doing away entirely with the current one

Adám

@Bubbler Sure, but one could define a function X$Y such that (X$Y)⌿X⍪Y would match X∪Y. Same goes for ∩

AviFS

@Bubbler I know, I know. Sorry I screwed up badly... And put future readers of this Cultivation at bad risk of being confused...

Was meant to be a simple question

Adám

@AviFS One could argue that set functions are entirely superfluous if ∊ hadn't ravelled its right argument.

AviFS

@Adám That's true. Hadn't even thought of that yet.

Which raises a much larger philosophical question that I think was mentioned in the first 8v8-Zoom thing about how 'extensible' vs 'user-friendly' to make a language. I forget the words used; was more eloquent. But something along those lines

So the larger question is definitely a much larger question with no straightforward answer, for another time

Adám

Right.

AviFS

Jul 14, 2020 14:50

I was specifically asking if the current unique operator was sort of extraneous now, or if you'd cling onto it

But maybe that's also a non-straightforward question for another time

Terribly sorry for all the confusion, though!

Adám

Well, it is a handy thing to have, and I wouldn't be opposed to two Sort functions, even though we have the grades.

AviFS

More than happy to let you go on!

Adám

It is worth noting that the result of ≠Y is much more light-weight than ∪Y, in that it only ever has one bit per major cell, while ∪Y could end up duplicating a lot of data.

AviFS

@Adám Happy to leave it at that. Though it does feel incongruent to not have the same equivalents for the two function

Esp. since sort is probably used far more often than unique, I imagine

Adám

Well, there's another difference. ≠ returns a mask, while ⍋ returns indices.

AviFS

Jul 14, 2020 14:53

@Adám Very good point. Hadn't occurred to me

Adám

One could have defined ≠ to return indices of course.

AviFS

@Adám True, but they feel very similar, no?

Adám

In that they give you the "background information", yes.

AviFS

They're both an extendable skeleton of something more specific

@Adám 'Xactly

But seriously, I'll let you get on now for the benefit of future readers!

Adám

And I guess that'd be the more APLy way. Generalising at the cost of a little brevity. APL is plenty terse anyway.

AviFS

Jul 14, 2020 14:55

@Adám Elegance vs. usabilitiy

@Adám I think that's the way you put it!

So what else about the nub sieve should we know?

Perhaps more examples of use?

RGS

@AviFS I have used ≠ to filter data for recursive calls of functions

Adám

+/≠Y can be a much more efficient way than ≢∪Y for counting how many unique elements there are:

      n←?1e6⍴1e6
      ]runtime -c ≢∪n +/≠n

  ≢∪n  → 4.9E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  +/≠n → 3.1E¯3 | -38% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

AviFS

@RGS Oh?

@Adám Interesting!

@Adám Is there an efficient algorithm that counts the number of 1s in a binary number?

Or does it really sum up the list? I can't imagine it would...

@Adám Also though, the latter is more expressive... kind of a shame

Adám

@AviFS Summing bit Booleans is super efficient. Implemented in the CPU!

Remember that Dyalog only uses one bit per bit (as opposed to most other languages' normal behaviour/usage).

RGS

@Adám ooooooor you could do ≢⍸≠n which surprisingly is still faster ahaha

AviFS

Jul 14, 2020 15:00

@Adám I wonder if ≢∪Y couldn't be optimized to perform the same exact thing as +/≠Y under the hood. Because it's definitely the more intuitive one to write and the easier one to read

RGS

      ]runtime -c ≢∪n ≢⍸≠n

  ≢∪n  → 6.2E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ≢⍸≠n → 2.6E¯3 | -58% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Adám

@AviFS It could. Would need Marshall's thunks (or an idiom or composition).

AviFS

@Adám Isn't it a reasonable idea?

@Adám Yeah, I mean the optimized idioms that get highlighted a different color

Adám

@RGS Are you sure?

AviFS

Like sorting

Adám

Jul 14, 2020 15:01

      ]runtime -c ≢∪n +/≠n ≢⍸≠n

  ≢∪n  → 4.9E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  +/≠n → 3.3E¯3 | -34% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ≢⍸≠n → 3.6E¯3 | -27% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

AviFS

@Adám Interesting!

Marshall

≢∘∪ has special code (which may or may not be faster).

Adám

@AviFS We put addition of more idioms on hold because we expected thunks to come along.

AviFS

@Adám Oh? What's the difference?

RGS

@Adám not suggesting it is the fastest, just saying that it sounded like a dumb suggestion and turns out is still faster than ≢∪

AviFS

Jul 14, 2020 15:02

And why didn't they?

Adám

@AviFS See this

AviFS

@RGS Wow! That really says something about efficiency/inefficiency...

Adám

@AviFS They were not due yet, but because Marshall was the one who was going to implement them…

Anyway, let's return to usage of ≠Y…

AviFS

@Adám :( I see

@Adám Will let you do that!

Adám

Another thing you can do with the mask is to combine it with other masks:

      ⎕←m←(≠∧∊∘'aeiou')t←'hello world'
0 1 0 0 1 0 0 0 0 0 0
      m/t
eo

These are the unique vowels. Clear how this works?

Of course, in this case, you could as well write 'aeiou'∩'hello world' but this example is to illustrate the concept.

Nic

Jul 14, 2020 15:08

@Adám yup and sprinters will object that it's faster because you're doing the second search in a smaller set, whereas the first formula does the two search operations on the original set

RGS

@Adám Yes; if asked to perform the task "get unique vowels" I think I'd do m←≠v←t/⍨∊∘'aeiou' ⊢ t←'hello world' ⋄ m/v

So the combining masks is a powerful concept but often one would rather make the search space smaller in each step, no? At least I feel it is more intuitive

Adám

Of course.

RGS

@Adám ok ○/

Adám

OK, here's an exercise for you. Given a text (simple character vector) t, return a matrix so that the first instance of each occurring character is "underlined":

      Fn 'mississippi'
mississippi
¯¯¯     ¯
      Fn 'Hello world'
Hello world
¯¯¯ ¯¯¯ ¯ ¯

RGS

@Adám I have one with @, ⍸ and ≠ but it is not tacit (not sharing yet so as not to spoil the exercise)

Adám

Jul 14, 2020 15:16

@RGS I never said it had to be tacit.

RGS

@Adám I know :P I will be glad to share if/when you ask

Bubbler

I have 14 char dfn and 11 char tacit, not counting Fn← part.

RGS

@Bubbler my dfn is 23 bytes BUT it is perfectly acceptable and understandable code

Adám

This isn't code golf.

AviFS

I've stupidly forgotten to how to catenate underneath so mine is 16 bytes...

I generated the underneath and then did ⍉⍵,⍪...

How silly is that?!

Adám

Jul 14, 2020 15:19

@AviFS That's perfectly fine. ↑top bottom works too, and so does ,[0.5].

Bubbler

I guess it's about time to reveal the code?

Adám

Yeah, go ahead all 3 of you!

RGS

@Bubbler {↑⍵('-'@(⍸≠⍵)⊢' '↑⍨≢⍵)}

AviFS

No hold on!

Bubbler

Fn←{↑⍵((≠⍵)\'-')} and, for early birds, Fn←↑⊢,⍥⊂'-'\⍨≠

AviFS

Jul 14, 2020 15:20

@Adám How to do this with take

Adám

@AviFS Mix, not take.

AviFS

@Adám Yeah, that :p was about to say...

Well anyway, here's what I have

{⍉⍵,⍪' _'[(≠⍵)]}

RGS

@Bubbler ah the (≠⍵)\'-' is nice

@AviFS {⍉⍵,⍪' _'[≠⍵]}

AviFS

@RGS Yeah, I just saw that...

So I guess it's also 14 bytes even with the stupid bit?

With mix, it could be:

{↑⍵{⍺⍵}' _'[≠⍵]}

But isn't there a better way?

Bubbler

@AviFS {↑⍵(' _'[≠⍵])}

RGS

Jul 14, 2020 15:23

@RGS I realize I still don't know well in my head all the APL primitives

Adám

@AviFS Yes, now we have ,⍥⊂ which is what Bubbler used.

AviFS

@Adám Ah, thanks, still worrying about my own and hadn't had a chance to review the others

@Adám Except that's not any shorter than the original because it still requires mix

@Bubbler Is that the golfiest way possible?

Adám

@AviFS Sure, but ,⍥⊂ is shorter than {⍺⍵}.

AviFS

@Adám True, but that's not saying much :p

Adám

7 mins ago, by Adám

This isn't code golf.

AviFS

Jul 14, 2020 15:25

@Bubbler's parens is even shorter

@Adám Yes, except I'm curious now

Adám

Do you want another exercise or shall we continue with something else?

RGS

@Adám both sound fine and fun; something else if there's an exercise on that at the end?

AviFS

@Adám Another exercise?

@Bubbler This is my final answer :)

Adám

@AviFS ↑⊢⍮' _'⊇⍨⍧ in Extended… (⍧ is the ≠ we are studying now).

AviFS

Random question for later: Is it at all worth adding $ to APL as used in Haskell. One of the extended, dzaima, ngn or bqn type dialects

Eg. {↑⍵(' _'[≠⍵])} → `{↑⍵$' _'[≠⍵]}

It's a byte shorter, but more importantly I personally find it much easier to read!

dzaima

Jul 14, 2020 15:30

@AviFS aplwiki.com/wiki/Pair (BQN has ≍ which is {↑⍺ ⍵} in APL)

RGS

@AviFS that's not really what $ does in Haskell, is it? with that I'd expect ↑⍵ to be computed and then stranded with what is to its right

AviFS

(And also to add in after having written a bunch of code, rather than having to hunt for the end to add another parenthesis and delete the autocompleted one)

@RGS You're right. I'm not sure exactly how that'd translate. But definitely the same basic idea of grouping everything after the $ in some sort of way

Adám

OK, so here's another one: Given a vector, return the set of elements which have duplicates.

RGS

@AviFS haskell binds left 2 right so $ is used to bind things to its right and then keep binding ltr. Using $ in APL I'd expect things to be reversed

AviFS

@dzaima @Adám That's tremendous and super useful! Thanks a bunch

Bubbler

Jul 14, 2020 15:33

@AviFS Another related one

AviFS

@RGS True. Anyway, it was inspired by the Haskell...

Adám

@Bubbler @AviFS But Link has issues, as discussed there.

RGS

@Adám done ○/ not golfed :P

AviFS

@Bubbler Super interesting!

Bubbler

@Adám Keep the duplicates or not?

Adám

Jul 14, 2020 15:35

@Bubbler No, hence "set".

Bubbler

So Fn 'mississippi' should be 'isp'?

Adám

@Bubbler yes, or any permutation thereof.

AviFS

@Bubbler +←1

@Adám Ah, I see. In that case got it

9 byte dfn

Adám

Me too.

RGS

Uh my dfn is 10 bytes long ⍥

nvm, forgot that ⍨ exists

AviFS

Jul 14, 2020 15:38

@RGS Maybe parens vs ⍨

@RGS :)

RGS

CMC: the same but preserving original order

AviFS

@RGS Hmm, doesn't the 9 byte solution already do that?

RGS

@AviFS mine {∪⍵/⍨~≠⍵} doesn't

AviFS

@RGS Doesn't it?

RGS

{∪⍵/⍨~≠⍵} 'mississippi' gave sip instead of isp

Adám

Jul 14, 2020 15:40

@RGS 've got dfn at 11.

AviFS

@Adám ???

What does that mean?

Adám

@Bubbler and @AviFS found the same as RGS for the any-order challenge?

@AviFS I have an 11-character dfn solution to that CMC.

AviFS

@Adám Yup!

@RGS I see what you mean

Bubbler

@Adám Yes.

AviFS

@RGS It is in the original order of the duplicates

Just not the original order of the letters

Adám

Jul 14, 2020 15:43

Right. I opted for any order because both of those orders would make sense.

AviFS

(s appears before i because s is duplicated first even though i appears first)

@Adám I see

Adám

Anyone wants more time for RGS's CMC?

RGS

@Adám feel free to proceed :)

Bubbler

Quite a hack: ∪∩{⍵/⍨~≠⍵}

RGS

@Adám I got a long one at who-knows-how-many-bytes

Adám

Jul 14, 2020 15:45

Mine is {∪⍵∩⍵/⍨~≠⍵}. Same idea as Bubblers, really.

Bubbler

Yeah.

RGS

a (longer) different idea {s/⍨(s←m/⍵)∊⍵/⍨~m←≠⍵}

Adám

@RGS Ooh, old school.

AviFS

@Bubbler Doesn't seem to work for me...

Adám

@AviFS Parenthesis?

RGS

Jul 14, 2020 15:46

@AviFS it is a fork so you have to use it inline inside ()

Bubbler

      Fn←∪∩{⍵/⍨~≠⍵}
      Fn 'mississippi'
isp

Adám

OK, Let's see if we can do the new constant operator in the remaining 15 mins. It is really simple.

AviFS

@RGS Duh... Thanks

Was doing ∪∩{⍵/⍨~≠⍵}'mississippi'

@Adám ...Nothing in the world is simpler than this though, and it took 1hr15 ⍤

Adám

⍨ has been overloaded (or extended, if you want) to handle an array as operand, in addition to a function.

It derives a constant function, i.e. a function which always returns that array, no matter what argument(s) you feed it.

AviFS

@Adám Your use of links really impresses me! Must be a fair bit of work to find...

@Adám Mind going over the uses again?

Adám

Jul 14, 2020 15:50

@AviFS Of course not. Maybe the best one is to preserve order in a train.

AviFS

@Adám Mind showing how? Can't remember

Adám

Let's say you want to define a function which computes the cube of the absolute value.

QA←3*⍨|

But really, the natural way to think of this is (|Y)*3 only that you can't have an array as the right tine of a fork.

By converting the constant 3 into a function, 3⍨ it works: |*3⍨

It also allows you to easily write a tacit function that ignores its argument(s), e.g. let's say you want to add a dice roll. {?6} can be written as ?6⍨

So you can roll the dice for each player:

      ?6 6⍨¨'Abe' 'Bob' 'Carl'
┌───┬───┬───┐
│6 6│4 1│1 5│
└───┴───┴───┘

(Abe is clearly cheating!)

AviFS

@Adám Super neat! That makes a lot of sense

@Adám Confused about this one, though

Bubbler

Basically it is a replacement for {x} hack (and various workarounds), right?

AviFS

Although I noticed f←|*{3} is the same!

RGS

Jul 14, 2020 15:56

He clearly is:

Adám

@Bubbler Yes, with {x} have the issue of computing the result repeatedly. E.g. (÷3)⍨ is much better than {÷3}

RGS

       ?6 6⍨¨'Abe' 'Bob' 'Carl'
┌───┬───┬───┐
│6 6│5 0│3 2│
└───┴───┴───┘

AviFS

@RGS That's amazing!!

@Adám But again with the idioms/thunk. If two things do the same thing and one is much better, why not make the worse one act like the better?

RGS

@AviFS (I just quote that xkcd comic whenever I have the chance, sometimes even when not appropriate)

AviFS

Wait nvm, that's intended behavior, isn't it.

Adám

Jul 14, 2020 15:58

@AviFS Indeed. {0} is an idiom which dates before this operator, but how many such idioms should one implement? There are a lot of possible arrays out there…

AviFS

@Adám It's intended to re-evaluate though, right?

Or at least I hope so

RGS

@Adám couldn't one generalize the pattern, though? Assuming we are talking about constant arrays

dzaima

@AviFS in general, making {÷3}¨⍳10 calculate ÷3 only once would require making a check for whether a dfn is pure, which might be non-trivial

AviFS

I use it with the intention that it should re-evaluate every now and then

Adám

@AviFS Sure, there's a need for both.

The real equivalent of A⍨ is (A⊣⊢) which is frankly obscure.

AviFS

Jul 14, 2020 16:00

Eg. As a arg-less function of things that have state. So that despite not taking params, it changes result depending on the state of the stuff inside

Whereas if it were an expression. It never would be re-evaluated

Adám

Right. There's a use case for both.

Any more questions before we close for today?

AviFS

@Adám You did say that. I just thought an example might be helpful

Adám

@AviFS E.g. you could loop over something and for each one check for the existence of a file. You'd want to check each time.

There are plenty of cases where you want to run an expression each time the function is called. Another common one is using a dfn to append to a global accumulator.

A⍨ is for those cases where you truly want a constant value.

RGS

@Adám Can only think of one: is there homework? :P

Adám

@RGS No. Sorry.

AviFS

Jul 14, 2020 16:05

@Adám Argh, midway through writing one!

RGS

@Adám Crushing all my hopes and dreams D:

Adám

@AviFS Go ahead.

RGS

@AviFS I think Adám won't mind you asking something else out of APL Cultivation hours hehe

AviFS

@Adám My one question is why this one-byte shortening (and admittedly optimized whatevers due to not rerunning) was added as opposed to countless other possibilities

Eg. the pair function mentioned earlier which removes need of parenthesis, thereby also shortening by one byte, making many expressions far more elegant and readable, but not actually adding any new functionality

It seems to me there are many potential operators in the category above (eg. with those 3 main traits of more elegant, slightly less code, perhaps more efficient, but no new functionality)

Adám

@AviFS It isn't just one-byte in the case where A⍨ occurs inside a longer train or before an operator. Also, you could make the same (or even a stronger) argument about N+M vs N--M. Notation as a tool of thought, I'd say.

AviFS

Jul 14, 2020 16:08

@Adám Notation as a tool of thought, definitely! The question was absolutely not why add this, but why was this chosen over others?

dzaima

@AviFS ⍨ is also much more clear often. Some order of implementing things must be chosen, and this managed to come before some others for Some Reasons™

Adám

Constant also had a very low cost, in that it fit nicely into an existing symbol, with no other sensible way to extend the domain of ⍨ to arrays.

AviFS

If there was some need for it spurred on by something in particular or such

@Adám Re: train. Can't {c} be used wherever c⍨ is used?

@dzaima That's a good point

Adám

@AviFS No, not really. I suggested a whole bunch of operators to add. Some were added in 18.0, others held off for later, and some not scheduled for implementation right now.

AviFS

@Adám Also a very good point

@Adám I see! Well that answers my question!

dzaima

Jul 14, 2020 16:10

@AviFS afaik there's been discussion about whether the builtin for pair should be {⍺ ⍵} or {↑⍺ ⍵}, so that's possibly an acceptable reason for the much simpler ⍨ getting in before other things

AviFS

Was really just curious what the impetus was

@Adám Really? Is it all you suggesting new operators; are you the guy for that? Or others as well?

@dzaima Interesting...

Adám

@AviFS No:

      mask←1 0 0 0 1 0 0 ⋄ data←'AbcdEfg'
      mask{'⎕'@{⍺}⍵}data
VALUE ERROR
      mask{'⎕'@{⍺}⍵}data
               ∧
      mask{'⎕'@(⍺⍨)⍵}data
⎕bcd⎕fg

RGS

@Adám good example; and ⍣ has a similar issue, then

AviFS

@Adám Hmmm...

There's also no clean workaround for some pair stuff afaik

Eg.

      6 7 8(+⍮-)3
┌───────┬─────┐
│9 10 11│3 4 5│
└───────┴─────┘

Adám

@AviFS Not just me. [John Scholes ](aplwiki.com/wiki/John_Scholes), Roger Hui, and Marshall Lochbaum all used to as well.

AviFS

Jul 14, 2020 16:12

But I guess {⍺⍵} isn't so bad

dzaima

@AviFS {⍺⍵} is an idiom iirc

AviFS

@dzaima Yeah, it is

@dzaima I give in

Alright, that's it from me @Adám. Thanks a bunch for everything!

Adám

@AviFS Well, we did add ⍥ (which we'll treat in an upcoming Cultivation) which allows ,⍥⊂

AviFS

@Adám True

Adám

OK, that's it for today then. See you in two weeks!

Lesson 46 - unique mask ≠ and constant ⍨

The APL Orchard

Participants