Loops and Recursion

Looping is an incredibly basic and fundamental programming construct which you will notice we have barely used at all so far. Or at least, we haven't used many explicit loops.

Terminology

The type of looping over items in a collection as provided by for and while loops is sometimes referred to as scalar looping. Other types of looping in APL might, for example, process each row of a matrix in turn but process whole rows at a time. In contrast, each ¨ is a mechanism for looping over every item of an array (the scalars); its operand function can see arrays nested within the scalars.

An introduction to an introduction to an introduction to an introduction to an int...

      {⍺←1 1 ⋄ ⍵=2:⍺ ⋄ (⍺,(+/¯2↑⍺))∇⍵-1}

Try the dfn above with various numeric arguments and consider the following questions:

Which symbol refers to the function itself?
Which symbol separates expressions?
Which part represents a conditional? This is where one part of code executes only if a preceding statement is true.
What is the default left argument? What happens if you call this function dyadically?

Give the function an appropriate name.

When a function calls itself like this it is called recursion. APL tends to rely less on explicit iteration and recursion than most popular programming languages, but it is good to be able to do it when you need to.

If a function gets stuck in an infinite loop, use Action → Interrupt in the menu. You can also use the key combination Ctrl+Break to interrupt a running function.

Write the shortest dfn which causes infinite recursion.
Write the shortest dfn which causes infinite recursion unless its argument is 0.
The factorial function multiplies integers up to ⍵. Write the factorial function as a recursive dfn called Factorial. Use the primitive !⍵ factorial function to check your solution.
Write an expression for the factorial function as a reduction (an expression which includes f/ for some function f).

A sort of detour

Dyalog's grade-up ⍋ and grade-down ⍒ functions are able to sort any array. However, it is interesting and useful to look at other approaches to sorting.

Here is a function 'NSort' for sorting numeric lists.

      NSort←{0=⍴⍵:⍬ ⋄ (U/⍵),∇(~U←⍵=⌊/⍵)/⍵}

Try NSort with some numeric arguments. Here it is presented piece-by-piece. For each comment prompt ⍝, write a brief description of what that part of the function does. The first one has been done for you.

      NSort←{
             0=⍴⍵:⍬                         ⍝ Reached end of list, return empty numeric vector
                    ⋄                       ⍝ 
                      (U/⍵),                ⍝ 
                            ∇               ⍝
                             (~U←⍵=⌊/⍵)     ⍝
                                       /⍵   ⍝
                                         }

Below is a function TSort for sorting character matrices.

      TSort←{⍺[((⍴⍵)[2])S ⍺⍳⍵]}
      S←{⍺=0:⍵ ⋄ (⍺-1)S ⍵[⍋⍵[;⍺];]}

Examine TSort and replace ⍺ below with an appropriate left argument to sort the character matrix WORDS.

      WORDS←↑'DOLPHIN' 'BRACKEN' 'SAUCER' 'MAGNET' 'FLOP'
      ⍺ TSort WORDS
BRACKEN
DOLPHIN
FLOP   
MAGNET 
SAUCER

What do the following expressions tell you about the ⍋ grade-up and ⍒ grade-down functions on high-rank arrays?

      ⍋4 2 2⍴'ABDCAADCBCDECDEF'
2 1 3 4
      ⍒4 2 2⍴'ABDCAADCBCDECDEF'
4 3 1 2

You have the power

One common type of iteration is to apply the same function again to the result of the previous application. In traditional mathematics, this is expressed with superscript notation:

\(f(x) = 1 + x\) Increment
\(p(x,y) = f^y(x)\) Add
\(m(x,y) = p^y(x,0)\) Multiply

We can express this with the power operator:

      Inc←{1+⍵}
      Plus←{(Inc⍣⍺)⍵}
      Times←{⍺(Plus⍣⍵)0}
      Power←{⍺(Times⍣⍵)1}

Primitive iterations are still loops

You might have noticed this already, but it is important to know that the rank operator F⍤j k l is conceptually a loop. It just happens to be that certain operations are parallelisable, and some of those are parallelised within the Dyalog interpreter.

We will give some details later in the section on performance.

Reduction is a loop

Primitive reductions are often optimised. For example, plus-reduction +/ is able to take advantage of vector instructions on certain machines and and-reduction ∧/ can quit early if a zero is found in the array.

We can observe differences by writing a custom function and comparing runtimes:

      ]runtime +/?1e7⍴0

* Benchmarking "+/?1e7⍴0"
             (ms) 
 CPU (avg):    94 
 Elapsed:      99 



      ]runtime {⍺+⍵}/?1e7⍴0

* Benchmarking "{⍺+⍵}/?1e7⍴0"
             (ms) 
 CPU (avg):  3688 
 Elapsed:    3723

Moving windows

Windowed-reduction ⍺ F/ ⍵ is an extension to reduction which applies an F-reduction F/ for a function F on a sliding window of size ⍺.

It is useful to use catenate to display the windowed selection of the array to which the reduction will be applied:

      3,/⍳10

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬──────┐
│1 2 3│2 3 4│3 4 5│4 5 6│5 6 7│6 7 8│7 8 9│8 9 10│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴──────┘

      3+/⍳10

6 9 12 15 18 21 24 27

You can think of this as a special case of stencil code, for which the primitive operator stencil ⌺ was added in version 16.0.

      1↓¯1↓{+/⍵}⌺3⊢⍳10

6 9 12 15 18 21 24 27

Don't forget scan!

Scan F\⍵ is another construct which is simple in a way that misleads you into thinking it is only used for very specific things. It is exactly a reduction F/ on successive prefixes of ⍵. The final value is F/⍵.

      +/⍳10
55
      +\⍳10
1 3 6 10 15 21 28 36 45 55

      ⌈\2 0 3 ¯1 4 2 6
2 2 3 3 4 4 6

However, scan can be used in many scenarios that you might not expect. Scans are often used in high performance expressions of partitioned-application functions which nowadays can be implemented with partitioning primitives (⍺⊂⍵ and ⍺⊆⍵), nested arrays and the each operator F¨.

For example, one YouTube video comparing APL and Haskell demonstrates one of the big differences in the APL approach in contrast to other types of programming.

      4 {1↓∊' '∘,¨⍺↑' '(≠⊆⊢)⍵} 'take the first four words'

take the first four

      4 {⍵⌿⍨⍺>+\' '=⍵} 'take the first four words'

take the first four

Despite both having types of function composition, Haskell and other functional programming languages tend to focus on the composition of those functions as the fundamental process to finding and refining solutions. In APL, we are usually most interested in the fundamental data transformation that is occurring, and using APL's inherently parallel, array-at-a-time primitives to achieve that transformation in a way that can tend towards simple and fast code.

Between integer and boolean arguments alone there are more interesting constructs than can be covered well here. You can find more on this topic by going to the following links:

Watch the Dyalog webinar about Boolean Scans and Reductions
Experiment with the examples in an interactive notebook on TryAPL
You can view the static notebook online

For and While

The traditional control structures such as for loops, while loops and if statements weren't introduced in Dyalog until version 8.0 in 1996. Usually, they are only used for program control on the outer levels, or if an algorithm explicitly requires that type of scalar looping.

The syntax is mentioned in the section on user-defined functions.

Performance note

When constructing loops, think about whether unnecessary computation is being performed.

For example,

:While LikelyToBeFales
:AndIf ExpensiveTest

is probably better than

:While LikelyToBeFales∧ExpensiveTest

You will also often see:

:While PreCondition
:AndIf OnlyComputableIfPreCondition

Problem set 8

Word Problems

We are going to do some text processing on a dictionary of words.

If you have access to the internet, paste the following into your session to download a text file dictionary (917kB in size) and store it as a nested vector of character vectors named words.

]Get bit.ly/unixwords
words ← (⎕UCS 10)(≠⊆⊢)unixwords

If you have the file on your computer (maybe it was given to you on a USB drive, for example) then you can load it into your workspace from disk using the following expressions.

(content encoding newline) ← ⎕NGET'/path/to/words.txt'
words ← (⎕UCS newline) (≠⊆⊢) content

Now answer the following questions about words.

How many words have at least 3 'e's in them?
How many words have exactly two consecutive 'e's in them? The first three such words are Aberdeen Abderdeen's and Aileen.
What is the shortest word with two consecutive 'a's?
What words have three consecutive double letters? For example, mississippi does not but misseetto does. Misseetto is not a real word.

A palindrome is the same when reversed. For example, racecar is a palindrome but racecat is not.
How many palindromes are there in words?
Which palindrome in words is the longest?
How many words have their letters arranged in alphabetical order?

Bell Numbers

A Bell number counts the possible partitions of a set. The n^th Bell number \(B_n\) counts the ways you can partition a set of \(n\) elements.

Here we will investigate 3 ways of computing Bell numbers.

Brute force

Write a function BellBrute which counts all of the unique partitions of length ⍵ by creating partitions as nested arrays.

Hint

Binary representations of decimal numbers can be used as partition vectors.
Triangle scheme

Implement the triangle scheme for calculations.
Recurrence relation of binomial coefficients The Bell numbers satisfy a recurrence relation involving binomial coefficients:

\(B_{n+1} = \sum_{k=0}^{n}\binom{n}{k}B_k\)

Implement BellRecur using this formula.

Four is Magic

Rosetta Code has the full problem description.

Start with a number. Spell that number out in words, count the number of letters and say it all aloud. For example, start with 6, print 'Six is three' and continue with the number 3. Once you reach 4, print four is magic.

      FourMagic 11
Eleven is six, six is three, three is five, five is four, four is magic.

Hash counting string

This problem is from week 102 of the Perl Weekly Challenge.

Write a monadic function HashCount which takes a scalar integer argument and returns a simple character vector where:

the string consists only of digits 0-9 and octothorpes AKA hashes, ‘#’
there are no two consecutive hashes: ‘##’ does not appear in your string
the last character is a hash
the number immediately preceding each hash (if it exists) is the position of that hash in the string, with the position being counted up from 1

      HashCount 1
#
      HashCount 2
2#
      HashCount 3
#3#
      HashCount 10
#3#5#7#10#
      HashCount 14
2#4#6#8#11#14#

Backspace

Write a function Backspace which takes a simple numeric vector argument and treats 0s like backspaces, removing successive numbers to their left unless none remain.

      Backspace 1 2 0
1
      Backspace 1 5 5 0 2 0 0 8
1 8

For an extra challenge, modify your function so that it can also accept a character vector where \b is treated as a single token and signifies a backspace character.