OCAML代写 | CSCI 2041 Advanced Programming Principles Homework 3

We are expecting to see your work in your private github repository for this course within a folder named hw3 that is itself within the hws folder. Specific to this homework, this folder should contain five files named prob1.ml through prob5.ml which contain the solutions to Problems 1 through 5,respectively. Further details of what we expect each of these files to contain are provided with the individual problem descriptions below. One general point that should be stressed: any functions that your are asked to write must adhere strictly to the names and types that we have assigned to them. If you do not respect this requirement, our automated tools will fail on your submission and we will not be able to grade you solution, meaning also that you will not get credit for your work.

To help you in following the described protocol, we have included skeleton files named prob1.ml through prob5.ml in the hw3 folder within the hws folder in the public repository for the course. Check this folder out and copy it over to the right place in the local version of your private repository and get started in filling the files out as needed for each problem.

Before you start working on the homework, make sure to read the comments on the protocol for homeworks and the issues we consider when grading. Note in particular that the structure and quality of your programs do matter. So also does presentation: you must not have excessively long lines and you must use indentation to make your program text readable. Also avoid using tabs because they show up differently under different editors and, depending on which editor your grader is using, can make your code look ugly.

2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 2/8

We will write scripts that will run tests on the programs asked for in this homework aimed at giving you preliminary, non-exhaustive feedback on your work. Starting on the day before the submission deadline, we will enable the feedback script on what you push as a solution. This script will generate output which will be written to your repository. After pushing to your repository, wait a little while (about a minute), pull from your repository, and check if a file called hw2_Feedback.md has been created. If this file has not been created, it would mean that the script is not yet active and so you should repeat the process of pushing and then pulling at a later time.

If the file hw3_Feedback.md appears in your repository after a pull, open it and look for lines in it that begin with the string “+ Fail:”. These lines indicate failures of some kind in your code. The text that follows should help you understand what the failure is and, hopefully, how to correct it. After correcting any mistakes, you should push again to your repository, wait a little while, and pull again to receive updated feedback. As we have explained before, you must not rely too much on this feedback mechanism: our script will omit some secret test cases and there are also other aspects of your code that the grader will examine in determining the credit to be given to your work.

A couple of important points that bear repeating: First, the feedback file will be created only when you push a commit that affects the files under hws/hw2 after the script has been enabled. If you pushed your homework before that time, you will have to push it again later in a way that actually changes the contents of the folder in order to trigger the feedback. You can do this by, for example, adding some inconsequential white space somewhere to one of your files in the folder before pushing the repository. The second point to note is that if you do not pull the feedback before trying to make another push, then you will encounter a conflict and your commit will fail. If this happens, you will need to pull from your repository, make a merge and only then try to push. As long as you do not modify the feedback file yourself, i.e. you treat it as a read-only file, such merges should succeed automatically.

Define a function

divide_list : (‘a -> bool) -> ‘a list -> ‘a list * ‘a list
that takes a boolean function over a given type and a list of elements of that type and divides the list into two lists, one containing all the elements that satisfy the boolean function and the other containing those that do not satisfy it. Here are some example interactions that characterize the desired behaviour of the function:

# divide_list (fun x -> true) [];;
– : ‘a list * ‘a list = ([], [])
# divide_list (fun x -> if (String.length x < 4) then true else false) [“this”; “is”; “a”; “list”; “of”; “mixed”; “length”; “strings”];; – : string list * string list = ([“is”; “a”; “of”], [“this”; “list”; “mixed”; “length”; “strings”]) # divide_list (fun x -> if (x mod 2 = 0) then true else false) [1;3;6;8;9;10];;
– : int list * int list = ([6; 8; 10], [1; 3; 9])
#

The second expression that we have asked OCaml to evaluate above makes use of a library function called length that works on strings. This library function is part of a String “module” in OCaml and to 2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 3/8

use it we have to qualify it with the name of the module; this is like the List module and the use that we made in the lecture of the map function from that module. We will talk explicitly about modules later in the course, for now just understand how to use what the library modules provide. Also, you may find it useful to know what OCaml provides you as library functions. For this, look up Part IV of the OCaml manual.

Note: For credit in this problem, you must define divide_list without the use of any OCaml library functions.

In class we considered mapping a function over a list. We should be able to do this for any recursive data type. In this problem we will consider doing it for a binary tree. In particular, let us use the representation for binary trees obtained from the following type declaration:

type ‘a btree =
Empty
| Node of ‘a * ‘a btree * ‘a btree
Define a function
treemap : ‘a btree -> (‘a -> ‘b) -> ‘b btree

That takes a binary tree and a function that acts on the elements of the binary tree as input and transforms the tree into a new tree that is obtained by applying the function to each element in the
tree.

To help you understand the function you need to define a bit better, here are some example applications of it:

# treemap (Node (4, Node (2, Empty, Empty), Node (5, Empty,Empty))) (fun x -> x + 3);;
– : int btree = Node (7, Node (5, Empty, Empty), Node (8, Empty, Empty))
# treemap (Node (4, Node (2, Empty, Empty), Node (5, Empty,Empty))) (fun x -> (x mod 2 = 0));;
– : bool btree =
Node (true, Node (true, Empty, Empty), Node (false, Empty, Empty))
#

For each of the function definitions below

explicitly follow the process that was explained in connection with the definition of append in class to determine if the function definition is type correct, and at the end of it, indicate what type is inferred for the function.

You must show your work for the first of the items above for credit in this problem. Also, do not forget that you have to complete the type checking process to conclude that the function is in fact type correct; if you leave it half way through, it is not clear that the type you infer will actually work,and so you will lose credit.

2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 4/8

1. The function reduce defined as follows:

let rec reduce f lst u =
match lst with
| [] -> u
| (h::t) -> f h (reduce f t u)

2. The function forall2 defined as follows

let rec forall2 p l1 l2 =
match (l1,l2) with
| ([],[]) -> true
| ([],_) -> false
| (_,[]) -> false
| ((h1::t1),(h2::t2)) ->
(p h1 h2) && (forall2 p t1 t2)

Solutions to the two parts of this problem must appear as OCaml comments in distinct areas of the file named prob3.ml. These areas should themselves begin with the OCaml comment
(* Solution to Part i *)
where i represents the relevant part of the question.

Fill in the blanks below to complete the definitions of the functions shown:

1. let append l1 l2 = reduce ___ l1 ___
2. let reverse l1 = accumulate ___ l1 ___
3. let filter f l1 = reduce ___ l1 ___

In case you missed the definition of accumulate in class, here it is let rec accumulate f lst u = match lst with
| [] -> u
| (h::t) -> accumulate f t (f h u)

Also, filter takes a boolean valued function and a list and it produces a list with only the items in the input list that satisfy the input function. Here is a sample interaction that brings its expected behaviour out:

# filter (fun x -> (x mod 2 = 0)) [1;2;3;4;5;6];;
– : int list = [2; 4; 6]
# filter (fun x -> (x mod 2 = 0)) [];;
– : int list = []
#

We will see a direct definition of filter that does not use any predefined functions in class.
Solutions to the two parts of this problem must appear as OCaml comments in distinct areas of the file named prob4.ml. These areas should themselves begin with the OCaml comment

2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 5/8

(* Solution to Part i *)
where i represents the relevant part of the question. These solutions should be preceded by the definitions of reduce and accumulate so that OCaml will be able to successfully compile your file.

Solutions to the two parts of this problem must appear as OCaml comments in distinct areas of the file named prob4.ml. These areas should themselves begin with the OCaml comment
(* Solution to Part i *)

where i represents the relevant part of the question.

This problem concerns substituting OCaml expressions for identifiers in other OCaml expressions.
When you substitute into OCaml expressions that do not involve binding, this is not too difficult to realize. However, things get a bit complicated when you have to consider let or function expressions.
In these cases, you should only substitute if the variable being bound is different from the one being substituted for. Moreover, when you substitute, you have to be careful not to bind variables in the expression being substituted in. The goal is to understand these issues concerning binding that apply not just to OCaml expressions but to other contexts such as when you are building an AI system that reasons.

Concretely, we return to the representation of OCaml expressions that we had seen before.
Specifically, we will work with the type expr type that is defined by the following declaration:
type expr =

Id of string (* for identifiers *)
| Int of int (* for integers *)
| True (* for the boolean value true *)
| False (* for the boolean value false *)
| Plus of (expr * expr) (* for exp1 + exp2 *)
| Minus of (expr * expr) (* for exp1 – exp2 *)
| Times of (expr * expr) (* for exp1 * exp2 *)
| Div of (expr * expr) (* for exp1 / exp2, division being for integers *)
| Lss of (expr * expr) (* for exp1 < exp2 *) | Eq of (expr * expr) (* for exp1 = exp2, = being equality comparison *) | Gtr of (expr * expr) (* for exp1 > exp2 *)
| And of (expr * expr) (* for exp1 && exp2 *)
| Or of (expr * expr) (* for exp1 || exp2 *)
| Not of expr (* for not exp *)
| Cond of (expr * expr * expr) (* for if exp1 then exp2 else exp3 *)
| Let of (string * expr * expr) (* for let = exp1 in exp2 *)
| Fun of (string * expr) (* for fun (x:ty) -> exp *)
| App of (expr * expr) (* for (exp1 exp2) *)

The eventual task is to define a function
subst : expr -> string -> expr -> expr

that takes an expression, the name of an identifier and an expression to replace it with and returns an expression that is obtained by replacing all occurrences of the identifier in the first expression by the second one. How this substitution should work seems fairly straightforward in all the cases except for those of Let and Fun. The following examples show what the function should do in the simple cases:

2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 6/8

# subst (Plus (Int 5, Id “x”)) “x” (Plus (Int 3,Int 4));;
– : expr = Plus (Int 5, Plus (Int 3, Int 4))
# subst (Times (Int 5, Id “y”)) “x” (Plus (Int 3,Int 4));;
– : expr = Times (Int 5, Id “y”)
# subst (Or (Id “x”, And (Not (Id “x”), Int 5))) “x” True;;
– : expr = Or (True, And (Not True, Int 5))
# subst (Cond (Or (Lss (Id “x”,Int 5), Eq (Id “y”, Int 7)), Id “x”, Int 10))
“x” (Plus (Int 3,Int 4));;
– : expr =
Cond (Or (Lss (Plus (Int 3, Int 4), Int 5), Eq (Id “y”, Int 7)),
Plus (Int 3, Int 4), Int 10)
#

Make sure to understand what substitution is doing in these cases before reading on.

Now on to understanding what it is about the let and function expressions that makes things more complicated. There are actually two sources for the complication.

First, if the name of the identifier being substituted for is identical to the identifier bound by the let or the function expression, then no substitution should be made. For example, the following expression

subst (Let (“x”, Id “y”, (Plus (Id “x”,Id “z”)))) “x” (Int 3)
must not evaluate to
Let (“x”, Id “y”, Plus (Int 3, Id “z”))
but to
Let (“x”, Id “y”, Plus (Id “x”, Id “z”)).

Note, however, that we still have to carry out the substitution in the expression that the identifier is getting bound to. For example

subst (Let (“x”, Id “x”, (Plus (Id “x”,Id “z”)))) “x” (Int 3)
should evaluate to
Let (“x”, Int 3, Plus (Id “x”, Id “z”)).

Second, when substituting into a let or function expression, we have to be careful that the expression being substituted does not have identifier occurrences that get accidentally bound in the expression. For example, the expression

subst (Let (“x”, Id “y”, Plus (Id “x”, Id “z”))) “z” (Plus (Int 3, Id “x”))
must not evaluate to
Let (“x”, Id “y”, Plus (Id “x”, Plus (Int 3, Id “x”)))
Instead, we should first “rename” the identifier bound by the let to get an expression something
like
Let (“var1”, Id “y”, Plus (Id “var1”, Id “z”))
and then carry out the substitution to get
Let (“var1”, Id “y”, Plus (Id “var1”, Plus (Int 3, Id “x”)))

2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 7/8

A natural question here is why the renaming is okay. The reason is simple: the main purpose for the name of the identifier being bound in a let or function expression is to determine where to use the expression it is being bound to in the body of the let and so long as we preserve this correspondence, we are not changing the meaning of the expression.

Having understood the nuances of substitution, let us now turn to how we can realize it correctly. We will do this in two steps.

1. First, define the function freeIn : expr -> string -> bool that takes an expression and a name and returns true if that name appears in the expression. Here are some interactions that show the expected behaviour of freeIn:

# freeIn (Plus (Id “x”, Id “y”)) “x”;;
– : bool = true
# freeIn (Plus (Id “x”, Id “y”)) “z”;;
– : bool = false
# freeIn (Let (“x”, Id “x”, Plus (Id “x”, Id “y”))) “x”;;
– : bool = true
# freeIn (Let (“x”, Id “z”, Plus (Id “x”, Id “y”))) “x”;;
– : bool = false
# freeIn (Fun (“x”, Id “x”)) “x”;;
– : bool = false
# freeIn (Fun (“y”, Id “x”)) “x”;;
– : bool = true
#

This function will be used in the next part.

2. Now define the function subst: expr -> string -> expr -> expr. Use the function freeIn to determine if renaming is needed in a let or function expression. To determine this, you have to check if the name bound by the let or by a function argument appears in the expression being substituted. If you do need to rename, you will need a way to generate a new name. Use the following code for this:

let namecounter = ref 0
let newname () =
( namecounter := !namecounter + 1; “var” ^ string_of_int !namecounter)

We will talk about the meaning of this code later in the course. For now, just note that every time you need a new name, you just need to use the expression newname (). Here is an interaction that shows how to use it and what happens when you do:

# newname ();;
– : string = “var1”
#

There is a possibility of course that the “new name” that is generated in this way also already appears in the expression but, for this homework, it is okay to assume that the name will actually be fresh; just be careful not to use an identifier name that begins with “var” in the testing examples you try. However, if building this kind of reliance on the user into your code annoys you like it does me, you might try to make the renaming more robust. For example, here is a case to deliberately break it that my definition if subst resists:

# subst (Let (“y”, Int 5, Id “x”)) “x” (Plus (Id “y”,Id “var1”));;
– : expr = Let (“var2”, Int 5, Plus (Id “y”, Id “var1”))
#

2020/3/3 CSCI 2041, Advanced Programming Principles

www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw3.html 8/8

If you want to build this robustness into your code too but are having difficulties in doing so, ask for suggestions on Piazza or talk to the instructor.

Last modified: Feb 22, 2020. Created by ngopalan atsign umn dot edu. Copyright (c) Gopalan Nadathur.

The views and opinions expressed in this page are strictly those of the page author(s). The contents of this page have not been reviewed or approved by the University of Minnesota.