Encode decode: ⊤⊥¶

Teaching peers is one of the best ways to develop mastery. –Jeff Atwood

Here’s some of APL’s secret sauce, not commonly encountered in other languages: Encode, ⊤ and Decode, ⊥. Encode and Decode provide efficient basis conversion across potentially mixed radixes.

Other resources:

⎕IO ← 0 ⍝ You know the drill


The canonical example is to convert numbers between bases, for example, converting a base-10 number to 8-bit binary:

(8⍴2)⊤54

0 0 1 1 0 1 1 0

…and back to base-10:

2⊥0 0 1 1 0 1 1 0

54

I vowed not to mention magic inverses, but these few are too damned useful to leave out. Convert a base-10 number to binary, using the least number of bits:

2∘⊥⍣¯1 ⊢ 54

1 1 0 1 1 0

…and as a consequence, split a number into its constituent digits:

10∘⊥⍣¯1 ⊢ 677398723 ⍝ Number to digit vector

6 7 7 3 9 8 7 2 3

Those were all fixed radix. An example of mixed radix is converting between seconds and days, hours, mins and seconds, e.g “how many days, hours, mins and seconds is 10000 seconds”?

1 24 60 60⊤10000

0 2 46 40

and, conversely, how many seconds in 1 day (and night)?

1 24 60 60⊥1 0 0 0

86400

Here’s an example of Decode and Encode, borrowed from Mathematica’s documentation for its corresponding MixedRadix function.

A Roman legion was made of 10 cohorts, a cohort of 6 centuries, a century of 10 contuberniae, and a contubernia of 8 soldiers.

units ← 'legion' 'cohort' 'century' 'contubernia' 'soldier'
bases ← 10 10 6 10 8


Given 16,894 soldiers, how are they organized?

↑units (bases⊤16894)

┌──────┬──────┬───────┬───────────┬───────┐ │legion│cohort│century│contubernia│soldier│ ├──────┼──────┼───────┼───────────┼───────┤ │3 │5 │1 │1 │6 │ └──────┴──────┴───────┴───────────┴───────┘

Going the other way, how many soldiers are there in a legion?

bases⊥1 0 0 0 0

4800

There are some less obvious uses, too. For example, we can use 1⊥ to sum vectors:

1⊥⍳10

45

The utility of that may not be obvious, but it comes very handy when writing tacit code which we’ll cover in depth later, but here’s a taster – given a vector where all elements are the same, bar one, what’s the index of the “odd one out”?

(1⍳⍨1⊥∘.=⍨) 243 243 243 243 251 243 243 ⍝ Index of "odd one out"

4

The enigmatic ⊥⍨ counts trailing 1s:

⊥⍨0 1 0 0 1 1 0 1 1 1 1 1

5

We can also use Encode and Decode between indices of an array and its ravel:

⎕ ← m ← 3 5 ⍴15?15
⎕ ← rav ← ,m

3 0 5 12 4 9 8 6 2 10 11 7 1 14 13
3 0 5 12 4 9 8 6 2 10 11 7 1 14 13

Given index ← 1 4 into the above array, what’s the corresponding index into the ravel vector?

index ← 1 4
⎕ ← k ← (⍴m)⊥index ⍝ 2D to 1D
m[⊂index]
k⊃rav

9
10
10

And the reverse:

⎕ ← i j←(⍴m)⊤k ⍝ 1D to 2D

1 4