Hello, here are the recordings of my two talks at Oredev with accompanying slides.

*Note: see the rest of the series so far.*

I stumbled across this post the other day and problem 2 seems like something I can easily do in APL since it essentially requires you to interleave two arrays.

The problem is:

Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

Here’s the solution I have come up with:

since it uses both (right argument) and (left argument) so it’s a dyadic function, let’s test it out:

=> a 1 b 2 c 3

Here’s how it works:

- concatenate the two arguments together, with the left argument first
- reshape the concatenated vector into 2 rows, so that you have effectively placed and into a matrix, i.e.

- transpose that matrix

- reshape the transposed matrix into a vector, and that’s it!

*Note: see the rest of the series so far.*

This is a classic interview question, and after some experimentation I ended up with the following solution in APL:

=> 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz

The answer looks correct, though this is perhaps not the most straight forward solution, so let’s walk through what’s happening here:

- first turn the input array into booleans to determine if they’re divisible by 3 or 5

: 0 0 1 0 0 1 0 0 1 0 0 1 …

: 0 0 0 0 1 0 0 0 0 1 0 0 …

- assuming that has length of 100, then transform the boolean arrays from the previous step so that 1s becomes 101s (for those divisible by 3) and 102s (for those divisible by 5)

: 0 0 101 0 0 101 0 0 101 0 0 101…

: 0 0 0 0 102 0 0 0 0 102 0 0 0…

- add the two arrays together, so that those divisible by 3 has value 101, divisible by 5 has value 102 and those divisible by 15 has value 203

0 0 101 0 102 101 0 0 101 102 0 101 0 0 **203** 0 0 101 …

- apply minimum to this array with 103 being the operand, so now numbers divisible by 15 has value 103 instead of 203

0 0 101 0 102 101 0 0 101 102 0 101 0 0 **103** 0 0 101 …

- apply maximum to this array with the input array to end up with the following

1 2 **101** 4 **102 101** 7 8 **101 102** 11 **101** 13 14 **103** 16 17 **101** …

- use this array as index for an array that is made up of the input array with ‘Fizz’ ‘Buzz’ ‘FizzBuzz’ added to the end at index position 101, 102 and 103 respectively

*Note: see the rest of the series so far.*

Surprisingly, my last post on APL did well on HackerNews, turns out there is genuine interest in APL out there, which is great to see

I have been busy with a number of conferences and talks since then so I haven’t had time to revisit APL. Over the next couple of posts in this series (or rather, what I hope would amount to a series) let’s try to solve some simple problems with APL. Mind you, my knowledge of APL is pretty shallow so what I end up with is likely far from idiomatic APL code, so feel free to offer pointers/feedbacks in the comments section below!

To start us off nice and easy, let’s look at something really simple, like Euler Problem 1.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Super easy, right? I knew how to solve this with a one-liner even when I was a total beginner in F#.

which roughly translates to the following in APL:

=> 23

Looks great, and running gives the right answer (I won’t spoil the answer for you, but feel free to run this in TryAPL at your own discretion!) So here’s what we did (p.s. | is the remainder operator):

- find elements from the input that are divisible by 3 or 5
- which gives us an array of booleans, which we then OR
- then we use compression to filter the input array to return only the elements that are divisible by 3 or 5
- and finally reduce over these elements with addition

p.s. OK, it’s not exactly a faithful translation of the F# code above, the equivalent F# code should probably use *reduce* as well:

**UPDATE 24/07/2015** : much to my pleasant surprise this piqued Tomas’s interest and he even did a quick AplMode to show how you can mimic the APL code above in F# and solve the problem in 19 characters.

To be fair, I’m writing APL whilst thinking like a F#er so I’m not doing it justice, but Stefano shared an even shorter APL solution (17 characters):

This took me a little while to understand, but fortunately Dyalog APL‘s IDE’s really quite easy to use and so after some experimentation here’s how Stefano’s solution works:

*(first you need to understand that in APL, you always read from RIGHT-TO-LEFT unless you can ( ))*

1) generate an outer product () of reminders (using the *residue* | operator):

- the array of 3 and 5; and
- input array

this generates (for 1 to 9) the matrix:

1 2 0 1 2 0 1 2 0

1 2 3 4 0 1 2 3 4

2) transform matrix into boolean by comparing them to 0 (0 = …)

0 0 1 0 0 1 0 0 1

0 0 0 0 1 0 0 0 0

3). so now we reduce the matrix using the logical OR operator (the special symbol you see here is called *reduce first* and is the same as reduce / but along the first dimension of the array)

0 0 1 0 1 1 0 0 1

4) since this array has the same length as our input, we can just multiply the two together!

0 0 3 0 5 6 0 0 9

5) and finally reduce over this array using addition and voila!

Having heard so much about APL from Phil Trelford (who is one of the leaders in the F# community) I decided to try it out too. For the uninitiated, APL code looks every bit as mind-bending and unbelievable as scenes from Johnny Depp’s *Fear and Loathing in L**as Vegas*.

For example, the **life** function below implements Conway’s game of life:

I know, right? WTF and mind blowing in equal measures…

As I was learning through Mastering Dyalog APL, I took down plenty of notes which I hope will help get you up to speed with the basics quickly.

You can try out the examples at TryAPL, just click on the “APL Keyboard” button and use the virtual keyboard to enter the symbols you need.

and does what you’d expect but multiplication and division becomes and (just like in maths).

in APL is power, i.e.

/ in APL also means something else, which we’ll come to later.

Also note the difference between negative sign and subtraction , e.g.

Use to assign a value (either scalar or array) to a name, e.g.

and remember, variable names are **case sensitive**.

Variables are **mutable**, and you can assign multiple variable at once:

but only if the length match, otherwise you’ll get an error

=>

You can perform arithmetic operations 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 variables is a scalar then the other variable can be any shape:

=>

=>

The same rule applies to other operations, e.g. max and min .

=>

=>

=>

Most symbols in APL have double meaning, just like they do in algebra, e.g.

where – means subtraction, a **dyadic** use of the symbol

where – means negative, a **monadic** use of the same symbol

(before you freak out, *monadic* here is of the Mathematics definition, and not the Haskell variant )

To find the length of an array, you can use Rho monadically:

=> 5

You can also Rho dyadically to organize items into specified shapes, i.e.

=>

where 4 2 describes the shape – 4 rows, 2 columns, followed by Rho and the array of items to be organized.

If the number of items in the array doesn’t match the number of slots in the shape we’re trying to organize into, then the array is repeated, e.g.

=>

=>

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

=>

Utilizing the way items are repeated, there’s a neat trick you can do, e.g.

=>

In general, APL has special names for data depending on its shape:

**scalar** – single value

**vector** – list of values

**matrix** – array with 2 dimensions

**array** – generic term for any set of values, regardless of no. of dimensions

**table** – common term for matrix

**cube** – common term for array with 3 dimensions

Ok, now that we’ve introduced the notion of dimensions, it’s time to confess that I slightly misled you earlier – Rho actually returns the **shape** of an array (not just its length, which only applies to a vector), so it works with multi-dimensional data too.

=> 2 2

Furthermore, since the result of Rho is itself a vector, applying Rho again will give us the number of dimensions an array has – otherwise known as its **Rank**.

=> 2

i.e. scalars have 0 rank, vectors have 1 rank, and so on…

You can also reduce over a set of values using / e.g. a plus reduction to sum up all the numbers in an array can be written as

=>

similarly, factorial can be written using multiply reduction:

=>

The / symbol is an operator, whereas etc. are functions. / can accept any of these functions and uses it to reduce over an array.

=> 9

=> 1

APL calls programs **defined functions**, and you can create a defined function like this:

=> 3

where:

– program name

– generic symbol for array passed on the right

– generic symbol for array passed on the left

for example, if we have a function such that

=> 16

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

Simple, right? Let’s try a few more.

=> 63

and you can use your custom functions with reduction:

=> 15

To index into an array, you can use the standard [ ] notation:

=> 4

noticed that? APL is **one-indexed**!

What’s more, just like everything 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 updating values in an array:

=> 42 2 42 4 42

=> 1 2 3 4 5

=>

Note that it follows the same rule as functions 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:

=>

Equally, if you use an invalid index, you’ll also get an error:

=>

You can use Iota to generate an array of integers from 1 to N, e.g.

=> 1 2 3 4

=> 1 2 3 4

Booleans are represented as 1 and 0, and you can use any one of these relational functions: < = =/ >

=> 0 1 1

=> 1 0 0

AND and OR semantics are represented by and respectively.

=> 1 0 1

=> 0 1 1

you can use them to count no. of employees based on salary for instance:

=> 2

You can also use an array of boolean values as masks too:

=> 1 3

=> iu

this is called **compression**, and is useful for selecting items conforming to some criteria, e.g.

=> 1 1 0 0 0 1 0

=> 7

=> 1 2 3 4 5 6 7

therefore, to find the indices of values that’s greater than 10

=> 1 2 6

and to get the corresponding values, just use compression:

=> 11 13 15

Given two arrays, A and B, you can return a new array with all the elements of A minus all the elements of B using the **without** operator ~

=> 1 2

this **doesn’t modify** A or B though.

=> 1 2 3

=> 3 4 5

**memberships**

To find items from an array that exists in another array, you can use the membership operator

=> 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 matches using compression:

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

or find the matching characters using compression:

=> aaaiaaaeeeaiaaii

inspecting the result tells us that those are indeed the characters we’re looking for!

**search**

We saw how we can combine memberships and iota-rho to find the indices in Phrase that corresponds to a member in ‘aeiouy’.

What if we want to find the first index each character in ‘aeiouy’ appears in Phrase, i.e. *“aeiouy”.Select(char -> Phrase.IndexOf(char))* if you’re coming from a .Net background.

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 essentially saying that ‘o’, ‘u’, ‘y’ never appeared in Phrase.

You can model an ‘else’ semantic 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 specified Area codes to corresponding discount rates: 17 -> 9, 50 -> 8, … 89 -> 4, and all others 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 Discount – i.e. the ‘other’ case we’re trying to model.

So if we use the result of as indices in Discount we’ll find the corresponding discount rate for the values in D:

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

this is an algorithm for **changing the frame of reference**, i.e. changing a list of area codes into a list of discount values, a general form can be described as:

where = + 1

**take and drop**

You can use the Take and Drop functions 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 negative 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

Given a list of values

suppose you want to find the change from one number to the next, i.e. 3 *(+5)* 8 *(-3)* 5 *(+9)* 14…

considering that

=> 8 5 14 34 5 17 21 18

=> 3 8 5 14 34 5 17 21

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

=>

clever, right? It’s reminiscent of the RX approach to tracking mouse moves.

**mirrors and transposition**

You can also pivot data about any direction easily:

(screenshot taken from Mastering Dyalog APL)

**outer products**

You can use the outer product operator to calculate the cartesian products of two lists:

=>

using the small circle + dot + an operation to apply, in this case multiply , but could easily be anything else:

=>

here’s even more examples taken from Mastering Dyalog APL:

Unlike some of the operations we’ve seen so far, the outer product operator works across different sized arrays too:

=>

Finally, there are some common patterns (or idioms) you’ll see in APL.

- find indices in A that exists in B

- find the members (not indices) of A that exists in B

- find indices in A where B first appeared in (i.e.
*IndexOf*)

- change the frame of reference

- generate indices with incrementing steps

So that’s it, I hope this post has given you a flavour of APL and help you learn the basics quickly. I find the array programming paradigm absolutely mind blowing and a completely different way to think about problems.

Also I find it has a similar transformative effect in changing the way I think about variables – as a point-in-time snapshot of some scalar value – to FRP (e.g. signals in Elm or observables in RX).

In the next post, let’s see how we can use APL to solve some simple problems (that’s all I’m able to manage for now!).

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.