From dc9cdd8a54e0057524c5ac69a21c52969a8e8cda Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Mon, 18 Apr 2022 10:52:26 -0400 Subject: Diagrams for Grade and Ordinals --- doc/order.md | 54 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 53 insertions(+), 1 deletion(-) (limited to 'doc') diff --git a/doc/order.md b/doc/order.md index 93c0c1c7..fae7f73f 100644 --- a/doc/order.md +++ b/doc/order.md @@ -24,7 +24,42 @@ Sort Down always [matches](match.md) Sort Up [reversed](reverse.md), `⌽∘∧` ## Grade -*See the [APL Wiki page](https://aplwiki.com/wiki/Grade) for a few more examples. BQN only has the monadic form.* + Grade is more abstract than Sort. Rather than rearranging the argument's cells immediately, it returns a list of indices (more precisely, a permutation) giving the ordering that would sort them. @@ -40,6 +75,22 @@ Given our list `l` of things in a solar system, Sort Up orders them by size, or ### Ordinals + + So the elements of the Grade of an array correspond to the cells of that array after it's sorted. It's tempting if you don't have the sorted list handy to try to match them up with major cells of the original array, but this never makes sense—there's no relationship. However, applying Grade *twice* gives us a list that does correspond to the original argument quite usefully: it says, for each major cell of that argument, what rank it has relative to the others (smallest is 0, next is 1, and so on, breaking ties in favor of which cell comes earlier in the argument). Experienced APL programmers call this pattern the "ordinals" idiom. l ≍ ⍋⍋ l @@ -77,6 +128,7 @@ The two Bins functions are written with the same symbols `⍋` and `⍒` as Grad Bins behaves like a [search function](search.md) with respect to rank: it looks up cells from `𝕩` relative to major cells of `𝕨`. However, there's an extra requirement: the left argument to Bins is already sorted according to whichever ordering is used. If it isn't, you'll get an error. 5‿6‿2‿4‿1 ⍋ 3 + 0‿3‿4‿7‿9 ⍒ 3 Given this, the simplest definition of `𝕨⍋𝕩` (or `𝕨⍒𝕩`) is that for each cell in `𝕩` of rank `(=𝕨)-1`, it counts the number of major cells from `𝕨` that come earlier in the ordering, or match that cell. -- cgit v1.2.3