In this lab, we will talk about what sequences are and you’ll get some practice using them. Please take advantage of this opportunity to practice writing functions with the assistance of the TAs and your classmates. You are encouraged to collaborate with your classmates and to ask the TAs for help.
1.1 Getting Started
Update your clone of the git repository to get the files for this weeks lab as usual by running
from the top level directory (probably named 15150).
You should practice writing requires and ensures specifications, and tests on the functions you write on this assignment. In particular, every function you write should have both specs and tests.
1.3 Compiling This Lab
As is common with modular code, this lab is distributed across many files and relies on the SML/NJ compilation manager to introduce structures into the environment at the right time. The files that contain relevant code are listed in the file sources.cm, and the compilation manager takes it from there. When you want to run your code for this lab, at the REPL, you will enter
As you progress through the lab, you’ll have to edit the sources.cm file to uncomment the files you’ve filled in. Make sure you’re comfortable with this process! The current homework is organized in the same way, so ask your TA or a neighbour if you can’t get this to work.
2 Sequences Cheat-Sheet
For your convenience a brief description of some of the functions on sequences is given here.
- Seq.map : (’a -> ’b) -> ’a Seq.seq -> ’b Seq.seq, which takes a function and a sequence and returns a sequence whose elements are the result of applying the given function to the corresponding element in the given sequence.
- Seq.reduce : (’a * ’a -> ’a) -> ’a -> ’a Seq.seq -> ’a, which combines all the elements of a sequence using a particular function and base case.
- Seq.mapreduce : (’a->’b) -> ’b -> (’b * ’b -> ’b) -> ’a Seq.seq -> ’b, which combines the operations of Seq.map and Seq.reduce by applying the given func-
tion of type ’a -> ’b to each element of the sequence before combining them as in
- Seq.length : ’a Seq.seq -> int, which returns the number of elements in the sequence.
- Seq.nth : int -> ’a Seq.seq -> ’a, which returns the element of the given se- quence at the indicated index, assuming it is in bounds.
- Seq.tabulate : (int -> ’a) -> int -> ’a Seq.seq, which computes a sequence of the given length such that the value of each element of the sequence is the result of applying the function to its index.
- Seq.singleton : ’a -> ’a Seq.seq, which takes a value and produces a sequence containing only that value.
- Seq.append : ’a Seq.seq -> ’a Seq.seq -> ’a Seq.seq, which takes two sequences and appends the second to the end of the first
3 Mapreduce All Day
mapreduce is intended to be used with a function f of type t1 -> t2 for some types t1 and t2, an associative binary function g of type t2 * t2 -> t2, a value z:t2, and a sequence of items of type t1.
The behavior of mapreduce f z g <x1, . . ., xn> (assuming that g is associative) is given by:
mapreduce f z g hx1 , . . . xni = (f x1 ) g (f x2 ) g . . . g (f xn) g z
The implementation of mapreduce uses a balanced parenthesization format for pairwise combinations, as with reduce. Its work and span are as for reduce, when f and g are constant time.
Although asymptotically mapping and then reducing has the same complexity as mapreduce, it, mapreduce, is actually the more efficient of the two because it doesn’t create an interme- diate sequence.
Let’s learn how to use mapreduce. First things first: it is so easy to construct lists.
Task 3.1 Write the function
seqFromList : ’a list -> ’a Seq.seq
seqToList : ’a Seq.seq -> ’a list
Hint: You should use mapreduce for seqToList.
Recall the function List.exists : (’a -> bool) -> ’a list -> bool, which deter- mines whether an element of the list satisfies the given predicate. You will write an analogous function for sequences:
Task 3.2 Write the function
seqExists : (’a -> bool) -> ’a Seq.seq -> bool
to determine if the sequence has an element that satisfies the given predicate. Hint: You should use mapreduce.
Task 3.3 Write the function
acronym : (char Seq.seq Seq.seq) -> string
that, given a sequence of nonempty character sequences, finds the string whose characters are the first character of each sequence in their order of appearance. Example:
acronym <<#”S”, #”O”, #”P”, #”R”, #”A”, #”N”, #”O”>,
<#”A”, #”L”, #”T”, #”O”>,
<#”T”, #”E”, #”N”, #”O”, #”R”>,
<#”B”, #”A”, #”S”, #”S”>>
Hint: you should use mapreduce for acronym. str : char -> string and ^: string *
string -> string (careful, it’s infix) will also be useful.
4 Sequence Puzzles
The following functions ask you to become familiar with Seq.tabulate, Seq.length, and
Seq.nth. Add your functions to lab11.sml.
Recall the function transpose from Homework 5:
transpose [[1,2,3], [4,5,6]]
==> [[1,4], [2,5], [3,6]]
Task 4.1 Write
fun transpose (s : ’a Seq.seq Seq.seq) : ’a Seq.seq Seq.seq
that transposes a sequence of sequences. You may assume that s is rectangular, with di- mensions m × n, where m, n > 0. Your solution should have O(m × n) work and O(1) span.
We’ve used the function filter, which takes a predicate and a list, and evaluates to a list with only the items that satisfy the given predicate, before. One of your tasks for this lab is to write an analogous function for sequences.
Task 4.2 Write
fun filter’ (p: ’a -> bool) (s: ’a Seq.seq) : ’a Seq.seq
such that filter’ p s evaluates to a sequence that includes only the elements x of s for which p x = true. Your implementation must not use Seq.filter.
Contraction is an algorithmic technique in which we take a problem, reduce it to a smaller problem and then recurse on the smaller problem. It’s similar to Divide and Conquer (the technique behind merge sort) but differs in a key way. Divide and Conquer is based around the idea that we take our problem, divide it up, perform a recursive call on each part, then combine the results together. In contraction, we take the input, make it smaller, and then
perform a single recursive call on the smaller input. Note that this difference can result in contraction algorithms having much better runtime then divide and conquer algorithms. Contraction is a very powerful technique that you will explore more in 15-210 (if you go on to take it). For our purposes we will use use contraction to implement the sequence function reduce with O(n) work and O(log n) span. The idea is to do pairwise reduction, and is illustrated by the following trace:
reduce op+ 0 <1,2,3,4,4,3,2,1>
==> reduce op+ 0 <3, 7, 7, 3 >
==> reduce op+ 0 <10, 10 >
==> reduce op+ 0 <20>
Task 4.3 Write
fun reduce (f : ’a * ’a -> ’a)(b : ’a)(s : ’a Seq.seq) : ’a Seq.seq
such that reduce f b s functions the same as Seq.reduce and runs in O(n) work and O(log n) span. You may assume that Seq.length s is a power of 2. Your implementation must not use Seq.reduce or Seq.mapreduce.
Have a TA check your code before proceeding!
5 Finitely Branching Parallel Trees
A Finitely Branching Parallel Tree is similar to the binary trees introduced earlier in the class, with the exception that each node can now have an arbitrary number of children (rather than exactly 2). To represent this, we define each node to be a sequence of fbtrees (this allows us to evaluate children of nodes in parallel). The datatype for these fbtrees is as such:
datatype ’a fbtree = Leaf of ’a | Node of ’a fbtree seq
All of the functions we’ve previously defined for binary trees have analogs for fbtrees as well. For example, here is the size function on fbtrees.
fun size (Leaf x) = 1
| size (Node s) = Seq.reduce (op +) 0 (Seq.map size s);
Task 5.1 Write the function
depth : ’a fbtree -> int
Depth for fbtrees is defined as the longest path from the root to a leaf in the tree. A leaf should have depth 1.
Task 5.2 Write the function
trav : ’a fbtree -> ’a list
such that trav T will evaluate to the inorder traversal of the tree T. This function might be useful when testing your code. Hint: the function @ may be useful.
Higher order functions, like map and reduce, can be implemented for fbtrees as well. Here is the implementation for map:
(* fbmap : (’a -> ’b) -> ’a fbtree -> ’b fbtree *) (* REQUIRES: f is a total function *)
(* ENSURES: the output of map f T is equivalent to applying f to all the leaves of T *)
fun fbmap f (Leaf x) = Leaf (f x)
| fbmap f (Node s) = Node (Seq.map (fbmap f) s)
Task 5.3 Write the function
fbreduce : (’a * ’a -> ’a) -> ’a -> ’a fbtree -> ’a
When g is associative and z is a zero for g, fbreduce g z T will evaluate to the result of pairwise combining the items in trav T using g. g is associative when, for all a,b,c, we have g(a,g(b,c)) = g(g(a,b),c)). z is a zero for g when, for all x, we have g(x,z) = x.