-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter5.html
More file actions
31 lines (30 loc) · 56.7 KB
/
chapter5.html
File metadata and controls
31 lines (30 loc) · 56.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
<!DOCTYPE html>
<html>
<head>
<title>L.B.Stanza</title>
<link type="text/css" rel="stylesheet" href="resources/mainstyle.css">
<link type="text/css" rel="stylesheet" href="resources/documentation.css">
</head>
<body>
<table class="wrap">
<tr><td colspan="3" class="banner">
<a href="index.html">Home</a><a href="stanzabyexample.html">Table of Contents</a><a href="chapter4.html">Previous Chapter</a><a href="chapter6.html">Next Chapter</a>
</td></tr>
<tr>
<td class="nav">
<h1>NAVIGATION</h1>
<h2><a href="#anchor232">Programming with First-Class Functions</a></h2><h3><a href="#anchor53">Nested Functions</a></h3><h4><a href="#anchor233">Example: Permutations</a></h4><h3><a href="#anchor54">Functions as Arguments</a></h3><h3><a href="#anchor55">Functions as Return Values</a></h3><h4><a href="#anchor234">Sorting By Digit</a></h4><h3><a href="#anchor56">Core Library Functions</a></h3><h4><a href="#anchor235">qsort!</a></h4><h4><a href="#anchor236">find</a></h4><h4><a href="#anchor237">index-when</a></h4><h4><a href="#anchor238">Maybe Objects and first</a></h4><h4><a href="#anchor239">map!</a></h4><h4><a href="#anchor240">all?, any?, none?</a></h4><h4><a href="#anchor241">do</a></h4><h3><a href="#anchor57">Anonymous Functions</a></h3><h4><a href="#anchor242">Bidirectional Type Inference</a></h4><h4><a href="#anchor243">Anonymous Function Shorthand</a></h4><h4><a href="#anchor244">Curried Function Shorthand</a></h4><h4><a href="#anchor245">The Application Operator</a></h4><h3><a href="#anchor58">The For Construct</a></h3><h4><a href="#anchor246">Operating Functions</a></h4><h3><a href="#anchor59">Stanza Idioms</a></h3><h3><a href="#anchor60">Tail Calls</a></h3><h4><a href="#anchor247">An Iterative Algorithm</a></h4><h4><a href="#anchor248">Tail Call Optimization</a></h4><h3><a href="#anchor61">Revisiting While</a></h3>
</td>
<td class="main">
<h1 id="anchor232">Programming with First-Class Functions</h1><p>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 <span style="font-style:italic;">first-class</span> functions, where functions themselves are passed as arguments and stored in datastructures. This is the subject of this chapter. </p><p>The second concept refers to a style of programming revolving around the mathematical definition of functions; so called <span style="font-style:italic;">pure</span> 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. </p><h2 id="anchor53">Nested Functions</h2><p>As a gentle introduction to first-class functions we will start with <span style="font-style:italic;">nested</span> functions. We hope the concept will seem straightforward, and then later we'll reveal that they are actually quite sophisticated underneath.</p><p>Here is a function that sorts an array of integers in increasing order.</p><pre><code>defn selection-sort (xs:Array<Int>) :<br> val n = length(xs)<br> for i in 0 to (n - 1) do :<br> var min-idx = i<br> var min-val = xs[i]<br> for j in (i + 1) to n do :<br> if xs[j] < min-val :<br> min-idx = j<br> min-val = xs[j]<br> if i != min-idx :<br> xs[min-idx] = xs[i]<br> xs[i] = min-val</code></pre><p>Let's try it out on an array of random numbers.</p><pre><code>defn main () :<br> val xs = Array<Int>(10)<br> xs[0] = 510<br> xs[1] = 923<br> xs[2] = 671<br> xs[3] = 811<br> xs[4] = -129<br> xs[5] = -581<br> xs[6] = 233<br> xs[7] = -791<br> xs[8] = 899<br> xs[9] = 313<br><br> selection-sort(xs)<br> println(xs)<br><br>main()</code></pre><p>It should print out</p><pre><code>[-791 -581 -129 233 313 510 671 811 899 923]</code></pre><p>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</p><pre><code>var min-idx = i<br>var min-val = xs[i]<br>for j in (i + 1) to n do :<br> if xs[j] < min-val :<br> min-idx = j<br> min-val = xs[j]</code></pre><p>compute the index of the minimum element between index <code>i + 1</code> and index <code>n</code>. The lines</p><pre><code>if i != min-idx :<br> xs[min-idx] = xs[i]<br> xs[i] = min-val</code></pre><p>swaps the element at index <code>i</code> with the element at index <code>min-idx</code>. <code>selection-sort</code> 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. </p><p>Let's define a <span style="font-style:italic;">nested</span> function, <code>index-of-min</code>, that takes two indices <code>start</code> and <code>end</code>, and returns the index of the minimum element between indices <code>start</code> (inclusive) and <code>end</code> (exclusive).</p><pre><code>defn index-of-min (start:Int, end:Int) :<br> var min-idx = start<br> var min-val = xs[start]<br> for i in (start + 1) to end do :<br> if xs[i] < min-val :<br> min-idx = i<br> min-val = xs[i]<br> min-idx </code></pre><p>Let's define another nested function, <code>swap</code>, that swaps the element in index <code>i</code> with the element in index <code>j</code>. </p><pre><code>defn swap (i:Int, j:Int) :<br> if i != j :<br> val xs-i = xs[i]<br> val xs-j = xs[j]<br> xs[i] = xs-j<br> xs[j] = xs-i</code></pre><p>And now let's clean up our <code>selection-sort</code> function using these nested functions.</p><pre><code>defn selection-sort (xs:Array<Int>) :<br> defn index-of-min (start:Int, end:Int) :<br> var min-idx = start<br> var min-val = xs[start]<br> for i in (start + 1) to end do :<br> if xs[i] < min-val :<br> min-idx = i<br> min-val = xs[i]<br> min-idx<br><br> defn swap (i:Int, j:Int) :<br> if i != j :<br> val xs-i = xs[i]<br> val xs-j = xs[j]<br> xs[i] = xs-j<br> xs[j] = xs-i<br> <br> val n = length(xs)<br> for i in 0 to (n - 1) do :<br> swap(i, index-of-min(i, n))</code></pre><p>The code is slightly longer than before, but the <span style="font-style:italic;">overall</span> algorithm is <span style="font-style:italic;">much</span> clearer now. </p><pre><code>for i in 0 to (n - 1) do :<br> swap(i, index-of-min(i, n))</code></pre><p>In English, it says: iterate with index <code>i</code> starting from 0 and proceeding to the end of the array, and swap the element at <code>i</code> with the minimum element in the rest of the array. </p><p>Notice that the nested functions <code>index-of-min</code> and <code>swap</code> are not merely functions declared within the body of <code>selection-sort</code>. If you tried to declare them as top-level functions, the program would give you this error when you try to compile it,</p><pre><code>Could not resolve xs.</code></pre><p>indicating that <code>xs</code> is not in scope and is not visible to <code>index-of-min</code> or <code>swap</code>. Part of the power of nested functions rests in them being able to refer to values defined in the function they're nested in.</p><h3 id="anchor233">Example: Permutations</h3><p>Here is another example of using nested functions to greatly simplify code. The <code>permutations</code> function accepts an array of strings and prints out all possible permutations of its contents. </p><pre><code>defn permutations (xs:Array<String>) :<br> val n = length(xs)<br> <br> defn swap (i:Int, j:Int) :<br> if i != j :<br> val xi = xs[i]<br> val xj = xs[j]<br> xs[i] = xj<br> xs[j] = xi<br> <br> defn permute (i:Int) :<br> if i < n - 1 :<br> for j in i to n do :<br> swap(i, j)<br> permute(i + 1)<br> swap(i, j)<br> else :<br> println(xs)<br><br> permute(0)</code></pre><p>It internally relies upon the nested functions <code>swap</code> and <code>permute</code>. </p><p>Let's try it out with these strings.</p><pre><code>defn main () :<br> val xs = to-array<String>(["All" "Dogs" "Are" "Awesome"])<br> permutations(xs)<br><br>main()</code></pre><p>When compiled and ran, it prints out</p><pre><code>["All" "Dogs" "Are" "Awesome"]<br>["All" "Dogs" "Awesome" "Are"]<br>["All" "Are" "Dogs" "Awesome"]<br>["All" "Are" "Awesome" "Dogs"]<br>["All" "Awesome" "Are" "Dogs"]<br>["All" "Awesome" "Dogs" "Are"]<br>["Dogs" "All" "Are" "Awesome"]<br>["Dogs" "All" "Awesome" "Are"]<br>["Dogs" "Are" "All" "Awesome"]<br>["Dogs" "Are" "Awesome" "All"]<br>["Dogs" "Awesome" "Are" "All"]<br>["Dogs" "Awesome" "All" "Are"]<br>["Are" "Dogs" "All" "Awesome"]<br>["Are" "Dogs" "Awesome" "All"]<br>["Are" "All" "Dogs" "Awesome"]<br>["Are" "All" "Awesome" "Dogs"]<br>["Are" "Awesome" "All" "Dogs"]<br>["Are" "Awesome" "Dogs" "All"]<br>["Awesome" "Dogs" "Are" "All"]<br>["Awesome" "Dogs" "All" "Are"]<br>["Awesome" "Are" "Dogs" "All"]<br>["Awesome" "Are" "All" "Dogs"]<br>["Awesome" "All" "Are" "Dogs"]<br>["Awesome" "All" "Dogs" "Are"]</code></pre><p>As an exercise, try writing a function called <code>combinations</code> that prints out all <span style="font-style:italic;">combinations</span> of an array of strings instead of all <span style="font-style:italic;">permutations</span>. </p><h2 id="anchor54">Functions as Arguments</h2><p>The <code>selection-sort</code> function in the previous example sorted the array in increasing order. But there are many ways to sort an array of integers. The following <code>sort-by-abs</code> function sorts the array by their <span style="font-style:italic;">absolute</span> values. </p><pre><code>defn sort-by-abs (xs:Array<Int>) :<br> defn index-of-min (start:Int, end:Int) :<br> var min-idx = start<br> var min-val = xs[start]<br> for i in (start + 1) to end do :<br> if abs(xs[i]) < abs(min-val) :<br> min-idx = i<br> min-val = xs[i]<br> min-idx<br><br> defn swap (i:Int, j:Int) :<br> if i != j :<br> val xs-i = xs[i]<br> val xs-j = xs[j]<br> xs[i] = xs-j<br> xs[j] = xs-i<br> <br> val n = length(xs)<br> for i in 0 to (n - 1) do :<br> swap(i, index-of-min(i, n))</code></pre><p>If you replace the call to <code>selection-sort</code> in the <code>main</code> function with <code>sort-by-abs</code> then it now prints out</p><pre><code>[-129 233 313 510 -581 671 -791 811 899 923]</code></pre><p>Here is yet another way of sorting an array. The following <code>sort-by-sum-of-digits</code> function sorts the array by the total sum of their individual digits.</p><pre><code>defn sum-of-digits (n:Int) :<br> if n == 0 : 0<br> else if n < 0 : sum-of-digits((- n))<br> else : (n % 10) + sum-of-digits(n / 10)<br><br>defn sort-by-sum-of-digits (xs:Array<Int>) :<br> defn index-of-min (start:Int, end:Int) :<br> var min-idx = start<br> var min-val = xs[start]<br> for i in (start + 1) to end do :<br> if sum-of-digits(xs[i]) < sum-of-digits(min-val) :<br> min-idx = i<br> min-val = xs[i]<br> min-idx<br><br> defn swap (i:Int, j:Int) :<br> if i != j :<br> val xs-i = xs[i]<br> val xs-j = xs[j]<br> xs[i] = xs-j<br> xs[j] = xs-i<br> <br> val n = length(xs)<br> for i in 0 to (n - 1) do :<br> swap(i, index-of-min(i, n))</code></pre><p>Replacing the call to <code>selection-sort</code> with <code>sort-by-sum-of-digits</code> prints out</p><pre><code>[510 313 233 811 -129 671 -581 923 -791 899]</code></pre><p>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.</p><pre><code>;Compare value directly<br>xs[i] < min-val<br><br>;Compare absolute values<br>abs(xs[i]) < abs(min-val)<br><br>;Compare the sum of their digits<br>sum-of-digits(xs[i]) < sum-of-digits(min-val)</code></pre><p>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 <span style="font-style:italic;">key</span> function that, for each item in the array, computes the value you wish to sort by.</p><p>Here is the general sorting function, <code>sort-by</code>, that accepts a key function <code>key</code>.</p><pre><code>defn sort-by (key:Int -> Int, xs:Array<Int>) :<br> defn index-of-min (start:Int, end:Int) :<br> var min-idx = start<br> var min-val = xs[start]<br> for i in (start + 1) to end do :<br> if key(xs[i]) < key(min-val) :<br> min-idx = i<br> min-val = xs[i]<br> min-idx<br><br> defn swap (i:Int, j:Int) :<br> if i != j :<br> val xs-i = xs[i]<br> val xs-j = xs[j]<br> xs[i] = xs-j<br> xs[j] = xs-i<br> <br> val n = length(xs)<br> for i in 0 to (n - 1) do :<br> swap(i, index-of-min(i, n))</code></pre><p>Notice especially the type of the <code>key</code> argument.</p><pre><code>Int -> Int</code></pre><p>This says that <code>key</code> is a <span style="font-style:italic;">function</span> that accepts a single argument, an <code>Int</code>, and returns an <code>Int</code>.</p><p>We can update our <code>main</code> function to sort the array in three different ways by using three different key functions.</p><pre><code>defn identity (x:Int) : x<br> <br>defn main () :<br> val xs = Array<Int>(10)<br> xs[0] = 510<br> xs[1] = 923<br> xs[2] = 671<br> xs[3] = 811<br> xs[4] = -129<br> xs[5] = -581<br> xs[6] = 233<br> xs[7] = -791<br> xs[8] = 899<br> xs[9] = 313<br><br> println("Sort by value directly.")<br> sort-by(identity, xs)<br> println(xs)<br><br> println("Sort by absolute value.")<br> sort-by(abs, xs)<br> println(xs)<br><br> println("Sort by sum of digits.")<br> sort-by(sum-of-digits, xs)<br> println(xs)<br> <br>main()</code></pre><p>Compiling and running the program prints out</p><pre><code>Sort by value directly.<br>[-791 -581 -129 233 313 510 671 811 899 923]<br>Sort by absolute value.<br>[-129 233 313 510 -581 671 -791 811 899 923]<br>Sort by sum of digits.<br>[510 313 233 811 -129 671 -581 923 -791 899]</code></pre> <p>Up until now, we have always referred to a function in <span style="font-style:italic;">function call position</span>. For example,</p><pre><code>abs( ... )<br>sum-of-digits( ... )</code></pre><p>But now you see that you can actually refer to functions directly as values to be passed to other functions!</p><pre><code>sort-by(abs, xs)<br>sort-by(sum-of-digits, xs)</code></pre><p>Functions that take functions as arguments are called <span style="font-style:italic;">higher-order functions</span>. They are an <span style="font-style:italic;">extremely</span> powerful programming technique, and you'll soon see that you've already been using them everywhere without knowing it. </p><h2 id="anchor55">Functions as Return Values</h2><p>When a language has <span style="font-style:italic;">first-class</span> 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.</p><p>Here's a function called <code>digit</code> that accepts a single argument <code>n</code>, and returns a <span style="font-style:italic;">function</span>. What the <span style="font-style:italic;">returned</span> function does is extract and return the <code>n</code>'th significant digit from its argument.</p><pre><code>defn digit (n:Int) -> (Int -> Int) :<br> defn extract-digit (x:Int, n:Int) :<br> if x < 0 : extract-digit((- x), n)<br> else if n == 0 : x % 10<br> else : extract-digit(x / 10, n - 1)<br> defn extract-digit-n (x:Int) :<br> extract-digit(x, n)<br> extract-digit-n</code></pre><p>Let's try it out on some numbers.</p><pre><code>defn main () :<br> val first-digit = digit(0)<br> val third-digit = digit(2)<br><br> defn test-first-digit (x:Int) :<br> println("The first digit of %_ is %_." % [x, first-digit(x)])<br> test-first-digit(413)<br> test-first-digit(-313)<br> test-first-digit(41)<br> test-first-digit(137)<br> test-first-digit(991)<br><br> defn test-third-digit (x:Int) :<br> println("The third digit of %_ is %_." % [x, third-digit(x)])<br> test-third-digit(413)<br> test-third-digit(-313)<br> test-third-digit(41)<br> test-third-digit(137)<br> test-third-digit(991)<br><br>main() </code></pre><p>Compiling and running the program prints out</p><pre><code>The first digit of 413 is 3.<br>The first digit of -313 is 3.<br>The first digit of 41 is 1.<br>The first digit of 137 is 7.<br>The first digit of 991 is 1.<br>The third digit of 413 is 4.<br>The third digit of -313 is 3.<br>The third digit of 41 is 0.<br>The third digit of 137 is 1.<br>The third digit of 991 is 9.</code></pre><p>The type signature of <code>digit</code> is daunting at first. </p><pre><code>defn digit (n:Int) -> (Int -> Int)</code></pre><p>Let's decipher it piece by piece. <code>digit</code> is a function that takes a single <code>Int</code> argument, and returns a <code>(Int -> Int)</code>. And we learned previously that a <code>(Int -> Int)</code> is a one argument function that takes an <code>Int</code> and returns an <code>Int</code>. The parentheses around <code>Int -> Int</code> is not strictly necessary as <code>-></code> is a right-associative operator. Thus, <code>digit</code> can also be declared the following way.</p><pre><code>defn digit (n:Int) -> Int -> Int</code></pre><p>Write it in the way that is most clear to you. As an exercise, think about what the type of <code>digit</code> is. </p><h3 id="anchor234">Sorting By Digit</h3><p>Now that we have a function for creating functions that are compatible with what is expected by <code>sort-by</code>, let's use <code>sort-by</code> to sort by different digits. Update the <code>main</code> function in our previous example.</p><pre><code>defn main () :<br> val xs = Array<Int>(10)<br> xs[0] = 510<br> xs[1] = 923<br> xs[2] = 671<br> xs[3] = 811<br> xs[4] = -129<br> xs[5] = -581<br> xs[6] = 233<br> xs[7] = -791<br> xs[8] = 899<br> xs[9] = 313<br><br> println("Sort by value directly.")<br> sort-by(identity, xs)<br> println(xs)<br><br> println("Sort by absolute value.")<br> sort-by(abs, xs)<br> println(xs)<br><br> println("Sort by sum of digits.")<br> sort-by(sum-of-digits, xs)<br> println(xs)<br><br> println("Sort by first digit.")<br> sort-by(digit(0), xs)<br> println(xs)<br><br> println("Sort by second digit.")<br> sort-by(digit(1), xs)<br> println(xs)<br><br> println("Sort by third digit.")<br> sort-by(digit(2), xs)<br> println(xs) </code></pre><p>Compile and run the program. It should print out</p><pre><code>Sort by value directly.<br>[-791 -581 -129 233 313 510 671 811 899 923]<br>Sort by absolute value.<br>[-129 233 313 510 -581 671 -791 811 899 923]<br>Sort by sum of digits.<br>[510 313 233 811 -129 671 -581 923 -791 899]<br>Sort by first digit.<br>[510 811 671 -581 -791 233 313 923 -129 899]<br>Sort by second digit.<br>[510 811 313 923 -129 233 671 -581 -791 899]<br>Sort by third digit.<br>[-129 233 313 510 -581 671 -791 811 899 923]</code></pre><p>Isn't that elegant! This is but a small demonstration of the power of first-class functions. </p><h2 id="anchor56">Core Library Functions</h2><p>The <code>sort-by</code> 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.</p><h3 id="anchor235">qsort!</h3><p>The <code>qsort!</code> 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 <code>sort-by</code> function. One big difference, though, is that <code>qsort!</code> works on many different kinds of objects whereas your <code>sort-by</code> function only worked on <code>Int</code> objects. </p><pre><code>val xs = Vector<String>()<br>add(xs, "Patrick")<br>add(xs, "Luca")<br>add(xs, "Emmy")<br>add(xs, "Sunny")<br>add(xs, "Whiskey")<br>add(xs, "Rummy")<br>qsort!(xs)<br>println(xs)</code></pre><p>The above is an example of sorting a vector of strings, and it prints out</p><pre><code>["Emmy" "Luca" "Patrick" "Rummy" "Sunny" "Whiskey"]</code></pre><p><code>qsort!</code> can optionally take a key function as its first argument for computing the item with which to sort. Here's how to sort the <code>xs</code> vector by the second letter.</p><pre><code>defn second-letter (s:String) : s[1]<br>qsort!(second-letter, xs)<br>println(xs)</code></pre><p>Running the program prints out</p><pre><code>["Patrick" "Whiskey" "Emmy" "Rummy" "Luca" "Sunny"]</code></pre><p>The third form of <code>qsort!</code> takes, as its second argument, a <span style="font-style:italic;">comparison</span> function with which to sort by. The comparison function is given two items from the collection and must return <code>true</code> if the first argument is less than the second argument, or <code>false</code> otherwise. </p><p>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.</p><pre><code>val xs = Vector<Int|String>()<br>add(xs, 1)<br>add(xs, 3)<br>add(xs, "A")<br>add(xs, "B")<br>add(xs, 4)<br>add(xs, -10)<br>add(xs, "Timon")<br>add(xs, "Pumbaa")<br>add(xs, 42)<br><br>defn compare-items (a:Int|String, b:Int|String) :<br> match(a, b) :<br> (a:Int, b:Int) : a < b<br> (a:Int, b:String) : a < length(b)<br> (a:String, b:Int) : length(a) < b<br> (a:String, b:String) : a < b<br>qsort!(xs, compare-items)<br>println(xs)</code></pre><p>Running the program prints out</p><pre><code>[-10 1 "A" "B" 3 4 "Pumbaa" "Timon" 42]</code></pre><h3 id="anchor236">find</h3><p>The <code>find</code> 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 <code>true</code> if the item satisfies the condition, or <code>false</code> otherwise. <code>find</code> returns the item if it is found, or <code>false</code> otherwise. </p><p>Here is an example of looking for the first capitalized word in a vector of strings.</p><pre><code>val xs = Vector<String>()<br>add(xs, "they")<br>add(xs, "call")<br>add(xs, "me")<br>add(xs, "Mr")<br>add(xs, "Pig")<br><br>defn capitalized? (x:String) : upper-case?(x[0])<br>println(find(capitalized?, xs))</code></pre><p>Running the program prints out</p><pre><code>Mr</code></pre><h3 id="anchor237">index-when</h3><p>The <code>index-when</code> function is similar to <code>find</code>, and looks for the first item in a collection that satisfies a condition. The difference is if the item is found, then <code>index-when</code> returns its <span style="font-style:italic;">index</span>. </p><p>Calling <code>index-when</code> instead of <code>find</code> on the previous example</p><pre><code>println(index-when(capitalized?, xs))</code></pre><p>prints out</p><pre><code>3</code></pre><h3 id="anchor238">Maybe Objects and first</h3><p>A <code>Maybe</code> is used to indicate the presence or absence of an object. A <code>None</code> object is a subtype of <code>Maybe</code> and indicates there is no object. A <code>One</code> object is a subtype of <code>Maybe</code> and contains a wrapped object. You can retrieve the wrapped object in a <code>One</code> object using the <code>value</code> function.</p><p>The <code>first</code> function takes an argument function, <code>f</code>, and a collection <code>xs</code>, and calls <code>f</code> repeatedly on each item in the collection. <code>f</code> must return a <code>Maybe</code> object. <code>first</code> returns the first <code>One</code> object that is returned by <code>f</code>, or a <code>None</code> object if no call to <code>f</code> returns a <code>One</code> object.</p><p>Here is an example of using first to find the first even sum of digits in a vector of integers.</p><pre><code>val xs = Vector<Int>()<br>add(xs, 14)<br>add(xs, 78)<br>add(xs, 232)<br>add(xs, 787)<br>add(xs, 49)<br><br>defn even-sum? (x:Int) :<br> val s = sum-of-digits(x)<br> if s % 2 == 0 : One(s)<br> else : None()<br>match(first(even-sum?, xs)) :<br> (x:One<Int>) :<br> println("The first even sum of digits is %_." % [value(x)])<br> (x:None) :<br> println("No number in xs has an even sum of digits.")</code></pre><h3 id="anchor239">map!</h3><p>The <code>map!</code> function takes a function <code>f</code> and an array (or vector) <code>xs</code>. It then iterates through the array and replaces each item in the array with a call to <code>f</code> on the item. </p><p>Here is how to capitalize each entry in a vector of strings using <code>map!</code>.</p><pre><code>val xs = Vector<String>()<br>add(xs, "they")<br>add(xs, "call")<br>add(xs, "me")<br>add(xs, "Mr")<br>add(xs, "Pig") <br><br>defn capitalize (x:String) :<br> append(upper-case(x[0 to 1]), x[1 to false])<br>map!(capitalize, xs)<br>println(xs)</code></pre><p>When ran, it prints out</p><pre><code>["They" "Call" "Me" "Mr" "Pig"]</code></pre><h3 id="anchor240">all?, any?, none?</h3><p><code>all?</code> is used to determine whether <span style="font-style:italic;">every</span> item in a collection satisfies some condition. The <code>all?</code> function takes a function <code>f</code> and a collection <code>xs</code>. It returns <code>true</code> if calling <code>f</code> on every item in <code>xs</code> returns <code>true</code>. If <code>f</code> returns <code>false</code> on any item then <code>all?</code> immediately returns <code>false</code>. </p><p>Here is how we can use <code>all?</code> to test whether all numbers in <code>xs</code> are positive.</p><pre><code>val xs = Vector<Int>()<br>add(xs, 4)<br>add(xs, 2)<br>add(xs, 3)<br>add(xs, -8)<br>add(xs, 5)<br><br>defn positive? (x:Int) : x > 0<br>all?(positive?, xs)</code></pre><p>The <code>any?</code> and <code>none?</code> functions work similarly. <code>any?</code> determines whether <span style="font-style:italic;">any</span> item satisfies the condition, and <code>none?</code> determines whether <span style="font-style:italic;">no</span> item satisfies the condition.</p><h3 id="anchor241">do</h3><p>Finally we get to the <span style="font-style:italic;">most</span> commonly used higher order function of them all: the <code>do</code> function. The <code>do</code> function takes a function <code>f</code> and a collection <code>xs</code> and calls <code>f</code> on each item in the collection.</p><p>Here is how to report the lengths of every string in a vector using <code>do</code>. </p><pre><code>val xs = Vector<String>()<br>add(xs, "they")<br>add(xs, "call")<br>add(xs, "me")<br>add(xs, "Mr")<br>add(xs, "Pig")<br><br>defn report-length (x:String) :<br> println("%_ has length %_." % [x, length(x)])<br>do(report-length, xs)</code></pre><p>When ran, it prints out</p><pre><code>they has length 4.<br>call has length 4.<br>me has length 2.<br>Mr has length 2.<br>Pig has length 3.</code></pre><p>At this point, particularly precocious readers might start to suspect that they have already used <code>do</code> in their programs without knowing it.</p><h2 id="anchor57">Anonymous Functions</h2><p>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 <span style="font-style:italic;">avoid</span> giving functions a name. A lot of functions are now only ever used once, and only as an argument to another higher-order function. </p><p><span style="font-style:italic;">Anonymous functions</span> are functions without names. Here is <code>report-length</code> from the previous example written as an anonymous function.</p><pre><code>fn (x:String) :<br> println("%_ has length %_." % [x, length(x)])</code></pre><p>Here is an example of rewriting the <code>do</code> example using an anonymous function.</p><pre><code>val xs = Vector<String>()<br>add(xs, "they")<br>add(xs, "call")<br>add(xs, "me")<br>add(xs, "Mr")<br>add(xs, "Pig")<br>do(fn (x:String) :<br> println("%_ has length %_." % [x, length(x)])<br> xs)</code></pre><p>Notice how the <code>report-length</code> function is now directly created using <code>fn</code> and passed immediately as an argument to <code>do</code>. The arguments to higher-order functions are often very short and anonymous functions provides a convenient syntax for using them.</p><h3 id="anchor242">Bidirectional Type Inference</h3><p>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 <code>?</code> 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. </p><p>Thus the call to <code>do</code> in the above example could be more concisely written as</p><pre><code>do(fn (x) : println("%_ has length %_." % [x, length(x)])<br> xs)</code></pre><p>From the context, the type of <code>xs</code> is <code>Vector<String></code>, and since <code>do</code> calls the function on each item in <code>xs</code>, it is obvious that <code>x</code> must be of type <code>String</code>.</p><p>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.</p><h3 id="anchor243">Anonymous Function Shorthand</h3><p>For <span style="font-style:italic;">extremely</span> short anonymous functions, Stanza provides a syntactic shorthand. The following function</p><pre><code>fn (x) : x + 1</code></pre><p>can be written equivalently as</p><pre><code>{_ + 1}</code></pre><p>As another example, the following function</p><pre><code>fn (x, y) : x + 2 * y</code></pre><p>can be written equivalently as</p><pre><code>{_ + 2 * _}</code></pre><p>The shorthand consists of surrounding the function body with the <code>{}</code> brackets, and using underscores to denote arguments. To create anonymous functions with explicit type annotations use the following form.</p><pre><code>fn (x:Int, y:String) : x + length(y)</code></pre><p>can be written equivalently as</p><pre><code>{_:Int + 2 * _:String}</code></pre><h3 id="anchor244">Curried Function Shorthand</h3><p>For <span style="font-style:italic;">extremely</span> short anonymous functions consisting of a single function call, Stanza provides another syntactic shorthand. The following function</p><pre><code>fn (xs) : qsort!(abs, xs)</code></pre><p>can be written equivalently as</p><pre><code>qsort!{abs, _}</code></pre><p>Similarly, to create anonymous functions with explicit type annotations use the following form.</p><pre><code>fn (i:Int) : index-of-min(i, length(xs))</code></pre><p>can be written equivalently as</p><pre><code>index-of-min{_:Int, length(xs)}</code></pre><h3 id="anchor245">The Application Operator</h3><p>With the introduction of anonymous functions, you'll find that you can implement lots of functionality using single lines of code. To help with this programming style, Stanza provides the <code>$</code> operator to help reduce the number of nested expressions. The expression</p><pre><code>f $ x</code></pre><p>is equivalent to </p><pre><code>f(x)</code></pre><p>Thus the <code>$</code> operator is just a shorthand for function application. Notice, however, that with the <code>$</code> operator, the above expression did not require any parentheses. </p><p>There is a very common usage pattern involving both curried functions and the <code>$</code> operator. Here is what it looks like.</p><pre><code>f{x, _} $ y</code></pre><p>Let's remove the syntactic shorthands incrementally to figure out what the above means. First, we will write out the <code>$</code> operator in full.</p><pre><code>(f{x, _})(y)</code></pre><p>Next, we will write out the curried function in full.</p><pre><code>(fn (a) : f(x, a))(y)</code></pre><p>So the expression, when written in full, just creates an anonymous function and then immediately calls it with <code>y</code>. Calling the anonymous function is then equivalent to</p><pre><code>f(x, y)</code></pre><p>Thus the expression</p><pre><code>f{x, _} $ y</code></pre><p>is equivalent to</p><pre><code>f(x, y)</code></pre><p>You can think of the <code>$</code> operator as substituting the right hand side expression in for the underscores in the left hand side expression. </p><p>This usage pattern is often used to chain a long sequence of operations together.</p><pre><code>f{1, _} $<br> head $<br> g{2, _} $<br> xs[2]</code></pre><p>is a shorthand for writing</p><pre><code>val result1 = xs[2]<br>val result2 = g(2, result1)<br>val result3 = head(result2)<br>f(1, result3)</code></pre><p>Here is a concrete example of an idiomatic usage of the <code>$</code> operator. In the demonstration of the <code>qsort!</code> operator, we explicitly created a <code>compare-items</code> function to pass into <code>qsort!</code>.</p><pre><code>defn compare-items (a:Int|String, b:Int|String) :<br> match(a, b) :<br> (a:Int, b:Int) : a < b<br> (a:Int, b:String) : a < length(b)<br> (a:String, b:Int) : length(a) < b<br> (a:String, b:String) : a < b<br>qsort!(xs, compare-items)</code></pre><p>But here is another way it can be (and often is) written.</p><pre><code>qsort!{xs, _} $ fn (a, b) :<br> match(a, b) :<br> (a:Int, b:Int) : a < b<br> (a:Int, b:String) : a < length(b)<br> (a:String, b:Int) : length(a) < b<br> (a:String, b:String) : a < b </code></pre><p>Since the types of the arguments of anonymous functions are inferred, there is also no need to provide explicit type annotations.</p><h2 id="anchor58">The For Construct</h2><p>Now that you've been introduced to anonymous functions and higher-order functions, we are now ready to introduce the <span style="font-style:italic;">full</span> for construct. The expression</p><pre><code>for x in xs do :<br> println(x)</code></pre><p>is equivalent to</p><pre><code>do(fn (x) :<br> println(x)<br> xs) </code></pre><p>As mentioned before, the for construct is not a looping mechanism. It is a syntactic shorthand for calling higher-order functions of a certain form. As explained earlier, the <code>do</code> function is what's responsible for looping over each element in <code>xs</code>. </p><p>The for construct can be called with multiple bindings as well.</p><pre><code>for (x in xs, y in ys) do :<br> println(x + y)</code></pre><p>is equivalent to</p><pre><code>do(fn (x, y) :<br> println(x + y)<br> xs, ys) </code></pre><p>Thus, in general, the for construct expands to a call to a higher order function where the first argument is an anonymous function followed by n remaining arguments. The anonymous function must take n arguments, one for each of the remaining arguments.</p><p>There are forms of the <code>do</code> function that accept multiple collections. The collections are iterated over in parallel, and iteration stops when it reaches the end of any one of them. The following example prints every item in a vector coupled with its index. </p><pre><code>val xs = Vector<String>()<br>add(xs, "Patrick")<br>add(xs, "Luca")<br>add(xs, "Emmy")<br><br>for (x in xs, i in 0 to false) do :<br> println("Element %_ is at index %_." % [x, i])</code></pre><p>It prints out </p><pre><code>Element Patrick is at index 0.<br>Element Luca is at index 1.<br>Element Emmy is at index 2.</code></pre><h3 id="anchor246">Operating Functions</h3><p><code>find</code>, <code>all?</code>, <code>any?</code>, <code>none?</code>, and <code>index-when</code> also have multiple collection versions that can be used with a for construct with multiple bindings.</p><p>Functions like <code>do</code>, with type signatures compatible with the for construct, are called <span style="font-style:italic;">operating functions</span>. Stanza's core library includes a large number of commonly used ones. For more details, read the reference documentation. </p><p>Occasionally, it might also be appropriate to implement your own operating function. Here is an operating function that first iterates over each odd integer in a vector and then iterates over each even integer in the vector.</p><pre><code>defn do-odd-then-even (f: Int -> ?, xs:Vector<Int>) :<br> for x in xs do :<br> if x % 2 != 0 : f(x)<br> for x in xs do :<br> if x % 2 == 0 : f(x)</code></pre><p>Here is an example of using it in conjunction with the for construct.</p><pre><code>val xs = Vector<Int>()<br>add(xs, 1)<br>add(xs, 3)<br>add(xs, 2)<br>add(xs, 6)<br>add(xs, 5)<br>add(xs, 2)<br>add(xs, 4)<br>add(xs, 3)<br><br>for x in xs do-odd-then-even :<br> println(x)</code></pre><p>Compiling and running the above prints out</p><pre><code>1<br>3<br>5<br>3<br>2<br>6<br>2<br>4</code></pre><h2 id="anchor59">Stanza Idioms</h2><p>With our new knowledge of anonymous functions, curried functions, and the for construct, we can now revisit our examples of using the core library and write them using standard Stanza idioms and functions.</p><pre><code>;A vector of strings<br>val strs = Vector<String>()<br>add-all(strs, ["patrick", "luca", "emmy", "Sunny", "whiskey", "Rummy"])<br>;Sort by the second letter<br>println("1.")<br>qsort!({_[1]}, strs)<br>println(strs)<br>;A vector of ints and strings<br>val int-strs = Vector<Int|String>()<br>add-all(int-strs, [1, 3, "A", "B", 4, -10, "Timon", "Pumbaa", 42])<br>;Sort using custom comparison function<br>println("\n2.")<br>qsort!{int-strs, _} $ fn (a, b) :<br> match(a, b) :<br> (a:Int, b:Int) : a < b<br> (a:Int, b:String) : a < length(b)<br> (a:String, b:Int) : length(a) < b<br> (a:String, b:String) : a < b<br>println(int-strs)<br>;Find first capitalized word<br>println("\n3.")<br>println $ for s in strs find :<br> upper-case?(s[0])<br>;Find index of first capitalized word<br>println("\n4.")<br>println $ for s in strs index-when :<br> upper-case?(s[0])<br>;Capitalize every word<br>println("\n5.")<br>for s in strs map! :<br> append(upper-case(s[0 to 1]), s[1 to false])<br>println(strs)<br>;A vector of integers<br>val ints = Vector<Int>()<br>add-all(ints, [4, 2, 3, -8, 5])<br>;Are they all positive?<br>println("\n6.")<br>println $ for x in ints all? :<br> x > 0<br>;Report lengths of string along with their index<br>println("\n7.")<br>for (s in strs, i in 0 to false) do :<br> println("strs[%_] = %_. Length = %_." % [i, strs[i], length(strs[i])])</code></pre><p>Compiling and running all of the above print outs</p><pre><code>1.<br>["patrick" "whiskey" "emmy" "Sunny" "Rummy" "luca"]<br><br>2.<br>[-10 1 "A" "B" 3 4 "Pumbaa" "Timon" 42]<br><br>3.<br>Sunny<br><br>4.<br>3<br><br>5.<br>["Patrick" "Whiskey" "Emmy" "Sunny" "Rummy" "Luca"]<br><br>6.<br>false<br><br>7.<br>strs[0] = Patrick. Length = 7.<br>strs[1] = Whiskey. Length = 7.<br>strs[2] = Emmy. Length = 4.<br>strs[3] = Sunny. Length = 5.<br>strs[4] = Rummy. Length = 5.<br>strs[5] = Luca. Length = 4.</code></pre><h2 id="anchor60">Tail Calls</h2><p>Consider the following function for computing the sum of all the positive integers less than or equal to <code>n</code>.</p><pre><code>defn sum-of (n:Int) :<br> if n > 0 : n + sum-of(n - 1)<br> else : 0</code></pre><p>Calling <code>sum-of(6)</code> returns <code>21</code>.</p><p>Here's a visualization of the <span style="font-style:italic;">execution context</span> as that operation is being performed.</p><pre><code>sum-of(6) =<br>6 + sum-of(5) =<br>6 + 5 + sum-of(4) =<br>6 + 5 + 4 + sum-of(3) =<br>6 + 5 + 4 + 3 + sum-of(2) =<br>6 + 5 + 4 + 3 + 2 + sum-of(1) =<br>6 + 5 + 4 + 3 + 2 + 1 + sum-of(0) =<br>6 + 5 + 4 + 3 + 2 + 1 + 0 =<br>6 + 5 + 4 + 3 + 2 + 1 = <br>6 + 5 + 4 + 3 + 3 = <br>6 + 5 + 4 + 6 = <br>6 + 5 + 10 = <br>6 + 15 = <br>21</code></pre><p>Observe that the computation of <code>sum-of(6)</code> requires knowing the result of <code>sum-of(5)</code>. And so we then recursively compute the result of <code>sum-of(5)</code> <span style="font-style:italic;">while remembering</span> that we should add <code>6</code> to the result to get the final answer. Similarly, the computation of <code>sum-of(5)</code> requires the result of <code>sum-of(4)</code>. Et cetera. </p><p>Each recursive invocation of <code>sum-of</code> requires us to remember what to do with the result. This is our execution context, and in Stanza, is saved in a stack of <span style="font-style:italic;">activation records</span>. How big does this stack get? Well, for <code>sum-of</code>, it grows to contain exactly <code>n</code> <span style="font-style:italic;">activation records</span>. </p><p>This can be verified by forcing a program failure when <code>n</code> is equal to <code>0</code> and looking at the <span style="font-style:italic;">stack trace</span>.</p><pre><code>defn sum-of (n:Int) :<br> if n > 0 : n + sum-of(n - 1)<br> else : fatal("n reached zero.")</code></pre><p>When compiled and ran, the above prints out</p><pre><code>FATAL ERROR: n reached zero.<br> at test.stanza:7.10<br> at test.stanza:6.18<br> at test.stanza:6.18<br> at test.stanza:6.18<br> at test.stanza:6.18<br> at test.stanza:6.18<br> at test.stanza:6.18<br> at test.stanza:9.0</code></pre><p>Each <code>test.stanza:6.18</code> entry in the stack trace refers to a recursive call to <code>sum-of(n - 1)</code>. Thus you can see that there are <code>6</code> entries corresponding to calling <code>sum-of(6)</code>. <span style="font-style:italic;">activation records</span> take up space. If <code>n</code> is too large, then eventually the stack of activation records will consume all of your program memory.</p><h3 id="anchor247">An Iterative Algorithm</h3><p>Now consider this alternative implementation of <code>sum-of</code>.</p><pre><code>defn sum-of (n:Int) :<br> x+sum-of(0, n)<br> <br>defn x+sum-of (x:Int, n:Int) :<br> if n > 0 : x+sum-of(x + n, n - 1)<br> else : x </code></pre><p>Here's a visualization of the execution context of computing <code>sum-of(6)</code>.</p><pre><code>sum-of(6) =<br>x+sum-of(0, 6) =<br>x+sum-of(6, 5) =<br>x+sum-of(11, 4) =<br>x+sum-of(15, 3) =<br>x+sum-of(18, 2) =<br>x+sum-of(20, 1) =<br>x+sum-of(21, 0) =<br>21</code></pre><p>Similar to before, the computation of <code>x+sum-of(0, 6)</code> requires knowing the result of <code>x+sum-of(6, 5)</code>. And so we then recursively compute the result of <code>x+sum-of(6, 5)</code>. But this time, we don't have to remember what to do with the result! The result of <code>x+sum-of(6, 5)</code> <span style="font-style:italic;">is</span> the result of <code>x+sum-of(0, 6)</code>, so just return whatever <code>x+sum-of(6, 5)</code> returns. </p><p>In concrete terms, what this means is that Stanza can discard the activation record for <code>x+sum-of(0, 6)</code> immediately before calling <code>x+sum-of(6, 5)</code> since there's no context to remember. If that is done, then the number of activation records does not grow, no matter how large <code>n</code> is. And thus the program will not run out of memory. This optimization is called <span style="font-style:italic;">tail call optimization</span>.</p><h3 id="anchor248">Tail Call Optimization</h3><p>By default, Stanza does not optimize tail calls in functions. This is done for the purposes of debugging. It is useful to have a complete stack trace, even if not strictly necessary for correct operation of the algorithm. To tell Stanza to optimize tail calls in a function, we have to explicitly declare the function as being tail call optimized.</p><pre><code>defn sum-of (n:Int) :<br> x+sum-of(0, n)<br> <br>defn* x+sum-of (x:Int, n:Int) :<br> if n > 0 : x+sum-of(x + n, n - 1)<br> else : x</code></pre><p><code>defn*</code> is the tail call optimized version of <code>defn</code>. Similarly, <code>defmethod*</code> is the tail call optimized version of <code>defmethod</code>, and <code>fn*</code> is the tail call optimized version of <code>fn</code>. </p><p>To verify that the stack frames are properly being discarded, we'll again force the program to fail when <code>n</code> is equal to <code>0</code> and examine the stack trace.</p><pre><code>defn* x+sum-of (x:Int, n:Int) :<br> if n > 0 : x+sum-of(x + n, n - 1)<br> else : fatal("n reached zero.")</code></pre><p>Compiling and running the program prints</p><pre><code>FATAL ERROR: n reached zero.<br> at tests/test.stanza:6.3<br> at tests/test.stanza:20.10</code></pre><p>There are now <span style="font-style:italic;">no</span> stack frames corresponding to <code>x+sum-of</code>. They have all been discarded.</p><h2 id="anchor61">Revisiting While</h2><p>With the introduction of tail calls, it is time for us to unveil the internals of the while loop construct. The expression</p><pre><code>var i = 0<br>while i < 10 :<br> println(i)<br> i = i + 1</code></pre><p>is equivalent to</p><pre><code>var i = 0<br>defn* loop () :<br> if i < 10 :<br> println(i)<br> i = i + 1<br> loop()<br>loop()</code></pre><p>Thus the while construct simply defines a local tail call optimized function and then calls it.</p><p>Directly expressing loops using recursive functions can often be much more natural than using a while loop. A while loop loops by default, and the programmer has to specify when it should <span style="font-style:italic;">stop</span> looping. In constrast, a recursive function does <span style="font-style:italic;">not</span> loop by default, and the programmer instead specifies when to perform another iteration.</p><p>Here is an example of using a tail call optimized function for finding the index of an integer <code>x</code> in a <span style="font-style:italic;">sorted</span> vector <code>xs</code> using binary search.</p><pre><code>defn bsearch (x:Int, xs:Vector<Int>) :<br> label<Int|False> return :<br> defn* loop (start:Int, end:Int) :<br> if start < end :<br> val mid = start + (end - start) / 2<br> if x < xs[mid] : loop(start, mid)<br> else if x > xs[mid] : loop(mid + 1, end)<br> else : return(mid)<br> loop(0, length(xs)) </code></pre><p><code>loop</code> finds the index of <code>x</code>, assuming that it exists between the <code>start</code> index and <code>end</code> index (exclusive). It does this by computing a midpoint, <code>mid</code>, between the two indices. If <code>x</code> is less than the element at <code>mid</code> then it looks again in the first half of the range. If <code>x</code> is greater than the element at <code>mid</code> then it looks again in the second half of the range. Otherwise it has found <code>x</code>, and it is at index <code>mid</code>.</p><p>Let's try looking for the numbers <code>1</code>, <code>14</code>, and <code>13</code>. </p><pre><code>defn main () :<br> val xs = Vector<Int>()<br> add-all(xs, [1,3,4,7,8,11,14,18,20,35])<br> println(bsearch(1, xs))<br> println(bsearch(14, xs))<br> println(bsearch(13, xs))<br><br>main()</code></pre><p>When compiled and ran, the above prints out</p><pre><code>0<br>6<br>false</code></pre>
</td>
<td class="rest">
<img url="resources/spacer.gif"></img>
</td>
</tr>
<tr><td colspan="3" class="footer">
Site design by Luca Li. Copyright 2015.
</td></tr>
</table>
</body>
</html>