NAVIGATION

Programming with First-Class Functions

Stanza fully supports and encourages functional programming, however "Functional Programming" is intentionally not the title of this chapter. In the community, the term functional programming has been used to refer to two different concepts. The first is the concept of programming with first-class functions, where functions themselves are passed as arguments and stored in datastructures. This is the subject of this chapter.

The second concept refers to a style of programming revolving around the mathematical definition of functions; so called pure functions. A pure function is guaranteed to return the same result if called with the same arguments, and also not affect the environment in any way (e.g. by printing to the terminal). This style of programming is largely an exercise in manipulating immutable datastructures. It is also a powerful paradigm and will be the subject of a later chapter.

Nested Functions

As a gentle introduction to first-class functions we will start with nested functions. We hope the concept will seem straightforward, and then later we'll reveal that they are actually quite sophisticated underneath.

Here is a function that sorts an array of integers in increasing order.

defn selection-sort (xs:Array<Int>) :
   val n = length(xs)
   for i in 0 to (n - 1) do :
      var min-idx = i
      var min-val = xs[i]
      for j in (i + 1) to n do :
         if xs[j] < min-val :
            min-idx = j
            min-val = xs[j]
      if i != min-idx :
         xs[min-idx] = xs[i]
         xs[i] = min-val

Let's try it out on an array of random numbers.

defn main () :
   val xs = Array<Int>(10)
   xs[0] = 510
   xs[1] = 923
   xs[2] = 671
   xs[3] = 811
   xs[4] = -129
   xs[5] = -581
   xs[6] = 233
   xs[7] = -791
   xs[8] = 899
   xs[9] = 313

   selection-sort(xs)
   println(xs)

main()

It should print out

[-791 -581 -129 233 313 510 671 811 899 923]

By reading through the algorithm, you can see that the larger problem of sorting the array is actually composed of a number of smaller subproblems. For example, the lines

var min-idx = i
var min-val = xs[i]
for j in (i + 1) to n do :
   if xs[j] < min-val :
      min-idx = j
      min-val = xs[j]

compute the index of the minimum element between index i + 1 and index n. The lines

if i != min-idx :
   xs[min-idx] = xs[i]
   xs[i] = min-val

swaps the element at index i with the element at index min-idx. selection-sort is short enough that we can still understand the main algorithm even without explicitly dividing the problem into smaller ones. But as programs get larger, the ability to break up a larger problem into smaller ones is very important. Nested functions gives us a lot of power for doing this.

Let's define a nested function, index-of-min, that takes two indices start and end, and returns the index of the minimum element between indices start (inclusive) and end (exclusive).

defn index-of-min (start:Int, end:Int) :
   var min-idx = start
   var min-val = xs[start]
   for i in (start + 1) to end do :
      if xs[i] < min-val :
         min-idx = i
         min-val = xs[i]
   min-idx

Let's define another nested function, swap, that swaps the element in index i with the element in index j.

defn swap (i:Int, j:Int) :
   if i != j :
      val xs-i = xs[i]
      val xs-j = xs[j]
      xs[i] = xs-j
      xs[j] = xs-i

And now let's clean up our selection-sort function using these nested functions.

defn selection-sort (xs:Array<Int>) :
   defn index-of-min (start:Int, end:Int) :
      var min-idx = start
      var min-val = xs[start]
      for i in (start + 1) to end do :
         if xs[i] < min-val :
            min-idx = i
            min-val = xs[i]
      min-idx

   defn swap (i:Int, j:Int) :
      if i != j :
         val xs-i = xs[i]
         val xs-j = xs[j]
         xs[i] = xs-j
         xs[j] = xs-i
   
   val n = length(xs)
   for i in 0 to (n - 1) do :
      swap(i, index-of-min(i, n))

The code is slightly longer than before, but the overall algorithm is much clearer now.

for i in 0 to (n - 1) do :
   swap(i, index-of-min(i, n))

In English, it says: iterate with index i starting from 0 and proceeding to the end of the array, and swap the element at i with the minimum element in the rest of the array.

Notice that the nested functions index-of-min and swap are not merely functions declared within the body of selection-sort. If you tried to declare them as top-level functions, the program would give you this error when you try to compile it,

Could not resolve xs.

indicating that xs is not in scope and is not visible to index-of-min or swap. Part of the power of nested functions rests in them being able to refer to values defined in the function they're nested in.

Example: Permutations

Here is another example of using nested functions to greatly simplify code. The permutations function accepts an array of strings and prints out all possible permutations of its contents.

defn permutations (xs:Array<String>) :
   val n = length(xs)
   
   defn swap (i:Int, j:Int) :
      if i != j :
         val xi = xs[i]
         val xj = xs[j]
         xs[i] = xj
         xs[j] = xi
      
   defn permute (i:Int) :
      if i < n - 1 :
         for j in i to n do :
            swap(i, j)
            permute(i + 1)
            swap(i, j)
      else :
         println(xs)

   permute(0)

It internally relies upon the nested functions swap and permute.

Let's try it out with these strings.

defn main () :
   val xs = to-array<String>(["All" "Dogs" "Are" "Awesome"])
   permutations(xs)

main()

When compiled and ran, it prints out

["All" "Dogs" "Are" "Awesome"]
["All" "Dogs" "Awesome" "Are"]
["All" "Are" "Dogs" "Awesome"]
["All" "Are" "Awesome" "Dogs"]
["All" "Awesome" "Are" "Dogs"]
["All" "Awesome" "Dogs" "Are"]
["Dogs" "All" "Are" "Awesome"]
["Dogs" "All" "Awesome" "Are"]
["Dogs" "Are" "All" "Awesome"]
["Dogs" "Are" "Awesome" "All"]
["Dogs" "Awesome" "Are" "All"]
["Dogs" "Awesome" "All" "Are"]
["Are" "Dogs" "All" "Awesome"]
["Are" "Dogs" "Awesome" "All"]
["Are" "All" "Dogs" "Awesome"]
["Are" "All" "Awesome" "Dogs"]
["Are" "Awesome" "All" "Dogs"]
["Are" "Awesome" "Dogs" "All"]
["Awesome" "Dogs" "Are" "All"]
["Awesome" "Dogs" "All" "Are"]
["Awesome" "Are" "Dogs" "All"]
["Awesome" "Are" "All" "Dogs"]
["Awesome" "All" "Are" "Dogs"]
["Awesome" "All" "Dogs" "Are"]

As an exercise, try writing a function called combinations that prints out all combinations of an array of strings instead of all permutations.

Functions as Arguments

The selection-sort function in the previous example sorted the array in increasing order. But there are many ways to sort an array of integers. The following sort-by-abs function sorts the array by their absolute values.

defn sort-by-abs (xs:Array<Int>) :
   defn index-of-min (start:Int, end:Int) :
      var min-idx = start
      var min-val = xs[start]
      for i in (start + 1) to end do :
         if abs(xs[i]) < abs(min-val) :
            min-idx = i
            min-val = xs[i]
      min-idx

   defn swap (i:Int, j:Int) :
      if i != j :
         val xs-i = xs[i]
         val xs-j = xs[j]
         xs[i] = xs-j
         xs[j] = xs-i
   
   val n = length(xs)
   for i in 0 to (n - 1) do :
      swap(i, index-of-min(i, n))

If you replace the call to selection-sort in the main function with sort-by-abs then it now prints out

[-129 233 313 510 -581 671 -791 811 899 923]

Here is yet another way of sorting an array. The following sort-by-sum-of-digits function sorts the array by the total sum of their individual digits.

defn sum-of-digits (n:Int) :
   if n == 0 : 0
   else if n < 0 : sum-of-digits((- n))
   else : (n % 10) + sum-of-digits(n / 10)

defn sort-by-sum-of-digits (xs:Array<Int>) :
   defn index-of-min (start:Int, end:Int) :
      var min-idx = start
      var min-val = xs[start]
      for i in (start + 1) to end do :
         if sum-of-digits(xs[i]) < sum-of-digits(min-val) :
            min-idx = i
            min-val = xs[i]
      min-idx

   defn swap (i:Int, j:Int) :
      if i != j :
         val xs-i = xs[i]
         val xs-j = xs[j]
         xs[i] = xs-j
         xs[j] = xs-i
   
   val n = length(xs)
   for i in 0 to (n - 1) do :
      swap(i, index-of-min(i, n))

Replacing the call to selection-sort with sort-by-sum-of-digits prints out

[510 313 233 811 -129 671 -581 923 -791 899]

You'll have noticed by now that the implementation of each sorting function is almost entirely identical except for one line. Here are the three different comparison functions.

;Compare value directly
xs[i] < min-val

;Compare absolute values
abs(xs[i]) < abs(min-val)

;Compare the sum of their digits
sum-of-digits(xs[i]) < sum-of-digits(min-val)

Couldn't we somehow write a general sort function and give it a specific way to compare things? We can! And the solution is to accept a key function that, for each item in the array, computes the value you wish to sort by.

Here is the general sorting function, sort-by, that accepts a key function key.

defn sort-by (key:Int -> Int, xs:Array<Int>) :
   defn index-of-min (start:Int, end:Int) :
      var min-idx = start
      var min-val = xs[start]
      for i in (start + 1) to end do :
         if key(xs[i]) < key(min-val) :
            min-idx = i
            min-val = xs[i]
      min-idx

   defn swap (i:Int, j:Int) :
      if i != j :
         val xs-i = xs[i]
         val xs-j = xs[j]
         xs[i] = xs-j
         xs[j] = xs-i
   
   val n = length(xs)
   for i in 0 to (n - 1) do :
      swap(i, index-of-min(i, n))

Notice especially the type of the key argument.

Int -> Int

This says that key is a function that accepts a single argument, an Int, and returns an Int.

We can update our main function to sort the array in three different ways by using three different key functions.

defn identity (x:Int) : x
   
defn main () :
   val xs = Array<Int>(10)
   xs[0] = 510
   xs[1] = 923
   xs[2] = 671
   xs[3] = 811
   xs[4] = -129
   xs[5] = -581
   xs[6] = 233
   xs[7] = -791
   xs[8] = 899
   xs[9] = 313

   println("Sort by value directly.")
   sort-by(identity, xs)
   println(xs)

   println("Sort by absolute value.")
   sort-by(abs, xs)
   println(xs)

   println("Sort by sum of digits.")
   sort-by(sum-of-digits, xs)
   println(xs)
   
main()

Compiling and running the program prints out

Sort by value directly.
[-791 -581 -129 233 313 510 671 811 899 923]
Sort by absolute value.
[-129 233 313 510 -581 671 -791 811 899 923]
Sort by sum of digits.
[510 313 233 811 -129 671 -581 923 -791 899]

Up until now, we have always referred to a function in function call position. For example,

abs( ... )
sum-of-digits( ... )

But now you see that you can actually refer to functions directly as values to be passed to other functions!

sort-by(abs, xs)
sort-by(sum-of-digits, xs)

Functions that take functions as arguments are called higher-order functions. They are an extremely powerful programming technique, and you'll soon see that you've already been using them everywhere without knowing it.

Functions as Return Values

When a language has first-class functions, it means that functions can be treated as values. In the previous section we saw how to pass functions as arguments. Now we'll see how to use functions as return values.

Here's a function called digit that accepts a single argument n, and returns a function. What the returned function does is extract and return the n'th significant digit from its argument.

defn digit (n:Int) -> (Int -> Int) :
   defn extract-digit (x:Int, n:Int) :
      if x < 0 : extract-digit((- x), n)
      else if n == 0 : x % 10
      else : extract-digit(x / 10, n - 1)
   defn extract-digit-n (x:Int) :
      extract-digit(x, n)
   extract-digit-n

Let's try it out on some numbers.

defn main () :
   val first-digit = digit(0)
   val third-digit = digit(2)

   defn test-first-digit (x:Int) :
      println("The first digit of %_ is %_." % [x, first-digit(x)])
   test-first-digit(413)
   test-first-digit(-313)
   test-first-digit(41)
   test-first-digit(137)
   test-first-digit(991)

   defn test-third-digit (x:Int) :
      println("The third digit of %_ is %_." % [x, third-digit(x)])
   test-third-digit(413)
   test-third-digit(-313)
   test-third-digit(41)
   test-third-digit(137)
   test-third-digit(991)

main()

Compiling and running the program prints out

The first digit of 413 is 3.
The first digit of -313 is 3.
The first digit of 41 is 1.
The first digit of 137 is 7.
The first digit of 991 is 1.
The third digit of 413 is 4.
The third digit of -313 is 3.
The third digit of 41 is 0.
The third digit of 137 is 1.
The third digit of 991 is 9.

The type signature of digit is daunting at first.

defn digit (n:Int) -> (Int -> Int)

Let's decipher it piece by piece. digit is a function that takes a single Int argument, and returns a (Int -> Int). And we learned previously that a (Int -> Int) is a one argument function that takes an Int and returns an Int. The parentheses around Int -> Int is not strictly necessary as -> is a right-associative operator. Thus, digit can also be declared the following way.

defn digit (n:Int) -> Int -> Int

Write it in the way that is most clear to you. As an exercise, think about what the type of digit is.

Sorting By Digit

Now that we have a function for creating functions that are compatible with what is expected by sort-by, let's use sort-by to sort by different digits. Update the main function in our previous example.

defn main () :
   val xs = Array<Int>(10)
   xs[0] = 510
   xs[1] = 923
   xs[2] = 671
   xs[3] = 811
   xs[4] = -129
   xs[5] = -581
   xs[6] = 233
   xs[7] = -791
   xs[8] = 899
   xs[9] = 313

   println("Sort by value directly.")
   sort-by(identity, xs)
   println(xs)

   println("Sort by absolute value.")
   sort-by(abs, xs)
   println(xs)

   println("Sort by sum of digits.")
   sort-by(sum-of-digits, xs)
   println(xs)

   println("Sort by first digit.")
   sort-by(digit(0), xs)
   println(xs)

   println("Sort by second digit.")
   sort-by(digit(1), xs)
   println(xs)

   println("Sort by third digit.")
   sort-by(digit(2), xs)
   println(xs)

Compile and run the program. It should print out

Sort by value directly.
[-791 -581 -129 233 313 510 671 811 899 923]
Sort by absolute value.
[-129 233 313 510 -581 671 -791 811 899 923]
Sort by sum of digits.
[510 313 233 811 -129 671 -581 923 -791 899]
Sort by first digit.
[510 811 671 -581 -791 233 313 923 -129 899]
Sort by second digit.
[510 811 313 923 -129 233 671 -581 -791 899]
Sort by third digit.
[-129 233 313 510 -581 671 -791 811 899 923]

Isn't that elegant! This is but a small demonstration of the power of first-class functions.

Core Library Functions

The sort-by function is so general and useful that you might wonder whether it's already included in Stanza's core library. And it is, along with many other useful higher order functions. We'll show you a few of them here.

qsort!

The qsort! function is Stanza's included sorting function. It implements the quick sort algorithm, and you can use it sort collections in much the same way that you used the sort-by function. One big difference, though, is that qsort! works on many different kinds of objects whereas your sort-by function only worked on Int objects.

val xs = Vector<String>()
add(xs, "Patrick")
add(xs, "Luca")
add(xs, "Emmy")
add(xs, "Sunny")
add(xs, "Whiskey")
add(xs, "Rummy")
qsort!(xs)
println(xs)

The above is an example of sorting a vector of strings, and it prints out

["Emmy" "Luca" "Patrick" "Rummy" "Sunny" "Whiskey"]

qsort! can optionally take a key function as its first argument for computing the item with which to sort. Here's how to sort the xs vector by the second letter.

defn second-letter (s:String) : s[1]
qsort!(second-letter, xs)
println(xs)

Running the program prints out

["Patrick" "Whiskey" "Emmy" "Rummy" "Luca" "Sunny"]

The third form of qsort! takes, as its second argument, a comparison function with which to sort by. The comparison function is given two items from the collection and must return true if the first argument is less than the second argument, or false otherwise.

Here is an example of sorting a vector containing both integers and strings. Integers are less than other integers if their numeric value is smaller. Strings are compared against other strings according to their lexicographic order. And integers are less than strings if the integer is less than the length of the string.

val xs = Vector<Int|String>()
add(xs, 1)
add(xs, 3)
add(xs, "A")
add(xs, "B")
add(xs, 4)
add(xs, -10)
add(xs, "Timon")
add(xs, "Pumbaa")
add(xs, 42)

defn compare-items (a:Int|String, b:Int|String) :
   match(a, b) :
      (a:Int, b:Int) : a < b
      (a:Int, b:String) : a < length(b)
      (a:String, b:Int) : length(a) < b
      (a:String, b:String) : a < b
qsort!(xs, compare-items)
println(xs)

Running the program prints out

[-10 1 "A" "B" 3 4 "Pumbaa" "Timon" 42]

find

The find function looks for the first item in a collection that satisfies a condition. The condition is given as a function, and takes a single argument representing an item from the collection. The condition function must return true if the item satisfies the condition, or false otherwise. find returns the item if it is found, or false otherwise.

Here is an example of looking for the first capitalized word in a vector of strings.

val xs = Vector<String>()
add(xs, "they")
add(xs, "call")
add(xs, "me")
add(xs, "Mr")
add(xs, "Pig")

defn capitalized? (x:String) : upper-case?(x[0])
println(find(capitalized?, xs))

Running the program prints out

Mr

index-when

The index-when function is similar to find, and looks for the first item in a collection that satisfies a condition. The difference is if the item is found, then index-when returns its index.

Calling index-when instead of find on the previous example

println(index-when(capitalized?, xs))

prints out

Maybe Objects and first

A Maybe is used to indicate the presence or absence of an object. A None object is a subtype of Maybe and indicates there is no object. A One object is a subtype of Maybe and contains a wrapped object. You can retrieve the wrapped object in a One object using the value function.

The first function takes an argument function, f, and a collection xs, and calls f repeatedly on each item in the collection. f must return a Maybe object. first returns the first One object that is returned by f, or a None object if no call to f returns a One object.

Here is an example of using first to find the first even sum of digits in a vector of integers.

val xs = Vector<Int>()
add(xs, 14)
add(xs, 78)
add(xs, 232)
add(xs, 787)
add(xs, 49)

defn even-sum? (x:Int) :
   val s = sum-of-digits(x)
   if s % 2 == 0 : One(s)
   else : None()
match(first(even-sum?, xs)) :
   (x:One<Int>) :
      println("The first even sum of digits is %_." % [value(x)])
   (x:None) :
      println("No number in xs has an even sum of digits.")

map!

The map! function takes a function f and an array (or vector) xs. It then iterates through the array and replaces each item in the array with a call to f on the item.

Here is how to capitalize each entry in a vector of strings using map!.

val xs = Vector<String>()
add(xs, "they")
add(xs, "call")
add(xs, "me")
add(xs, "Mr")
add(xs, "Pig")   

defn capitalize (x:String) :
   append(upper-case(x[0 to 1]), x[1 to false])
map!(capitalize, xs)
println(xs)

When ran, it prints out

["They" "Call" "Me" "Mr" "Pig"]

all?, any?, none?

all? is used to determine whether every item in a collection satisfies some condition. The all? function takes a function f and a collection xs. It returns true if calling f on every item in xs returns true. If f returns false on any item then all? immediately returns false.

Here is how we can use all? to test whether all numbers in xs are positive.

val xs = Vector<Int>()
add(xs, 4)
add(xs, 2)
add(xs, 3)
add(xs, -8)
add(xs, 5)

defn positive? (x:Int) : x > 0
all?(positive?, xs)

The any? and none? functions work similarly. any? determines whether any item satisfies the condition, and none? determines whether no item satisfies the condition.

do

Finally we get to the most commonly used higher order function of them all: the do function. The do function takes a function f and a collection xs and calls f on each item in the collection.

Here is how to report the lengths of every string in a vector using do.

val xs = Vector<String>()
add(xs, "they")
add(xs, "call")
add(xs, "me")
add(xs, "Mr")
add(xs, "Pig")

defn report-length (x:String) :
   println("%_ has length %_." % [x, length(x)])
do(report-length, xs)

When ran, it prints out

they has length 4.
call has length 4.
me has length 2.
Mr has length 2.
Pig has length 3.

At this point, particularly precocious readers might start to suspect that they have already used do in their programs without knowing it.

Anonymous Functions

Before the introduction of higher-order functions it was natural for you to give every function in your program a name. After all, if a function has no name, then how would you call it? But after having been exposed to higher-order functions, you might now be wondering if it's possible to avoid giving functions a name. A lot of functions are now only ever used once, and only as an argument to another higher-order function.

Anonymous functions are functions without names. Here is report-length from the previous example written as an anonymous function.

fn (x:String) :
   println("%_ has length %_." % [x, length(x)])

Here is an example of rewriting the do example using an anonymous function.

val xs = Vector<String>()
add(xs, "they")
add(xs, "call")
add(xs, "me")
add(xs, "Mr")
add(xs, "Pig")
do(fn (x:String) :
      println("%_ has length %_." % [x, length(x)])
   xs)

Notice how the report-length function is now directly created using fn and passed immediately as an argument to do. The arguments to higher-order functions are often very short and anonymous functions provides a convenient syntax for using them.

Bidirectional Type Inference

The type inference rules for anonymous functions are different than those for named functions. For a named function, if a type annotation is left off of an argument, then the argument is assumed to have the ? type, and can accept anything. For an anonymous function, if a type annotation is left off of an argument, then the argument's type is inferred from the context in which the function is used.

Thus the call to do in the above example could be more concisely written as

do(fn (x) : println("%_ has length %_." % [x, length(x)])
   xs)

From the context, the type of xs is Vector<String>, and since do calls the function on each item in xs, it is obvious that x must be of type String.

Idiomatic Stanza code rarely contains type annotations for anonymous functions, and instead relies upon type inference. In certain circumstances, Stanza will be unable to infer the argument types, in which case you'll have to provide them explicitly.

Anonymous Function Shorthand

For extremely short anonymous functions, Stanza provides a syntactic shorthand. The following function

fn (x) : x + 1