Fear and Loathing with APL

Hav­ing heard so much about APL from Phil Trelford (who is one of the lead­ers in the F# com­mu­ni­ty) I decid­ed to try it out too. For the unini­ti­at­ed, APL code looks every bit as mind-bend­ing and unbe­liev­able as scenes from John­ny Depp’s Fear and Loathing in Las Vegas.

For exam­ple, the life func­tion below imple­ments Conway’s game of life:

I know, right? WTF and mind blow­ing in equal mea­sures…

 

As I was learn­ing through Mas­ter­ing Dya­log APL, I took down plen­ty of notes which I hope will help get you up to speed with the basics quick­ly.

You can try out the exam­ples at TryAPL, just click on the “APL Key­board” but­ton and use the vir­tu­al key­board to enter the sym­bols you need.

Learn APL in 10 Minutes

and does what you’d expect but mul­ti­pli­ca­tion and divi­sion becomes and (just like in maths).

in APL is pow­er, i.e.

/ in APL also means some­thing else, which we’ll come to lat­er.

Also note the dif­fer­ence between neg­a­tive sign and sub­trac­tion , e.g.

 

Use to assign a val­ue (either scalar or array) to a name, e.g.

and remem­ber, vari­able names are case sen­si­tive.

Vari­ables are muta­ble, and you can assign mul­ti­ple vari­able at once:

but only if the length match, oth­er­wise you’ll get an error

=>

 

You can per­form arith­metic oper­a­tions between two arrays with the same shape:

=>

=>

look ma, no loops 

If the shape doesn’t match, then you get an error:

=>

 

But, if one of the vari­ables is a scalar then the oth­er vari­able can be any shape:

=>

=>

The same rule applies to oth­er oper­a­tions, e.g. max and min .

=>

=>

=>

 

Most sym­bols in APL have dou­ble mean­ing, just like they do in alge­bra, e.g.

where — means sub­trac­tion, a dyadic use of the sym­bol

where — means neg­a­tive, a monadic use of the same sym­bol

(before you freak out, monadic here is of the Math­e­mat­ics def­i­n­i­tion, and not the Haskell vari­ant )

To find the length of an array, you can use Rho monad­i­cal­ly:

=> 5

 

You can also Rho   dyad­i­cal­ly to orga­nize items into spec­i­fied shapes, i.e.

=>

where 4 2 describes the shape — 4 rows, 2 columns, fol­lowed by Rho and the array of items to be orga­nized.

If the num­ber of items in the array doesn’t match the num­ber of slots in the shape we’re try­ing to orga­nize into, then the array is repeat­ed, e.g.

=>

=>

If there are too many items then extra items are ignored:

=>

Uti­liz­ing the way items are repeat­ed, there’s a neat trick you can do, e.g.

=>

 

In gen­er­al, APL has spe­cial names for data depend­ing on its shape:

scalar — sin­gle val­ue

vec­tor — list of val­ues

matrix — array with 2 dimen­sions

array — gener­ic term for any set of val­ues, regard­less of no. of dimen­sions

table — com­mon term for matrix

cube — com­mon term for array with 3 dimen­sions

Ok, now that we’ve intro­duced the notion of dimen­sions, it’s time to con­fess that I slight­ly mis­led you ear­li­er — Rho actu­al­ly returns the shape of an array (not just its length, which only applies to a vec­tor), so it works with mul­ti-dimen­sion­al data too.

=> 2 2

Fur­ther­more, since the result of Rho is itself a vec­tor, apply­ing Rho again will give us the num­ber of dimen­sions an array has — oth­er­wise known as its Rank.

=> 2

i.e. scalars have 0 rank, vec­tors have 1 rank, and so on…

 

You can also reduce over a set of val­ues using / e.g. a plus reduc­tion to sum up all the num­bers in an array can be writ­ten as

=>

sim­i­lar­ly, fac­to­r­i­al can be writ­ten using mul­ti­ply reduc­tion:

=>

The / sym­bol is an oper­a­tor, where­as etc. are func­tions. / can accept any of these func­tions and uses it to reduce over an array.

=> 9

=> 1

 

APL calls pro­grams defined func­tions, and you can cre­ate a defined func­tion like this:

=> 3

where:

— pro­gram name

— gener­ic sym­bol for array passed on the right

— gener­ic sym­bol for array passed on the left

for exam­ple, if we have a func­tion such that

=> 16

what we’ve done here is to sum the array on the right of — 4 5 6 7 — and sub­tract it with the sum of the array on the left — 1 2 3.

Sim­ple, right? Let’s try a few more.

=> 63

and you can use your cus­tom func­tions with reduc­tion:

=> 15

 

To index into an array, you can use the stan­dard [ ] nota­tion:

=> 4

noticed that? APL is one-indexed!

What’s more, just like every­thing else, you can index into array with either a scalar or an array:

=> 1 3 4

=> 1 3 4 1

This also works when it comes to updat­ing val­ues in an array:

=> 42 2 42 4 42

=> 1 2 3 4 5

=>

Note that it fol­lows the same rule as func­tions with regards to the input being either a scalar or a same-shaped array.

If the shape of the array doesn’t match, then it’ll error:

=>

Equal­ly, if you use an invalid index, you’ll also get an error:

=>

 

You can use Iota to gen­er­ate an array of inte­gers from 1 to N, e.g.

=> 1 2 3 4

=> 1 2 3 4

 

Booleans are rep­re­sent­ed as 1 and 0, and you can use any one of these rela­tion­al func­tions: < = =/ >

=> 0 1 1

=> 1 0 0

AND and OR seman­tics are rep­re­sent­ed by and respec­tive­ly.

=> 1 0 1

=> 0 1 1

you can use them to count no. of employ­ees based on salary for instance:

=> 2

 

You can also use an array of boolean val­ues as masks too:

=> 1 3

=> iu

this is called com­pres­sion, and is use­ful for select­ing items con­form­ing to some cri­te­ria, e.g.

=> 1 1 0 0 0 1 0

=> 7

=> 1 2 3 4 5 6 7

there­fore, to find the indices of val­ues that’s greater than 10

=> 1 2 6

and to get the cor­re­spond­ing val­ues, just use com­pres­sion:

=> 11 13 15

 

Giv­en two arrays, A and B, you can return a new array with all the ele­ments of A minus all the ele­ments of B using the with­out oper­a­tor ~

=> 1 2

this doesn’t mod­i­fy A or B though.

=> 1 2 3

=> 3 4 5

 

mem­ber­ships

To find items from an array that exists in anoth­er array, you can use the mem­ber­ship oper­a­tor

=> 1 0 1 0 1

it also works with strings

=> 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0

you can (like before) get the indices of match­es using com­pres­sion:

=> 2 4 6 8 11 14 16 20 23 24 30 33 36 41 43 45

or find the match­ing char­ac­ters using com­pres­sion:

=> aaa­iaaaeeea­iaaii

inspect­ing the result tells us that those are indeed the char­ac­ters we’re look­ing for!

 

search

We saw how we can com­bine mem­ber­ships and iota-rho to find the indices in Phrase that cor­re­sponds to a mem­ber in ‘aeiouy’.

What if we want to find the first index each char­ac­ter in ‘aeiouy’ appears in Phrase, i.e. “aeiouy”.Select(char -> Phrase.IndexOf(char)) if you’re com­ing from a .Net back­ground.

We can use the dyadic form of Iota :

=> 2 20 8 47 47 47

note that the length of Phrase is 46

=> 46

so the result 47 is essen­tial­ly say­ing that ‘o’, ‘u’, ‘y’ nev­er appeared in Phrase.

 

You can mod­el an ‘else’ seman­tic using two arrays whose lengths are off by 1. For instance:

based on the way search works (not found = length + 1), we can map the spec­i­fied Area codes to cor­re­spond­ing dis­count rates: 17 -> 9, 50 -> 8, … 89 -> 4, and all oth­ers to 2.

=> 6 6 5 6 6 2 6 2 4 6 1 5

so where D does not exist in Area, you’ll get index 6 which does not exist in Area, BUT exists in Dis­count — i.e. the ‘oth­er’ case we’re try­ing to mod­el.

So if we use the result of as indices in Dis­count we’ll find the cor­re­spond­ing dis­count rate for the val­ues in D:

=> 2 2 4 2 2 8 2 8 5 2 9 4

this is an algo­rithm for chang­ing the frame of ref­er­ence, i.e. chang­ing a list of area codes into a list of dis­count val­ues, a gen­er­al form can be described as:

where  =  + 1

 

take and drop

You can use the Take and Drop func­tions like you do with Enumerable.Take and Enumerable.Drop in LINQ:

=> 1 2 3 4

=> 5 6 7 8 9 10

if the count is neg­a­tive then you take from the end of the list, e.g. take last 3 items or drop last 7 items:

=> 8 9 10

=> 1 2 3

 

Giv­en a list of val­ues

sup­pose you want to find the change from one num­ber to the next, i.e. 3 (+5) 8 (-3) 5 (+9) 14…

con­sid­er­ing that

=> 8 5 14 34 5 17 21 18

=> 3 8 5 14 34 5 17 21

so now you can sub­tract the two arrays (of equal length) to get the answer:

=>

clever, right? It’s rem­i­nis­cent of the RX approach to track­ing mouse moves.

 

mir­rors and trans­po­si­tion

You can also piv­ot data about any direc­tion eas­i­ly:

(screen­shot tak­en from Mas­ter­ing Dya­log APL)

 

out­er prod­ucts

You can use the out­er prod­uct oper­a­tor  to cal­cu­late the carte­sian prod­ucts of two lists:

=>

using the small cir­cle + dot + an oper­a­tion to apply, in this case mul­ti­ply , but could eas­i­ly be any­thing else:

=>

here’s even more exam­ples tak­en from Mas­ter­ing Dya­log APL:

Unlike some of the oper­a­tions we’ve seen so far, the out­er prod­uct oper­a­tor works across dif­fer­ent sized arrays too:

=>

 

Final­ly, there are some com­mon pat­terns (or idioms) you’ll see in APL.

• find indices in A that exists in B

• find the mem­bers (not indices) of A that exists in B

• find indices in A where B first appeared in (i.e. Index­Of)

• change the frame of ref­er­ence

• gen­er­ate indices with incre­ment­ing steps

 

So that’s it, I hope this post has giv­en you a flavour of APL and help you learn the basics quick­ly. I find the array pro­gram­ming par­a­digm absolute­ly mind blow­ing and a com­plete­ly dif­fer­ent way to think about prob­lems.

Also I find it has a sim­i­lar trans­for­ma­tive effect in chang­ing the way I think about vari­ables — as a point-in-time snap­shot of some scalar val­ue — to FRP (e.g. sig­nals in Elm or observ­ables in RX).

 

In the next post, let’s see how we can use APL to solve some sim­ple prob­lems (that’s all I’m able to man­age for now!).

 

Links

• Mas­ter­ing Dya­log APL (free ebook)
• TryAPL
• C# eye for the APL guy