15-150 Homework #5 Solution

Description

1    Introduction

 

This  homework  will focus on applications  of higher  order  functions,  polymorphism,  and user-defined datatypes.

 

 

1.1     Getting The Homework Assignment

 

The starter files for the homework assignment have been distributed through  our git repos- itory, as usual.

 

 

1.2     Submitting The Homework Assignment

 

Submissions will be handled  through  Autolab,  at

 

https://autolab.cs.cmu.edu

 

In preparation for submission, your hw/05 directory  should contain  a file named exactly

hw05.pdf containing  your written  solutions to the homework.

To submit your solutions, run make from the hw/05 directory (that contains a code folder and a file hw05.pdf). This should produce a file hw05.tar, containing  the files that  should be handed  in for this homework assignment.  Open the Autolab  web site, find the page for this assignment,  and submit  your hw05.tar file via the “Handin  your work” link.

 

The Autolab handin script does some basic checks on your submission:  making sure that the file names are correct; making sure that  no files are missing; making sure that  your code compiles cleanly.  Note that  the handin  script  is not  a grading script—a  timely submission that  passes the handin script will be graded, but will not necessarily receive full credit.  You can view the results  of the handin  script  by clicking the number  (usually  either  0.0 or 1.0) corresponding  to the “check” section of your latest  handin  on the “Handin  History”  page. If this number is 0.0, your submission failed the check script; if it is 1.0, it passed.

Remember  that  your written  solutions  must  be submitted in PDF  format—we  do not accept MS Word files or other formats.

 

Your  hw05.sml file must  contain  all the  code that  you want  to  have  graded  for this assignment,  and must compile cleanly.  If you have a function that  happens to be named the same as one of the  required  functions  but  does not  have the  required  type, it will not  be graded.

 

 

 

 

1.4     Methodology

 

You must  use the five step methodology  discussed in class for writing functions,  for every

function you write in this assignment.  Recall the five step methodology:

 

1. In the first line of comments, write the name and type of the function.

 

2. In the second line of comments, specify via a REQUIRES clause any assumptions about the arguments passed to the function.

 

3. In the third line of comments, specify via an ENSURES clause what  the function com- putes (what  it returns).

 

4. Implement the function.

 

5. Provide testcases, generally in the format

val <return value> = <function> <argument value>. For example, for the factorial function presented  in lecture:

(* fact : int -> int

* REQUIRES: n >= 0

* ENSURES: fact(n) ==> n!

*)

 

fun fact (0 : int) : int = 1

| fact (n : int) : int = n * fact(n-1) (* Tests: *)

val 1 = fact 0

val 720 = fact 6

 

2    Types and Polymorphism

 

In class we discussed typing rules.  In particular:

 

• A function expression fn x => e has type t -> t’ if and only if, by assuming that x

has type t, we can show that  e has type t’.

 

• An application e1  e2  has type t’ if and only if there is a type t such that  e1  has type

t -> t’ and e2  has type t.

 

• An expression can be used at any instance of its most general type.

 

 

 

Task 2.1 (4%).  Consider the following ML function declaration:

 

fun all (your, base) =

case your of

0 => base

|  => “are belong to us” :: all(your – 1, base)

 

What  is the most general type of all?

 

Task 2.2 (2%).  Consider a different ML function:

 

fun funny (f, []) = 0

| funny (f, x::xs) = f(x, funny(f, xs))

 

What  is the most general type of funny?

 

Task 2.3 (2%).  Now consider the following function expression:

 

fn x => (fn y => x)

 

What  is its most general type?

 

Task 2.4 (2%).  Now look at this slightly different expression:

 

(fn x => (fn y => x)) “Hello, World!”

 

What  is the most general type of this expression?

 

3    Bases

 

The  digits  we use to  represent a number  depend  on the  base  we use.   We usually  write numbers  in base ten,  or using digits from 0 to 9.  More generally, numbers  in a particular base b can use digits between 0 and b − 1, inclusive. We can notate  this base with a subscript, so the number fifty-four is 5410 . In computer  science we also commonly see base 2, or binary numbers,  which count with 1s and 0s. For example, 102 = 210 , 112 = 310 , and so on.

We’ll be representing  numbers  in different bases as an int list of digits with the least

significant digit as the first element of the list, so 11002 is [0, 0, 1, 1].

 

 

3.1     Converting to an int

 

Formally,  given a base b and  a string  of n digits  dn dn−1 . . . d1, the  numerical  value of the string is

 

n

X bi−1di

i=1

For example, 3410  is 3 ∗ 101 + 4 ∗ 100 = 3 ∗ 10 + 4 ∗ 1 = 34.

We look at the same example in base 2: 1000102 = 1 ∗ 25 + 1 ∗ 21 = 1 ∗ 32 + 1 ∗ 2 = 34. Given

this formula, we can take any string of digits in a base and convert the digits to an int.

 

Task 3.1 (5%).  Define the higher-order function

 

toInt : int -> int list -> int

 

such that  for all b > 1 and all L : int list, if L is a list of base b digits, then

toInt b L is the corresponding  integer value n.  Note that  toInt is higher-order,  so toInt b should return  a function from int list to int. For example,

 

val base2ToInt = toInt 2 val 2 = base2ToInt [0, 1]

 

3.2     Converting from an int

 

For  any  natural number  n and  a base b, we can convert  n into  base b with  the  following algorithm:

 

1. If n = 0, then stop. You’re done.

 

2. Find the remainder of n divided by b. Prepend this to our current list of digits.

 

3. Do an integer division of n by b.

 

4. Go back to step 1 using n = n div b.

 

For example, this is the process of converting 4210  to base 5.

 

42 mod 5 = 2                                           [42 div 5 = 8]

8 mod 5 = 3                                             [8 div 5 = 1]

1 mod 5 = 1                                             [1 div 5 = 0]

 

Reading from the bottom  up, we get 4210 = 1325 , which we can confirm using the formula for converting to base 10. 1 ∗ 52 + 3 ∗ 5 + 2 = 25 + 15 + 2 = 42.

 

Task 3.2 (5%).  Define the higher order function

 

toBase : int -> int -> int list

 

such that  for all b > 1, n ≥ 0, toBase b n returns  the  representation of n in base b. Again, toBase is higher-order,  so toBase b should return  a function.  For example,

 

val toBase3 = toBase 3 val [2, 1] = toBase3 5

 

 

Task 3.3 (5%).  Define the higher order function

 

convert : int * int -> int list -> int list

 

such  that for all b1, b2 > 1 and  for all L : int list such  that  L is a list  of base b1 digits, convert (b1, b2) L changes the representation of the input  number  from base b1 to base b2.  We should have toInt b2 (convert(b1, b2) L) = toInt b1 L hold for convert. You may use toInt and toBase in your solution.

 

4    Higher-Order Functions

 

Recently  we introduced  several new language  features:   polymorphism,  option  types, and higher-order  functions.   In the  next problems,  you will write  some simple functions  using these new tools.

You’ll start  by  writing  functions  on vectors.   Vectors  of length  n  are  essentially  lists of numbers  which indicate  a direction  and  a magnitude  in Rn .   For  example,  vectors  in R2   are  line segments  from the  origin to  the  (x, y) point they  contain.   We will represent vectors in SML as real lists. Mathematically, then,  a vector ha1, a2 , …, an i translates to [a1, a2, …, an ].

 

 

4.1     Dot product

 

Recall :   To calculate  the dot product  of vectors ~a and ~b

 

~a · ~b = ha1 , a2, …, an i · hb1, b2, …, bn i = (a1  ∗ b1 ) + (a2  ∗ b2) + … + (an ∗ bn )

 

 

Task 4.1 (4%).  Write  the function

 

dotProduct : real list * real list -> real

 

that  calculates  the  dot product  of two  vectors  of the  same length.  You solution  should be non-recursive and it should instead  use higher order functions  to accomplish its goal. Hint: You can use

 

zip: ’a list * ’b list -> (’a * ’b) list

 

 

 

4.2     Magnitude

 

Recall :   The magnitude  of a vector ~a, denoted  by ||~a||, is

q                          

 

||~a|| = ||ha1, a2 , …, an i|| =

a2  + a2  + … + a2

 

1          2                      n

 

 

Task 4.2 (4%).  Write  the function

 

magnitudeOfVector : real list -> real

 

that  calculates  the magnitude  of a given vector.  You solution should be non-recursive  and should again use higher order functions.  Note that  you can use

 

Math.sqrt : real -> real

 

to calculate  the square root of a real number.

 

4.3     Angle

 

Now that  we can calculate the dot product  of two vectors and their magnitudes,  we can also calculate  the angle between them.

Recall :   The angle between two vectors ~a and ~b is

   ~a · ~b      !

 

θ = cos−1

 

 

Task 4.3 (5%).  Write  the function

||

||~a|| ∗   ~b||

 

 

 

angleBetweenVectors : real list * real list -> real

 

that  calculates the angle between given vectors.  Please note that  you can use

 

Math.acos : real -> real

 

to calculate  the inverse cosine of a real number.

 

 

4.4     Extract

 

 

Task 4.4 (7%).  Write  a function

 

fun extract (p : ’a -> bool, l : ’a list) : (’a * ’a list) option =

 

such that

 

1. If there is some element x of l for which p x = true, then extract(p,l) evaluates to

SOME(x,l’), where l’ is l without  that  particular x but  unchanged  otherwise.

 

2. If for every element x of l, p x = false then extract(p,l) evaluates to NONE.

 

If there is more than  one element satisfying the predicate  in a particular argument list, it is your choice which to return.

For example:

 

extract(oddP , [2,3,4]) = SOME (3,[2,4])

extract(oddP , [2,4,6]) = NONE

extract(fn x => String.size x < 2 , [“aaa”,”b”,”bca”])

= SOME (“b”, [“aaa”, “bca”])

 

extract should  be recursive.   You should  use this  function  when you implement  Blocks

World below.

 

5    Blocks World

 

In artificial intelligence, planning is the task of figuring what an agent (a robot, that  paperclip in Microsoft Word, your roommate,  etc.)  should do. One way to solve planning problems is to simulate the circumstances  of the agent, so that  you can simulate plans, and then search through  potential  plans for good ones.

A simple planning  problem,  which is often used to illustrate  this  idea, is blocks world. The idea is that  there are a bunch of blocks on a table:

 

—	—	—
|A|	|B|	|C|
—	—	—

————————-

 

and a robotic hand.  You can pick one block up with the hand:

 

/|\

—

|C|

—

 

 

 

 

 

—  —

|A|  |B|

—  —

 

————————-

 

and place it back on the table or on another  block:

 

—

|C|

—

—  —

|A|  |B|

—  —

————————-

 

Of course, you can’t put a block on one that  already has something on it, so in the next two moves we can’t pick up B and then put it on A. A planning problem would be something like “starting with the blocks on the table,  make the tower BCA”.

In this problem, you will represent blocks world in ML, so that  you can simulate  plans

(we won’t ask you to search for plans that  achieve specific goals).

At the end of the problem, you’ll be able to interact with Blocks World as in the figure above. We’ve written  all the input/output code for you, so you just need to do the interesting bits.

 

 

 

 

 

 

 

– playBlocks ();

 

Possible moves:

pickup <block> from table put <block> on table

pickup <block> from <block>

put <block> on <block>

quit

 

—  —  —

|A|  |B|  |C|

—  —  —

————————-

Next move: pickup C from table

 

/|\

—

|C|

—

 

 

 

 

 

—  —

|A|  |B|

—  —

 

————————- Next move: put C on A

 

—

|C|

—

—  —

|A|  |B|

—  —

————————-

 

 

Figure 1: Sample Blocks World Interaction

 

5.1     Rules

 

We will model Blocks World as follows:

 

• There are three blocks, A, B, C .

 

• We will represent the state of the world as a list of facts.  There are five kinds of facts:

 

–  Block b is free (available  to be picked up)

 

–  Block a is on block b

 

–  Block a is on the table

 

–  The hand is empty

 

–  The hand is holding block b

 

• At each step, there are four possible moves:

 

 

pickup <b> from table put <b> on table pickup <a> from <b> put <a> on <b>

 

These moves act as follows:

 

–  pickup <a> from table

Before: a is free, and a is on the table,  and the hand is empty. After:  the hand holds a.

 

–  put <b> on table

Before: the hand holds b.

After:  the hand is empty,  and b is on the table,  and b is free.

 

–  pickup <a> from <b>

Before: a is free, and a is on b, and the hand is empty. After:  b is free, and the hand is holding a.

 

–  put <a> on <b>

Before: the hand holds a, and and b free.

After:  a is free, the hand is empty,  and a is on b.

 

In these  descriptions,  the  “before” facts must  hold about  the  world for the  move to be executed;  after  executing  the  move, the  “before” facts no longer hold (e.g.  after picking up a block, the hand is no longer empty),  and the “after”  facts holds.

 

5.2     Tasks

 

 

Task 5.1  (5%).  First,  we will need a function to extract  many elements from a list.  Write a function

extractMany : (’a * ’a -> bool * ’a list * ’a list) -> (’a list) option extractMany is polymorphic in the list’s element type, but it needs to test whether two list el-

ements are equal.  For this reason, extractMany takes an argument function eq:’a * ’a -> bool

that  can be used to test  whether two values of type ’a are equal.

extractMany (eq,toExtract,from) “subtracts” the elements of toExtract from from, checking that  all the elements of toExtract are present in from. More formally, if toExtract is a sub-multi-set  (according to the definition given in the subset-sum problem on HW 3, but

using eq to determine when an element “appears”) of from, then extractMany(eq,toExtract,from)

returns  SOME xs, where xs is from with every element of toExtract removed.  If toExtract

is not a sub-multi-set  of from, then  extractMany(eq,toExtract,from) returns  NONE.

This means that  the number of times an element occurs matters, but  order does not:

 

extractMany(inteq, [2,1,2], [1,2,3,3,2,4,2]) = SOME [3,3,4,2]

extractMany(inteq, [2,2], [2]) = NONE

 

You may define this recursively, and should use extract.

 

Task 5.2  (8%).  Define datatypes representing  blocks, moves, and  facts,  according  to the above rules:

 

datatype block = … datatype move = … datatype fact = …

 

Observe the convention that  datatype constructors  start  with an upper-case letter (e.g. Node

and Empty).

 

Task 5.3 (2%).  Define a state of the world to be a list of facts:

 

type state = fact list

 

Fill in

 

val initial : state = …

 

to represent the following state:  the hand is empty, each of A,B,C  is on the table, and each of A,B,C  is free.

 

Task 5.4 (3%).  Define a short helper function

 

consumeAndAdd : (state * fact list * fact list) -> state option

 

consumeAndAdd(s,before,after) subtracts before from s and adds after to the result, checking that  every fact in before occurs.  More formally,  if before is a sub-multi-set  of s, then  consumeAndAdd(s, before, after) returns  SOME s’, where s’ is s with before removed and  after added.   If before is not  a sub-multi-set, consumeAndAdd(s, before, after) returns  NONE.

You will need to use the provided function extractManyFacts, which instantiates your

extractMany with an equality operation  derived from the fact datatype.

consumeAndAdd should not be recursive.

 

Task 5.5 (7%).  Implement a function

 

step : (move * state) -> state option

 

If the “before” facts of m hold in s, then  step(m,s) must  return  SOME s’, where s’ is the collection of facts resulting  from performing the move m. It should return  NONE if the move cannot  be applied in that  state.  This function should not be recursive.

 

 

Task 5.6 Optional:  In the file blocks_world.sml, fill in your datatype constructors  at the spots indicated.  You will then  be able to play Blocks World interactively  as follows:

 

– use “hw05.sml”;

– use “blocks_world.sml”;

– playBlocks();

 

This task is optional;  do not hand in blocks_world.sml.

 

 

 

Task 5.7  EXTREMELY OPTIONAL CHALLENGE TASK:

If you’re really really bored, here’s something fun you can try.

The text-based  interface we made for blocks world works but is kind of bland.  Download a graphics library for SML and use it to implement a fancier interface for blocks world. You’ll almost certainly have to make a custom .cm file, so don’t modify the one for this assignment. Make a new one and when you’re done submit  it along with the rest of the homework.

If you want to do 2D graphics you can learn about  SDL::ML at http://www.hardcoreprocessing.com/Freeware/SDLML.html and  if you want  to  do 3D graphics you can learn about  SML3D at http://sml3d.cs.uchicago.edu/.

 

6    Conflatten

 

In this  question  you will prove the  correctness  for some simple functions  on lists.   First, consider the declaration  for the size function.

 

fun size [] = 0

| size ([]::R) = 1 + size R

| size ((x::L)::R) = 1 + size (L::R)

 

 

 

Task 6.1  (2%).  Describe in a sentence or two what size does. Give the most general type for size.

 

Now, consider the following functions:

 

fun flatten [] = []

| flatten (L::R) = L @ flatten R

 

 

fun concat [] = []

| concat ([]::R) = concat R

| concat ((x::L)::R) = x :: concat(L::R)

 

Both  of these  functions  achieve the  same end.  They  take  a list  of lists and put  all the values from each sub-list into a single main list.  For example,

 

val [1, 2, 3] = flatten [[1], [], [2, 3]]

val [1, 2, 3] = concat [[1], [], [2, 3]]

val [“a”, “b”, “c”] = flatten [[“a”, “b”], [], [], [“c”], []]

 

Task 6.2  (12%).  Prove Theorem  1 by induction.  Think  carefully about  what  variable you induct  over, as now you’re inducting  over lists of lists instead  of just  lists.  Be sure to cite any lemmas you use in your proof.1

 

Theorem 1.  For  all types t and for all L : t list list,

 

flatten L = concat L

 

Lemma 1.  size is a total  function.   (ie.   for all types t, for all values L of type t list list then size L evaluates to a value.)

 

Lemma 2.  You may assume that

 

size [] = 0

 

 

Lemma 3.  For  all correctly-typed  values R,

 

size ([] :: R) > size R

 

Lemma 4.  For  all correctly-typed  values x and R,

 

size((x :: L) :: R) > size(L :: R)

 

Lemma 5.  For  all types t and all values L : t list,

either L = [] or L = x :: L’ for some x : t and L’ : t list.

 

Lemma 6.  For  all types t and all values L : t list,

 

[]@L = L

 

Lemma 7.  For  all types t and all values L : t list, R : t list, and x : t,

 

x :: (L@R) = (x :: L)@R

 

 

 

 

 

 

 

 

 

 

 

 

 

1 It’s interesting to note that we could have stated Theorem  1 a more concisely as

 

flatten = concat

 

which is a direct  transcription of the intuition of the problem  into a formal statement. The statement given is an immediate  expansion  of this,  so we don’t lose anything by being a little  bit more verbose.

 

7    Higher-Order Shrubs

 

For the next few problems, we’re going to introduce a different tree-like data structure called a shrub.  Instead  of containing  data  at the nodes, shrubs only have data  at the leaves. You’ll be writing  and  analyzing  higher  order  functions  on polymorphic  shrubs.   Here’s the  type definition of shrub:

 

datatype ’a shrub = Leaf of ’a

| Branch of ’a shrub * ’a shrub

 

 

 

Task 7.1 (5%).  Define a higher order function

 

shrubMap : (’a -> ’b) -> ’a shrub -> ’b shrub

 

such that  for any shrub s : ’a shrub and any total  function f : ’a -> ’b,

shrubMap f s returns  a shrub with f applied to every leaf. For example, to multiply all the leaves by 3 for someShrub : int shrub, we could use shrubMap:

 

val multThree = shrubMap (fn(n) => n * 3)

val newShrub = multThree someShrub

 

 

Task 7.2 (2%).  Write  a recurrence for WshrubM ap (n) where n is the size of the input  shrub. For this and the following problems, assume that  the function f given to shrubMap  has O(1) work and span, and assume that  the input  shrub is balanced.

 

Task 7.3 (1%).  Derive an estimate for the big-O of WshrubM ap (n).

 

Task 7.4 (2%).  Write  a recurrence for SshrubM ap (n).

 

Task 7.5 (1%).  Derive an estimate for the big-O of SshrubM ap (n).

 

Task 7.6 (5%).  Define a higher order function

 

shrubCombine : (’a * ’a -> ’a) -> ’a -> ’a shrub -> ’a

 

such that  for any shrub s : ’a shrub and any total, associative function f : ’a * ’a -> ’a and its corresponding identity  i : ’a, shrubCombine f i s returns  the result of recursively combining the  shrub  with  f.  You can think  of shrubCombine like foldl for shrubs.   For example, to sum all the leaves in a shrub,  we could use shrubCombine:

 

val sumShrub = shrubCombine (op +) 0 val someSum = sumShrub someShrub

 

At a leaf, shrubCombine should  combine the  identity  with  the  value at  the  leaf (in  that order).  At a branch,  shrubCombine should combine sub-branches  in left-to-right order.

For f to be associative, for all well-typed values a, b, c we have:

f(a, f(b, c)) = f(f(a, b), c).   For  example,  addition  is associative  as  (1+2)+3 =

1+(2+3), but  subtraction is not  associative  as (1 − 2) − 3 = 1 − (2 − 3).   The  identity

i of f is a value such that  f(i, a) = f(a, i) = a for all well-typed values a.

And now that  you’ve defined the shrubbery, you must  cut down the mightiest  tree in the forest with…  a herring!