Design Recipes for Pyret Functions
You can find the book, which uses a variant of Scheme rather than Pyret, for free at http://htdp.org/.
Have you ever looked at a blank file, starting a new program, with no idea where to begin? While there’s no silver bullet answer to the problem, the Design Recipe is a methodology for writing programs, described in the book How to Design Programs (HtDP), that tackles this problem for a number of programming patterns.
These patterns happen to match the style of programming that is used in a number of the pieces of implementations of programming languages themselves extremely well. As such, the first thing we’ll talk about in this course is programming in this style. And though the Design Recipe won’t directly inform the design of every program you write in the future, oftentimes it will provide just the right view on the problem.
1 Note
If you want to read about more language forms and examples, this tour has a longer introduction, though we won’t use everything that’s described there.
In order to familiarize yourself with Pyret, you should have already read this introduction to Pyret, which lays out some basics we’ll use here.
Some of the initial parts of this may seem boring. If they do, don’t worry, there is a reason for being so pedantic and things will ramp up. If they don’t, wonderful, you’re approaching this with a sufficiently open mind.
2 Recipe for Atomic Data
The basics of the design recipe involve an analysis of the types of values the program is working with, and how those values relate to the input and output of functions. The recipe works through the problem starting from the definition of the input and finishes with the implementation.
For our first example, we’ll take something simple enough that we could understand it in just about any context: calculating hourly wage with overtime.
To keep things simple, we’ll assume a constant hourly rate of $10/hour, so the only parameter is the number of hours worked. Then we proceed through several steps.
Understand the Data Definition
The incoming hours worked are Numbers, and there are two interesting kinds of numbers: those greater than 40 and those less than or equal to 40.
Function Header and Purpose
Next, to get started with the function, we write down the name of the function, the types of the arguments, and the type of value that will be returned. We also write a short English sentence, using the doc: keyword, describing the function:
fun hourstowages(hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime" end
This says that hourstowages will consume a Number and return another Number. The description informs the reader that the interpretations of the numbers for argument and return are hours and wages, respectively.
Write Examples of Calling the Function (Test Cases)
Next, we write a few test cases. This helps us think through what the implementation will look like, lets us know of any problematic cases that might come up, and gives us something to run to confirm that our implementation does what we expect when we’re done.
These examples of calls go in a where: block at the end of the function, and the simplest ones use is to check that the output is an expected value:
fun hourstowages(hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime, at $10/hr base" where: hourstowages(40) is 400 hourstowages(40.5) is 407.5 hourstowages(41) is 415 hourstowages(0) is 0 hourstowages(45) is 475 hourstowages(20) is 200 end
Examples should cover at least all the different cases mentioned in the data definition, and also to test common extremes and base cases. In this case, for example, it’s useful to note that the 40th hour doesn’t count towards overtime, but the 41st does.
Implement the Body
Now all that’s left is to fill a Pyret expression into the body of the function that computes the correct answer based on the inputs.
In the case of this running example, the data definition has a condition in it: whether or not the hours have exceeded 40. Conditional data usually implies a conditional expression in code. That means an if expression to test which case of the data definition the function is handling. Then, the bodies of the branches can be filled in with the appropriate answers.
fun hourstowages(hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime, at $10/hr base" if hours < 41: hours * 10 else if hours >= 41: (40 * 10) + ((hours  40) * (10 * 1.5)) end where: hourstowages(40) is 400 hourstowages(40.5) is 407.5 hourstowages(41) is 415 hourstowages(0) is 0 hourstowages(45) is 475 hourstowages(20) is 200 end
Run the Tests, and Fix Mistakes
Now we can click run, and get feedback on if there are any mistakes in the definition we wrote. If any tests fail, we have to figure out if we misunderstood the test, or misimplemented the program. It can require many rounds of backandforth before settling on a good set of tests and an agreeing implementation that does precisely what we intend.
In this case, there’s a mismatch between the implementation and the tests: the first test fails. When this happens, we have to ask: did we get the test wrong or the implementation? In this case, it happens to be the implementation; the first condition shouldn’t include the case where hours is between 40 and 41, which should be handled by the second case.
Since we got something wrong around a boundary condition, it’s probably a good idea to add one more test to make sure we didn’t screw up in the other direction. This is the correct implementation, with a new test to doublecheck things:
fun hourstowages(hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime, at $10/hr base" if hours <= 40: # this line changed hours * 10 else if hours > 40: # this line changed (40 * 10) + ((hours  40) * (10 * 1.5)) end where: hourstowages(40) is 400 hourstowages(39.5) is 395 # this test was added hourstowages(40.5) is 407.5 # this test is correct now hourstowages(41) is 415 hourstowages(0) is 0 hourstowages(45) is 475 hourstowages(20) is 200 end
2.1 Abstracting Common Parts
The hourstowages function always assumes an hourly rate of $10/hour. We can change it to accommodate a different hourly rate, say $20/hour, by changing the constant 10 where it appears representing the hourly rate:
fun hourstowages20(hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime, at $20/hr base" if hours <= 40: hours * 20 else if hours > 40: (40 * 20) + ((hours  40) * (20 * 1.5)) end end
We could make another copy of the function for $30/hour workers, and so on. However, it’s also possible, and quite straightforward, to change the function to work for any hourly wage. We note the shared parts across the implementation and lift them out, adding a new parameter to the function.
fun hourstowagesany(rate :: Number, hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime, at the given rate" if hours <= 40: hours * rate else if hours > 40: (40 * rate) + ((hours  40) * (rate * 1.5)) end end
Note that we’ll take the convention of adding new parameters at the beginning of the argument list. We simply add the new parameter (with an appropriate annotation), and replace all instances of the constant with it.
2.2 Exercises
Write a function called hasovertime that takes a number of hours and returns true if the number of hours is greater than 40 and false otherwise.
Working negative hours is nonsense. Write a version of hourstowages that uses the raise function to throw an error if fewer than 0 hours are reported. Use the raises form to test for it (read about raises in the Pyret documentation).
Write a function called hourstowagesot that takes a number of hours, an hourly rate, and an overtime threshold, and produces the total pay. Any hours worked beyond the overtime threshold should be credited at 1.5 times the normal rate of pay, as before.
3 Evaluating by Reducing Expressions
There’s an imporant note about Pyret going on in this example: There are no return statements in Pyret. The function body (the if expression here) evaluates when called, and the result of the body’s evaluation is the result of the function call.
We can show this evaluation visually, with an example of a call:
hourstowages(45) => if 45 <= 40: hours * 10 else if 45 > 40: (40 * 10) + ((45  40) * 15) end
=> if false: hours * 10 else if 45 > 40: (40 * 10) + ((45  40) * 15) end
=> if false: hours * 10 else if true: (40 * 10) + ((45  40) * 15) end
=> (40 * 10) + ((45  40) * 15)
=> 400 + (5 * 15) => 475
This style of reduction is the best way to think about the evaluation of Pyret function calls and expressions. The whole body of the function takes steps that simplify it, much like simplifying expressions in algebra. We’ll use this reductionstyle example later in the notes, and you can use it yourself if you want to try and work through the evaluation of a Pyret function by hand (or in your head).
When you look at at a test case in Pyret, like
hourstowages(45) is 475
the same idea of algebraic simplification applies. This will reduce to
475 is 475
which is clearly true, and is causes it to be registered as a passing test. When a check or where block runs, it evaluates each is test and compares it to the answer in this same way.
4 Recipe for Simple Data
This definition of primitive versus compound data has a little bit of a fuzzy border: we could think of strings as lists of characters, for instance. Usually the kind of program we’re writing makes it clear what data we are treating as atomic and what data we are breaking down further.
Lots of interesting programs work over far more than primitive data like Numbers and Strings. They combine pieces of primitive data into richer datatypes, and the recipe has a natural extension to dealing with those cases.
Our example will be calculating the distance from the origin of a 2dimensional point, and we’ll adapt the initial recipe as needed for it.
Understand the Data Definition and Write Examples
A 2D point has an x and y coordinate, which are both numbers. We’ll use a Pyret data definition to represent points that has both of these fields:
data Point:  point(x :: Number, y :: Number) end
When working with more complicated data, it’s useful to write down examples of the data itself along with the definition. These examples can be useful for thinking through what kinds of values can be represented by the data definition, and also serve as useful inputs to tests later. Some examples of points are:
point(0, 0) point(3, 4) point(3, 4)
Write Down the Function Header, Contract, and Purpose
This step is basically unchanged from atomic data, just adapted for the new definition. We’re calculating the distance from the origin to a given point, so the function will consume a point as input and produce a Number as output. There aren’t any extra arguments:
fun distancetoorigin(p :: Point) > Number: doc: "Produces the distance from the origin to the given point." end
Write Example Calls to the Function
Next, we write a few test cases. This helps us think through what the implementation will look like, lets us know of any problematic cases that might come up, and gives us something to run to confirm that our implementation does what we expect when we’re done. Our examples of the data definition from earlier can come in handy here as test inputs.
fun distancetoorigin(p :: Point) > Number: doc: "Produces the distance from the origin to the given point." where: distancetoorigin(point(0, 0)) is 0 distancetoorigin(point(3, 4)) is 5 distancetoorigin(point(3, 4)) is 5 end
Write Down a Template for the Data Definition
This is a new step beyond what’s needed for atomic data. When values get more structure, it’s useful to have a structure to program them with. Functions that work over Points will need access to the x and y fields. For breaking apart instances of data defined by data, Pyret provides an expression called cases. Here’s what a cases expression looks like over one of our example Points:
cases(Point) point(0, 1):  point(x, y) => x + y end => 0 + 1
You may be wondering why this is called cases when there’s only one case here. A more general version will be shown soon. The cases expression matches the constructor of the given value (in this case, point(0, 1)) with the case (a case is everything after a ) that has the same constructor name. Then, the fields of the value are substituted for the names in the case pattern (in this case, x and y), and the whole cases expression reduces to the body of that case.
The annotation in parentheses, (Point), checks that the value you provide is correct, and dictates which cases make sense to use—
only those from the data definition. Whenever we work with Points (or other compound data), a cases expression is a good way to get at the data inside it in a principled way. Most functions over Points will have this structure:
# fun pointfunction(p :: Point) > ???: cases(Point) p:  point(x, y) => ... x ... ... y ... end end #
That is, we don’t know what it will produce, but the function will consume a point, use cases to inspect the point value, and then do something with the x and y fields. The precise operation isn’t clear until we look at the particular function we’re trying to implement, but one or both of those values will almost certainly be involved.
So, the next step is to copy the template into the definition we’re building:
fun distancetoorigin(p :: Point) > Number: doc: "Produces the distance from the origin to the given point." cases(Point) p:  point(x, y) => ... x ... ... y ... end where: distancetoorigin(point(0, 0)) is 0 distancetoorigin(point(3, 4)) is 5 distancetoorigin(point(3, 4)) is 5 end
Now to fill in the function body, we just need to figure out what the ... parts should be.
Fill in the Function Body
With a solid understanding of the function, we can now fill in the body with an implementation that gives the answers our tests expect. Here, we just use the standard definition of distance, computed by Pyret’s numsqrt function and the * and + operators.
fun distancetoorigin(p :: Point) > Number: doc: "Produces the distance from the origin to the given point." cases(Point) p:  point(x, y) => numsqrt((x * x) + (y * y)) end where: distancetoorigin(point(0, 0)) is 0 distancetoorigin(point(3, 4)) is 5 distancetoorigin(point(3, 4)) is 5 end
Run the Tests and Fix Mistakes
As before, we run the tests to figure out any mistakes we may have made, both in our understanding of the examples and in the implementation itself.
4.1 Functions Over Mixed, Related Data
Data definitions can define more than one kind of constructor: Point just has one (point). We could extend the definition to handle polar points:
data Point:  point(x :: Number, y :: Number)  polar(theta :: Number, magnitude :: Number) end
Now, the use of cases is a little more obvious, in distinguishing between these multiple constructors, which we often refer to as variants:
cases(Point) polar(0, 5):  point(x, y) => x  polar(theta, magnitude) => magnitude end => 5
cases(Point) point(1, 2):  point(x, y) => x  polar(theta, magnitude) => magnitude end => 1
4.2 More Refined Comparisons
Sometimes, a direct comparison via is isn’t enough for testing. We saw raises in the last section for testing errors. However, when doing some computations, especially involving math with approximations, we want to ask a different question. For example, consider these tests for distancetoorigin:
check: distancetoorigin(point(1, 1)) is ??? end
What can we check here? Typing this into the REPL, we can find that the answer prints as 1.4142135623730951. That’s an approximation of the real answer, which Pyret cannot represent exactly. But it’s hard to know that this precise answer, to this decimal place, and no more, is the one we should expect up front, and thinking through the answers is supposed to be the first thing we do!
Since we know we’re getting an approximation, we can really only check that the answer is roughly correct, not exactly correct. If we can check that the answer to distancetoorigin(point(1, 1)) is around, say, 1.41, and can do the same for some similar cases, that’s probably good enough for many applications, and for our purposes here. If we were calculating orbital dynamics, we might demand higher precision, but note that we’d still need to pick a cutoff! Testing for inexact results is a necessary task.
Let’s first define what we mean by "around" with one of the most precise ways we can, a function:
fun around(actual :: Number, expected :: Number) > Boolean: doc: "Return whether actual is within 0.01 of expected" numabs(actual  expected) < 0.01 where: around(5, 5.01) is true around(5.01, 5) is true around(5.02, 5) is false around(numsqrt(2), 1.41) is true end
The is form now helps us out. There is special syntax for supplying a userdefined function to use to compare the two values, instead of just checking if they are equal:
check: 5 is%(around) 5.01 numsqrt(2) is%(around) 1.41 distancetoorigin(point(1, 1)) is%(around) 1.41 end
Adding %(something) after is changes the behavior of is. Normally, it would compare the left and right values for equality. If something is provided with %, however, it instead passes the left and right values to the provided function (in this example around). If the provided function produces true, the test passes, if it produces false, the test fails. This gives us the control we need to test functions with predictable approximate results.
4.3 Exercises
Extend the definition of distancetoorigin to include polar points.
This might save you a Google search: polar conversions. Use the design recipe to write xcomponent and ycomponent, which return the x and y Cartesian parts of the point (which you would need, for example, if you were plotting them on a graph). Read about numsin and other functions you’ll need at the Pyret number documentation.
Write a data definition called Pay for pay types that includes both hourly employees, whose pay type includes an hourly rate, and salaried employees, whose pay type includes a total salary for the year. Use the design recipe to write a function called expectedweeklywages that takes a Pay, and returns the expected weekly salary: the expected weekly salary for an hourly employee assumes they work 40 hours, and the expected weekly salary for a salaried employee is 1/52 of their salary.
5 Recipe for Recursive Data
Sometimes, a data definition has a piece that refers back to itself. For example, a linked list of numbers:
data NumList:  nlempty  nllink(first :: Number, rest :: NumList) end
Moving on to defining examples, we can talk about empty lists:
nlempty
We can represent short lists, like a sequence of two 4’s:
nllink(4, nllink(4, nlempty))
Since these are created with constructors from data, we can use cases with them:
cases(NumList) nlempty:  nlempty => "empty!"  nllink(first, rest) => "not empty" end => "empty!"
cases(NumList) nllink(1, nllink(2, nlempty)):  nlempty => "empty!"  nllink(first, rest) => first end => 2
This describes a qualitatively different kind of data than something like a Point, which is only made up of other kinds of simple data. In fact, in contrast to something like a Point, the size of NumLists is unbounded or arbitrarilysized. Given a NumList, there is an easy way to make a new, larger one: just use nllink. So, we need to consider larger lists:
nllink(1, nllink(2, nllink(3, nllink(4, nllink(5, nllink(6, nllink(7, nllink(8, nlempty))))
Let’s try to write a function contains3, which returns true if the NumList contains the value 3, and false otherwise.
First, our header:
fun contains3(nl :: NumList) > Boolean: doc: "Produces true if the list contains 3, false otherwise" end
Next, some tests:
fun contains3(nl :: NumList) > Boolean: doc: "Produces true if the list contains 3, false otherwise" where: contains3(nlempty) is false contains3(nllink(3, nlempty)) is true contains3(nllink(1, nllink(3, nlempty))) is true contains3(nllink(1, nllink(2, nllink(3, nllink(4, nlempty))))) is true contains3(nllink(1, nllink(2, nllink(5, nllink(4, nlempty))))) is false end
Next, we need to fill in the body with the template for a function over NumLists. We can start with the analogous template using cases we had before:
fun contains3(nl :: NumList) > Boolean: doc: "Produces true if the list contains 3, false otherwise" cases(NumList) nl:  nlempty => ...  nllink(first, rest) => ... first ... ... rest ... end end
An empty list doesn’t contain the number 3, surely, so the answer must be false in the nlempty case. In the nllink case, if the first element is 3, we’ve successfully answered the question. That only leaves the case where the argument is an nllink and the first element does not equal 3:
fun contains3(nl :: NumList) > Boolean: cases(NumList) nl:  nlempty => false  nllink(first, rest) => if first == 3: true else: # handle rest here end end end
Since we know rest is a NumList (based on the data definition), we can use a cases expression to work with it. This is sort of like filling in a part of the template again:
fun contains3(nl :: NumList) > Boolean: cases(NumList) nl:  nlempty => false  nllink(first, rest) => if first == 3: true else: cases(NumList) rest:  nlempty => ...  nllink(firstofrest, restofrest) => ... firstofrest ... ... restofrest ... end end end end
If the rest was empty, then we haven’t found 3 (just like when we checked the original argument, nl). If the rest was a nllink, then we need to check if the first thing in the rest of the list is 3 or not:
fun contains3(nl :: NumList) > Boolean: cases(NumList) nl:  nlempty => false  nllink(first, rest) => if first == 3: true else: cases(NumList) rest:  nlempty => false  nllink(firstofrest, restofrest) => if firstofrest == 3: true else: # fill in here ... end end end end end
Since restofrest is a NumList, we can fill in a cases for it again:
fun contains3(nl :: NumList) > Boolean: cases(NumList) nl:  nlempty => false  nllink(first, rest) => if first == 3: true else: cases(NumList) rest:  nlempty => false  nllink(firstofrest, restofrest) => if firstofrest == 3: true else: cases(NumList) restofrest:  nlempty => ...  nllink(firstofrestofrest, restofrestofrest) => ... firstofrestofrest ... ... restofrestofrest ... end end end end end end
See where this is going? Not anywhere good. We can copy this cases expression as many times as we want, but we can never answer the question for a list that is just one element longer than the number of times we copy the code.
So what to do? We tried this approach of using another copy of cases based on the observation that rest is a NumList, and cases provides a meaningful way to break apart a NumList; in fact, it’s what the recipe seems to lead to naturally.
Let’s go back to the step where the problem began, after filling in the template with the first check for 3:
fun contains3(nl :: NumList) > Boolean: cases(NumList) nl:  nlempty => false  nllink(first, rest) => if first == 3: true else: # what to do with rest? end end end
We need a way to compute whether or not the value 3 is contained in rest. Looking back at the data definition, we see that rest is a perfectly valid NumList, simply by the definition of nllink. And we have a function (or, most of one) whose job is to figure out if a NumList contains 3 or not: contains3. That ought to be something we can call with rest as an argument, and get back the value we want:
fun contains3(nl :: NumList) > Boolean: cases(NumList) nl:  nlempty => false  nllink(first, rest) => if first == 3: true else: contains3(rest) end end end
And lo and behold, all of the tests defined above pass. It’s useful to step through what’s happening when this function is called. Let’s look at an example:
contains3(nllink(1, nllink(3, nlempty)))
First, we substitute the argument value in place of nl everywhere it appears; that’s just the usual rule for function calls.
=> cases(NumList) nllink(1, nllink(3, nlempty)):  nlempty => false  nllink(first, rest) => if first == 3: true else: contains3(rest) end end
Next, we find the case that matches the constructor nllink, and substitute the corresponding pieces of the nllink value for the first and rest identifiers.
=> if 1 == 3: true else: contains3(nllink(3, nlempty)) end
=> if false: true else: contains3(nllink(3, nlempty)) end => contains3(nllink(3, nlempty))
=> cases(NumList) nllink(3, nlempty):  nlempty => false  nllink(first, rest) => if first == 3: true else: contains3(rest) end end
Again, we substitute into the nllink branch.
=> if 3 == 3: true else: contains3(nlempty) end
This time, since 3 is 3, we take the first branch of the if expression, and the whole original call evaluates to true.
=> if true: true else: contains3(nlempty) end => true
An interesting feature of this trace through the evaluation is that we reached the expression contains3(nllink(3, nlempty)), which is a normal call to contains3; it could even be a test case on its own. The implementation works by doing something (checking for equality with 3) with the nonrecursive parts of the datum, and combining that result with the result of the same operation (contains3) on the recursive part of the datum. This idea of doing recursion with the same function on selfrecursive parts of the datatype lets us extend our template to handle recursive positions.
The simple design recipe dictated this as the template:
# fun numlistfun(nl :: NumList) > ???: cases(NumList) nl:  nlempty => ...  nllink(first, rest) => ... first ... ... rest ... end end #
However, this template doesn’t give much guidance with what to do with the rest field. We will extend the template with the following rule: each selfrecursive position in the data definition becomes a selfrecursive function call in the template. So the new template looks like:
# fun numlistfun(nl :: NumList) > ???: cases(NumList) nl:  nlempty => ...  nllink(first, rest) => ... first ... ... numlistfun(rest) ... end end #
To handle recursive data, the design recipe just needs to be modified to have this extended template. When you see a recursive data definition (of which there will be many in this course), you should naturally start thinking about what the recursive calls will return and how to combine their results with the other, nonrecursive pieces of the datatype.
5.1 Exercises
Use the design recipe to write a function containsn that takes a NumList and a Number, and returns whether that number is in the NumList.
Use the design recipe to write a function sum that takes a NumList, and returns the sum of all the numbers in it. The sum of the empty list is 0.
Use the design recipe to write a function remove3 that takes a NumList, and returns a new NumList with any 3’s removed. The remaining elements should all be in the list in the same order they were in the input.
Write a data definition called NumListList that represents a list of NumLists, and use the design recipe to write a function sumoflists that takes a NumListList and produces a NumList containing the sums of the sublists.
6 Parameterizing Data Definitions
If we wanted to define a list of Strings in the same style we defined a list of numbers, we might write:
data StringList:  slempty  sllink(first :: String, rest :: StringList) end
Similarly, the exercises from Recipe for Recursive Data had you define a representation of lists of NumLists. It would be straightfoward, if tedious, to do the same for lists of Booleans, lists of Pay objects, and so on.
Each of these forms has the same structure:
data ??List:  xxempty  xxlink(first :: ??, rest :: ??List) end
Where the ?? and xx are filled in with applicationspecific names like Num and nl, or String and sl. It would be useful to not require a new definition for each kind of data; repeating ourselves is generally good to avoid in programming.
Pyret has special syntax for this kind of data definition:
data AList<a>:  aempty  alink(first :: a, rest :: AList<a>) end
We say that the header, data AnyList<a> creates a data definition that is parametric or polymorphic over a. At the time of defining AList, we have not yet decided what kind of elements it will hold, and defer that decision until we create a particular AList whose contents we know. At that point, we can instantiate different kinds of lists by using <> to fill in an appropriate annotation for the contents of a particular AList:
ls :: AList<String> = alink("a", alink("b", alink("c", aempty))) lls :: AList<AList<String>> = alink(alink("a", aempty), alink(alink("b", alink("c", aempty)), aempty)) ln :: AList<Number> = alink(1, alink(2, aempty)) lp :: AList<Point> = alink(point(1, 2), alink(polar(3, 45), aempty))
We can call types like AList<Number> instantiations of the polymorphic AList type. We can rewrite the NumList functions we defined before in terms of ALists, like contains3:
fun contains3(nl :: AList<Number>) > Boolean: doc: "Returns true if 3 is in the list, false otherwise" cases(AList<Number>) nl:  aempty => false  alink(first, rest) => if first == 3: true else: contains3(rest) end end where: contains3(aempty) is false contains3(alink(3, aempty)) is true contains3(alink(1, alink(3, aempty))) is true contains3(alink(1, alink(2, alink(3, alink(4, aempty))))) is true contains3(alink(1, alink(2, alink(5, alink(4, aempty))))) is false end
The only difference is the use of AList<Number> instead of NumList in the header and the cases expression (and the renaming of nl to a).
Let’s consider another example; calculating the length of a list of numbers. We start with the header as always:
fun length(nl :: AList<Number>) > Number: doc: "Returns the number of elements in the list.". end
Next we add examples:
fun length(nl :: AList<Number>) > Number: doc: "Returns the number of elements in the list.". where: length(aempty) is 0 length(alink(8, aempty)) is 1 length(alink(22, alink(43, aempty))) is 1 end
Next, we add the template:
fun length(nl :: AList<Number>) > Number: doc: "Returns the number of elements in the list." cases(AList<Number>) nl:  aempty => ...  alink(first, rest) => ... first ... ... length(rest) ... end where: length(aempty) is 0 length(alink(8, aempty)) is 1 length(alink(22, alink(43, aempty))) is 2 end
The length of an empty list is 0, and the length of a link is one larger than the length of the rest of the list:
fun length(nl :: AList<Number>) > Number: doc: "Returns the number of elements in the list." cases(AList<Number>) nl:  aempty => 0  alink(first, rest) => 1 + length(rest) end where: length(aempty) is 0 length(alink(8, aempty)) is 1 length(alink(22, alink(43, aempty))) is 2 end
This should be a pretty easy exercise to understand by now. What would happen if we wanted to write the same definition for AList<String>? It would look like this:
fun length(sl :: AList<String>) > Number: doc: "Returns the number of elements in the list.". cases(AList<String>) sl:  aempty => 0  alink(first, rest) => 1 + length(rest) end end
What about a AList<AList<Point>>?
fun length(pll :: AList<AList<Point>>) > Number: doc: "Returns the number of elements in the list.". cases(AList<AList<Point>>) pll:  aempty => 0  alink(first, rest) => 1 + length(rest) end end
Aside from the annotations and the name of the argument, these functions are exactly the same! Mirroring the way we unified the various ??List data definitions, we can lift out the common part of the type:
fun length<a>(al :: AList<a>) > Number: doc: "Returns the number of elements in the list." cases(AList<a>) al:  aempty => 0  alink(first, rest) => 1 + length(rest) end end
This works (and makes sense) for all the different kinds of examples:
check: length(aempty) is 0 length(alink(8, aempty)) is 1 length(alink(22, alink(43, aempty))) is 2 length(aempty) is 0 length(alink("a", aempty)) is 1 length(alink("a", alink(43, aempty))) is 2 length(aempty) is 0 length(alink(alink(point(1, 2), aempty), aempty)) is 1 end
We’ll talk more about how to actually typecheck parametric types later in the semester. We call length a parametric or polymorphic function, just as we called AList a parametric data definition. It means that the function can work over all possible instantiations of AList. We’ll talk about more instances of interesting functions like this in Abstracting Common Parts of List Functions.
6.1 List and the list Abbreviation
Lists in this style are so useful that they are built into Pyret. The definition in Pyret’s library is:
data List<a>:  empty  link(first :: a, rest :: List<a>) end
The names List, link, and empty are all available anywhere in Pyret (to avoid confusion, Pyret will also stop any other programs from redefining them).
Since lists are constructed often, and writing nested link and empty calls is tedious, Pyret supports a special syntax for constructing lists more concisely:
check: [list: 1, 2] is link(1, link(2, empty)) [list:] is empty [list: [list:], [list: 1]] is link(empty, link(link(1, empty), empty)) end
We’ll switch to using this syntax for lists for the rest of the notes and examles, and to using the builtin List with problemappropriate instantiations.
7 Abstracting Common Parts of List Functions
In Abstracting Common Parts, we saw how to pull out common parts of functions over atomic data. What happens if we apply the same rules to functions over lists?
Let’s consider two functions over List<Number>s, sqrnums and absnums:
fun sqrnums(nl :: List<Number>) > List<Number>: doc: "Return a list with the squares of the given numbers" cases(List<Number>) nl:  empty => empty  link(first, rest) => link(numsqr(first), sqrnums(rest)) end end fun absnums(nl :: List<Number>) > List<Number>: doc: "Return a list with the absolute values of the given numbers" cases(List<Number>) nl:  empty => empty  link(first, rest) => link(numabs(first), absnums(rest)) end end
We can identify the common parts: the numabs function and numsqr functions appear in the same spot. By following the rules of extraction, we add a new parameter name at the beginning, replace the common part with that identifier in the function body, and put that argument in the beginning of the argument lists for each call.
fun dotonums(operation :: ???, nl :: List<Number>) > List<Number>: doc: "Return a new list made of the elements of nl with operation done to them" cases(List<Number>) nl:  empty => empty  link(first, rest) => # replaced numabs/numsqr with operation in the line below, and added it # in the recursive call to dotonums, according to the rules of # extracting common parts link(operation(first), dotonums(operation, rest)) end end
What about the annotation for operation? What goes there?
To describe operation, we’re going to introduce a new kind of annotation, an function or arrow annotation. Its syntax is
(Ann1, Ann2, ..., AnnN > AnnR)
where Ann1 through AnnN are annotations representing arguments to a function, and AnnR is an annotation representing the return type of a function. So we can write the annotation for numsqr and numabs as:
(Number > Number)
That is, they are both functions that consume and produce Numbers. We can use one to describe the operation argument of dotonums:
fun dotonums(operation :: (Number > Number), nl :: List<Number>) > List<Number>: doc: "Return a list containing operation applied to each element of nl" cases(List<Number>) nl:  empty => empty  link(first, rest) => link(operation(first), dotonums(operation, rest)) end where: dotonums(numsqr, [list:]) is [list:] dotonums(numsqr, [list: 1, 2]) is [list: 1, 4] dotonums(numabs, [list:]) is [list:] dotonums(numabs, [list: 1, 1]) is [list: 1, 1] end
In the examples for dotonums, we see that, following the rules from extracting common parts, we provide numabs and numsqr as arguments. We can run the program and its examples and see that it works.
In Pyret (and many other languages), all functions are values, just like 5 or point(1, 2) are values. This goes for userdefined functions, too, so we can use dotonums with, say, an hourstowages function:
fun hourstowages(hours :: Number) > Number: if hours <= 40: hours * 10 else if hours > 40: (40 * 10) + ((hours  40) * (10 * 1.5)) end end check: dotonums(hourstowages, [list: 40, 39, 41]) is [list: 400, 390, 415] end
It’s useful to see how this impacts the evaluation of dotonums for a small example:
dotonums(hourstowages, link(41, link(39, empty)))
We aren’t calling hourstowages yet, so no substitution happens. The function value (which we’ll represent with its name) is simply passed in as a value to the body of dotonums.
=> cases(List<Number>) link(41, link(39, empty)):  empty => empty  link(first, rest) => link(hourstowages(first), dotonums(hourstowages, rest)) end
=> link(hourstowages(41), dotonums(hourstowages, link(39, empty)))
=> link( if 41 <= 40: 41 * 10 else if 41 > 40: (40 * 10) + ((41  40) * (10 * 1.5)) end, dotonums(hourstowages, link(39, empty)))
=> link( 415, dotonums(hourstowages, link(39, empty)))
Now another call to dotonums. Note that we are still processing the argument list of the call to link. We’re done processing the first element, but we’re processing the rest in a place where it will become the rest field of the new list that’s being created.
=> link( 415, cases(List<Number>) link(39, empty):  empty => empty  link(first, rest) => link(hourstowages(first), dotonums(hourstowages, rest)) end)
=> link( 415, link( hourstowages(39), dotonums(hourstowages, empty)))
=> link( 415, link( if 39 <= 40: 39 * 10 else if 39 > 40: (40 * 10) + ((39  40) * (10 * 1.5)) end, dotonums(hourstowages, empty)))
=> link( 415, link( 39, dotonums(hourstowages, empty)))
=> link( 415, link( 390, cases(List<Number>) empty:  empty => empty  link(first, rest) => link(hourstowages(first), dotonums(hourstowages, rest)) end))
=> link( 415, link( 390, empty))
When we pass functions as values, we will continue to represent them with just their name in evaluation sequences. The don’t cause their body to be evaluated when they appear as values or are passed as arguments. This only happens when the function is called by writing it with a parenthesized list of arguments after it. Other than keeping those new rules in mind, the rules for evaluating programs that use functions as values is the same as all the programs we’ve seen so far.
Functions as values are also called firstclass functions, and when they are passed as arguments, they can be referred to as higherorder functions. Lots of languages have firstclass functions, from Python and JavaScript to Ocaml and Haskell, and they have a ton of uses, many of which we’ll study in this course.
The dotonums function is a pretty nice abstraction: we can now apply a function to all the elements of a list of numbers, and get back a new list with the outputs.
But we can do one better. Let’s look at what dotostrings, a version of dotonums for Strings, would look like:
fun dotostrings(operation :: (String > String), sl :: List<String>) > List<String>: doc: "Return a list containing operation applied to each element of ns" cases(List<String>) sl:  empty => empty  link(first, rest) => link(operation(first), dotostrings(operation, rest)) end end
Like when we saw similar versions of length for different types, dotostrings and dotonums only differ in the declared types: String in place of Number everywhere. This suggests that we can use a parametric type again:
fun dotoa<a>(operation :: (a > a), al :: List<a>) > List<a>:
If we fill in the definition of dotoa, we could redefine:
fun dotonums(operation :: (Number > Number), nl :: List<Number>) > List<Number>: dotoa(operation, nl) end fun dotostrs(operation :: (String > String), sl :: List<String>) > List<String>: dotoa(operation, sl) end
But before we declare ourselves done, there’s one last part of this definition worth generalizing. Do you see it? What if we wanted to write numstostrings, which takes a list of Numbers and produces a list of Strings:
fun numstostrings(nums :: List<Number>) > List<String>: ... end
Can we use dotoa to do it? The definition would look like:
fun numstostrings(nl :: List<Number>) > List<String>: dotoa(numtostring, nl) end
We could actually run this version of numstostrings without error: Pyret doesn’t currently check that we don’t misuse parametric types. That doesn’t change the fact that we would be violating the stated contract of dotoa, though.
But, this violates the contract of dotoa, because dotoa must return a list of the same type it consumes. In this example, it would produce a list of a different type. So there’s one final change to make to dotoa to make it handle this last case:
fun turnasintobs<a, b>(atob :: (a > b), al :: List<a>) > List<b>: doc: "Return a the b's returned from atob on each a in the input" cases(List<a>) al:  empty => empty  link(first, rest) => link(atob(first), turnasintobs(atob, rest)) end end
This new function, turnasintobs, is parameterized over two types, the type of the elements of the input list (a), and the type of the elements of the output list (b). With this final tweak, all of these examples now make sense with the same function:
check: turnasintobs(numsqr, [list:]) is [list:] turnasintobs(numsqr, [list: 1, 2]) is [list: 1, 4] turnasintobs(numabs, [list:]) is [list:] turnasintobs(numabs, [list: 1, 1]) is [list: 1, 1] turnasintobs(stringtoupper, [list: "a", "b", "c"]) is [list: "A", "B", "C"] turnasintobs(stringtolower, [list: "A", "B", "C"]) is [list: "a", "b", "c"] turnasintobs(numtostring, [list: 1, 2]) is [list: "1", "2"] end
The function turnasintobs is typically called map, and is a major building block in programming with functions, just like the for loop is a major building block in C++ and Java. It’s important enough that map is a default library function in many programming languages with higherorder functions.
8 Functions that Return Functions
We saw in Abstracting Common Parts of List Functions that the turnasintobs function, more commonly known as map, covered a number of use cases for transforming lists. Recall that we can use it, for instance, to calculate the hourly wage for a list of numbers representing hours:
# This function is just as before fun hourstowages(hours :: Number) > Number: doc: "Compute total wage from hours, accounting for overtime, at $10/hr base" if hours < 41: hours * 10 else if hours >= 41: (40 * 10) + ((hours  40) * (10 * 1.5)) end end # Now we could use check: map(hourstowages, [list: 30, 40]) is [list: 300, 400] end
It’s easy to define versions of this that for hourly rates of 20, or 30, and use those with map. But we already saw that in Abstracting Common Parts, it’s a good idea to not write many copies of essentially the same function, when we can abstract out the common parts.
But, if we have a modified version of hourstowages that takes the hourly rate as an argument:
fun hourstowagesrated(hours :: Number, rate :: Number) > Number:
How do we use this with map? Let’s say we have two lists of hours:
atrate10 = [list: 35, 40, 30] atrate20 = [list: 25, 45, 40]
How can we use map to calculate the first list’s wages at a rate of $10/hr, and the second list’s wages at $20/hr? If we just try calling it directly:
check: map(hourstowagesrated, atrate10) is [list: 350, 400, 300] map(hourstowagesrated, atrate20) is [list: 500, 950, 800] end
We get an arity mismatch error from inside the map function. Why? Recall that what the map function does is apply the function given to it as its first argument to each list element. So it tries to apply, in the first example:
hourstowagesrated(35)
This is clearly an error, since hourstowagesrated’s contract requires two arguments, and only one is provided here. What would solve the problem is a function that takes an hourly rate, and returns a function like hourstowages that only takes one argument, but keeps track of the given hourly rate.
Let’s first think about what the header to such a function would look like:
fun makeratedhourstowages(rate :: Number) > (Number > Number):
That’s the typebased description of what we just said: makeratedhourstowages takes a Number and returns a function that takes a Number and produces one. We can write some examples of what it would look like to use such a function:
fun makeratedhourstowages(rate :: Number) > (Number > Number): doc: "Create a function that computes wages at the given rate" where: makeratedhourstowages(10)(40) is 400 makeratedhourstowages(10)(35) is 350 makeratedhourstowages(20)(35) is 700 end
Note how the tests look different from anything we’ve seen: There is a function invocation followed by another, because makeratedhourstowages returns a function, which we immediately call. Note also that this matches the return type in the contract, which specifies that the function should return a (Number > Number) function. As further examples, the returned functions ought to be of the right shape to use with map:
check: map(makeratedhourstowages(10), atrate10) is [list: 350, 400, 300] map(makeratedhourstowages(20), atrate20) is [list: 500, 950, 800] end
lam is short for lambda, which is a traditional name for anonymous functions that comes from the λcalculus. So how to fill in the body of makeratedhourstowages? There are a few ways, here we’re going to add to our inventory of Pyret concepts. In Pyret, we can use the lam keyword to create a function value directly, anywhere an expression is allowed. A use of lam looks like a use of fun but without the name. The resulting value is just like a function created with fun; they can be called, passed to map, bound to identifiers, and so on:
check: f = lam(x :: Number) > Number: x + 1 end f(1) is 2 f(2) is 3 map(lam(x): x + 1 end, [list: 1, 2, 3]) is [list: 2, 3, 4] map(f, [list: 1, 2, 3]) is [list: 2, 3, 4] end
So, we can make the body of makeratedhourstowages be a single lam expression, that takes in a number of hours and does the call to hourstowagesrated with both arguments.
fun makeratedhourstowages(rate :: Number) > (Number > Number): doc: "Create a function that computes wages at the given rate" lam(hours :: Number) > Number: hourstowagesrated(hours, rate) end end
Let’s step through a substitution, which has an interesting new consequence:
makeratedhourstowages(10)(30) => lam(hours :: Number) > Number: hourstowagesrated(hours, 10) end(30) => hourstowagesrated(30, 10) => 300 # ... after some arithmetic
In a call to map, the lam value is not called immediately, and is passed through. As a reminder, here is the definition of map:
fun map<a, b>(atob :: (a > b), al :: List<a>) > List<b>: doc: "Return a the b's returned from atob on each a in the input" cases(List<a>) al:  empty => empty  link(first, rest) => link(atob(first), map(atob, rest)) end end
Let’s look at a call to map with an anonymous function created from makeratedhourstowages:
map(makeratedhourstowages(10), [list: 35, 40, 30]) => map(lam(hours): hourstowages(hours, 10) end, [list: 35, 40, 30])
=> cases(List<Number>) [list: 35, 40, 30]:  empty => empty  link(first, rest) => link((lam(hours): hourstowages(hours, 10) end(first)), map(lam(hours): hourstowages(hours, 10) end, rest)) end => link(lam(hours): hourstowages(hours, 10) end(35), map(lam(hours): hourstowages(hours, 10) end, [list: 40, 30]))
=> link(hourstowages(35, 10), map(lam(hours): hourstowages(hours, 10) end, [list: 40, 30])) => link(350, # skipping arithmetic again map(lam(hours): hourstowages(hours, 10) end, [list: 40, 30]))
=> link(350, cases(List<Number>) [list: 40, 30]:  empty => empty  link(first, rest) => link((lam(hours): hourstowages(hours, 10) end(first)), map(lam(hours): hourstowages(hours, 10) end, rest)) end)
Anonymous functions are a useful tool when working with functions like map, because they provide a way to manage multiargument functions, and also can create functions to use in map without creating verbose new fun declarations.
As far as definitions go, we call lam expressions anonymous function expressions. When an anonymous function expression’s body has a reference to an identifier that isn’t one of its arguments, we say that it closes over that identifier. Similarly, when a value is substituted for a closed over identifier, we say that the value has been closed over. The resulting function that is closed over other values is called a closure.
Closures will come up many times in the rest of the course, and they are one of the first things we’ll learn to implement.
9 More and Mutually Recursive Data
Linked lists are just one instance of recursive data. There are many other patterns of recursive data to consider, and they have interesting consequences for constructing functions over them.
9.1 Other Recursive Patterns
If you want an introduction to binary trees that uses Pyret, check out this development in PAPL. It’s not required reading for this course, but it shows a nice approach to programming efficiently with functions and recursive data definitions. Binary trees are a familiar instance, that have more than one recursive piece:
data BinTree<a>:  leaf  node(value :: a, left :: BinTree<a>, right :: BinTree<a>) end
Extending the recipe for this kind of recursive data is straightforward. We modify the template to include recursive calls for each recursive piece:
fun bintreefun<a>(t :: BinTree<a>) > ???: cases(BinTree<a>) t:  leaf => ...  node(value, left, right) => ... value ... ... bintreefun(left) ... ... bintreefun(right) ... end end
We can use this template to fill in, for example, treesum, which adds up the numbers in a BinTree<Number>:
fun treesum(t :: BinTree<Number>) > Number: cases(BinTree<Number>) t:  leaf => 0  node(value, left, right) => value + treesum(left) + treesum(right) end where: treesum(leaf) is 0 treesum(node(2, leaf, leaf)) is 2 treesum(node(3, node(4, leaf, leaf), leaf)) is 7 treesum(node(3, node(4, leaf, leaf), node(6, leaf, leaf))) is 13 end
What’s the time complexity of treeinorder, assuming that + is linear time in the length of the lefthand list. Is there a better solution using an accumulator? Or, as another example, treeinorder, which returns a List of the elements in order (note that + is suitable to use as a way to append lists):
fun treeinorder<a>(t :: BinTree<a>) > List<a>: cases(BinTree<a>) t:  leaf => empty  node(value, left, right) => treeinorder(left) + [list: value] + treeinorder(right) end end
This is a straightforward extension of handling recursive datatypes, but is useful to note on its own.
9.2 Mutually Recursive Data
The last section defined binary trees, but what about general trees with lists of children? In this case, we might define it as:
data TList<b>:  tempty  tlink(first :: Tree<b>, rest :: TList) end data Tree<b>:  node(value :: b, children :: TList<b>) end
Note that the type variable b in TList differs from the one in List: it is parametrizing the kind of Tree the first field contains, not the type of the first field itself. What would it look like to define Tree with plain Lists for children?
Here, there is no direct recursion in the body of Tree: its variants of Tree make no reference back to itself. However, they do make reference to TList, which refers back to Tree in the first field of tlink. (We would notice the cycle if we started from TList, as well).
For mutuallyrecursive datatypes, we cannot consider one without the other: Any function that works over Trees may need to consider all the nuances of TLists (or List<Tree>s) as well.
This is true in any examples of the datatype (can you write an example, other than tempty, that uses one without the other?), and in the code that we write. Let’s try to develop treesum with this definition, starting with a template:
fun treesum(t :: Tree<Number>) > Number: doc: "Add up the elements of the tree" cases(Tree<Number>) t:  node(val, children) => ... val ... ... children ... end where: treesum(node(4, tempty)) is 4 treesum(node(5, tlink(node(4, tempty), tlink(node(6, tempty), tempty))) is 15 end
We want to add val (which we know to be a number), to the sum of the list of children. That’s a big enough job that it should be deferred to a helper, so:
fun listsum(l :: TList<Number>) > Number: doc: "Add up the elements of the list" end fun treesum(t :: Tree<Number>) > Number: doc: "Add up the elements of the tree" cases(Tree<Number>) t:  node(val, children) => val + listsum(children) end end
Now, we can insert the template for listsum, which contains a recursive call for the rest field, and no guidance (yet) on the first field:
fun listsum(l :: TList<Number>) > Number: doc: "Add up the elements of the list" cases(TList<Number>) l:  tempty => 0  tlink(first, rest) => ... first ... ... listsum(rest) ... end end fun treesum(t :: Tree<Number>) > Number: doc: "Add up the elements of the tree" cases(Tree<Number>) t:  node(val, children) => val + listsum(children) end end
If we follow the same rule we followed for treesum, we ought to be able to just call back into treesum for first:
fun listsum(l :: TList<Number>) > Number: doc: "Add up the elements of the list" cases(TList<Number>) l:  tempty => 0  tlink(first, rest) => treesum(first) + listsum(rest) end end fun treesum(t :: Tree<Number>) > Number: doc: "Add up the elements of the tree" cases(Tree<Number>) t:  node(val, children) => val + listsum(children) end end
This completes the definition, and the tests defined above will now pass. As usual, it’s useful to step through an evaluation of an example to see the pattern in action:
treesum(node(5, tlink(node(4, tempty), node(6, tempty))))
=> cases(Tree<Number>) node(5, tlink(node(4, tempty), tlink(node(6, tempty), tempty))):  node(val, children) => val + listsum(children) end => 5 + listsum(tlink(node(4, tempty), node(6, tempty))) => 5 + cases(TList<Number>) tlink(node(4, tempty), tlink(node(6, tempty), tempty)):  tempty => 0  tlink(first, rest) => treesum(first) + listsum(rest) end
=> 5 + (treesum(node(4, tempty)) + listsum(tlink(node(6, tempty), tempty))) => 5 + (cases(Tree<Number>) node(4, tempty):  node(val, children) => val + listsum(children) end + listsum(tlink(node(6, tempty), tempty))) => 5 + ((4 + listsum(tempty)) + listsum(tlink(node(6, tempty), tempty)))
Note that these calls are quite deeply nested; now another call to listsum needs to be resolved before we can go on.
=> 5 + ((4 + cases(TList<Number>) tempty:  tempty => 0  tlink(first, rest) => treesum(first) + listsum(rest) end) + listsum(tlink(node(6, tempty), tempty))) => 5 + ((4 + 0) + listsum(tlink(node(6, tempty), tempty)))
Up to here corresponds to processing the first subtree of the input. The 4 corresponds to the treesum call in listsum.
=> 5 + (4 + listsum(tlink(node(6, tempty), tempty)))
It’s a useful exercise to fill in the rest of the reduction down to, eventually, 5 + (4 + 6), corresponding to the three value fields in the original tree. Do that now if you’re not positive what it would look like.
We can extract some new rules from this: if we notice a cycle in the datatypes used in a data definition, we need to make sure that we handle the whole cycle when we think through examples, and through the template. When designing the template, we should consider a template for each datatype involved in the cycle. In this example, that would mean a template like:
fun tlistfun<a>(l :: TList<a>) > ???: cases(TList<a>) l:  tempty => ...  tlink(first, rest) => # call to treefun, which will be handled below ... treefun(first) ... ... tlistfun(rest) ... end end fun treefun<a>(t :: Tree<a>) > a: cases(Tree<a>) t:  node(val, children) => ... val ... # call to tlistfun, to handle children above ... tlistfun(children) ... end end
This generalizes to mutual recursion between any number of data definitions. If you notice that your data definitions have a cycle of reference, be aware that you’ll need to work through examples and an implementation that handles all of them.
9.3 A Note on Parametric Data Definitions
The definition in the last section made up a new datatype, TList, for representing lists of trees. That was useful for an example, but most of the time, it would be preferable to just use the builtin List datatype rather than defining something totally new. So a Tree definition like this would make better use of Pyret’s builtins:
data Tree<a>:  node(value :: a, children :: List<Tree<a>>) end
The template wouldn’t change much; it would simply refer to List<Tree<a>> instead of TList<a>, and listsum would use List<Tree<Number>> instead of TList<Number>. But we saw other functions that used Lists, and conceivably the lists that they work over could have subelements that are Trees. Does that mean that map, and length, need to be concerned with Trees? Hopefully the answer is no, because otherwise we’d need to rethink the whole discussion about map in Abstracting Common Parts of List Functions to account for Trees!
This brings up an important distinction between the data that a specific problem works with, and a single Pyret data declaration. Problems that work over Tree<Number>s are concerned with specifically List<Tree<Number>>s, not any other kind of list. When writing functions over List<Tree<Number>>s, it’s natural that we have to take Trees into account, and consider Treehandling functions in the template. The data definition of a Tree problem specifies the type of data that the list works with, and it becomes part of the examples and the problem template.
However, other instantiations of List, like List<Number>, have no relationship with Trees, and those problems have no reason to include templates for Trees. The problem we’re trying to solve dictates the types of data to use, which may include some specific instantiations, and that guides us towards a template.
Finally, describing some problems’ data doesn’t require a fully instantiated datatype. For example, taking the length of a list, or calculating the number of nodes in a tree, work for any instantiation of a List or Tree. Since these problems can be solved without referring to particular instantiations, they don’t need to consider the contents at all.
10 Naming Intermediate Values
Sometimes, we perform a computation and want to use the result more than once. For example, in this implementation of maxinlist, we get the max value from the rest of the list in two places:
fun maxinlist(l :: List<Number>) > Number: doc: "Return the largest number in the list" cases(List<Number>) l:  empty => 0  link(first, rest) => if first > maxinlist(rest): first else: maxinlist(rest) end end where: maxinlist([list: 1, 5, 4]) is 5 maxinlist([list:]) is 0 end
The expression maxinlist(rest) appears twice in this example. To avoid duplicating it, we can give it a name, like this:
fun maxinlist(l :: List<Number>) > Number: doc: "Return the largest number in the list" cases(List<Number>) l:  empty => 0  link(first, rest) => maxrest = maxinlist(rest) if first > maxrest: first else: maxrest end end end
We call the expression maxrest = maxinlist(rest) an identifier binding or let binding expression. We need to add a new rule for reducing this kind of expression. It’s a little different than the rules we’ve seen so far, because it takes multiple expressions into account. When handling an identifier binding, we look at the binding expression itself and the expression(s) immediately after it in the same block of code. So in the example above, we’d be considering:
maxrest = maxinlist(rest) if first > maxrest: first else: maxrest end
An identifier binding evaluates by evaluating the expression to the right of the = sign, and then substituting the resulting value into the rest of the expressions after it. Before stepping through all of maxinlist, here’s a short example that has a similar structure:
x = 5 + 5 if x > 9 x else: x + 11 end => x = 10 if x > 9 x else: x + 11 end
This is where x in the rest of the expressions (the if expression) gets substituted with 10.
=> if 10 > 9: 10 else: 10 + 11 end => if true: 10 else: 10 + 11 end => 10
So, a full substitution for a call to maxinlist would look like:
maxinlist([list: 1, 5]) => cases(List<Number>) [list: 1, 5]:  empty => 0  link(first, rest) => maxrest = maxinlist(rest) if first > maxrest: first else: maxrest end end => maxrest = maxinlist([list: 5]) if 1 > maxrest: 1 else: maxrest end
This step is interesting, because we have to process the maxinlist call to find the answer to store in maxrest.
=> maxrest = cases(List<Number>) [list: 5]:  empty => 0  link(first, rest) => maxrest = maxinlist(rest) if first > maxrest: first else: maxrest end end if 1 > maxrest: 1 else: maxrest end
The block: ... end notation is used to explicit indicate that there is a sequence of expressions that will be evaluated just like any other. Note that we have two maxrests, each of which will be substituted into its own block.
=> maxrest = block: maxrest = maxinlist([list:]) if 5 > maxrest: 5 else: maxrest end end if 1 > maxrest: 1 else: maxrest end => maxrest = block: maxrest = cases(List<Number>) [list:]:  empty => 0  link(first, rest) => if first > maxrest: first else: maxrest end end if 5 > maxrest: 5 else: maxrest end end if 1 > maxrest: 1 else: maxrest end
Now there is a value, 0, to substitute for the maxrest that is further to the right, so we can do the substitution for maxrest where it appears.
=> maxrest = block: maxrest = 0 if 5 > maxrest: 5 else: maxrest end end if 1 > maxrest: 1 else: maxrest end => maxrest = block: if 5 > 0: 5 else: 0 end end if 1 > maxrest: 1 else: maxrest end => maxrest = block: if true: 5 else: 0 end end if 1 > maxrest: 1 else: maxrest end
When a block: contains only a single value expression, it evaluates to that value.
=> maxrest = block: 5 end if 1 > maxrest: 1 else: maxrest end => maxrest = 5 if 1 > maxrest: 1 else: maxrest end
Now we can substitute for the first maxrest, and finish the if evaluation to get 5.
=> if 1 > 5: 1 else: 5 end => if false: 1 else: 5 end => 5
If there are multiple identifier bindings in a row, they are processed in order, and get substituted into the righthandsides of any other bindings that happen later in the same block:
=> x = 4 + 5 y = x + 10 z = y + x z  3 => x = 9 y = x + 10 z = y + x z  3 => y = 9 + 10 z = y + 9 z  3 => y = 19 z = y + 9 z  3 => z = 19 + 9 z  3 => z = 28 z  3 => 28  3 => 25
10.1 Some Gotchas
Standalone Bindings: A letbinding expression doesn’t make much sense on its own; in this binding, what expression can y be substituted into?
fun add5(x :: Number) > Number: y = x + 5 end
Pyret cannot do anything meaningful with the body of add5, so Pyret reports an error upon running this program, that the block ended in a letbinding and thus cannot be evaluated. This version of add5 would make sense:
fun add5(x :: Number) > Number: y = x + 5 y end
Conditional Assignment: A common pattern in Python is to conditionally assign a value to a variable:
def get_by_index(l, i): 
"""Use i if it is 0 or positive, length of list  i otherwise""" 
if i < 0: 
index_to_use = len(l) + i 
else: 
index_to_use = i 
return l[index_to_use] 

get_by_index([1, 2, 3], 1) # is 3 
get_by_index([1, 2, 3], 1) # is 2 
The analogous Pyret program is an error:
fun getbyindex<a>(l :: List<a>, i :: Number) > a: if i < 0: indextouse = l.length() + i else: indextouse = i end l.get(indextouse) end
Do you see why? It has exactly the problem that was mentioned in the last section: it ends a block in a letbinding. Actually, it does it twice, in the branches of the ifelse statement. There’s a way to accomplish what we want in Pyret, though, because if is an expression that can appear on the righthand side of a binding:
fun getbyindex<a>(l :: List<a>, i :: Number) > a: indextouse = if i < 0: l.length() + i else: i end l.get(indextouse) where: getbyindex([list: 1, 2, 3], 1) is 3 getbyindex([list: 1, 2, 3], 1) is 2 end
There are a few main takeaways here:
Identifier binding works by substitution, just like function parameters do upon function application.
Substitution isn’t defined when there is no expression to substitute into. If you see an error telling you "block ended in a letbinding", you may need to slightly restructure that block.
The x = e expression is not an assignment expression, and doesn’t change anything about any existing values. It simply evaluates the righthandside, and then performs substitution.