MP 1 Pattern Matching and Recursion Solution

Change Log




1.0 Initial Release.




 
Objectives and Background




The purpose of this MP is to help the student master:




pattern matching recursion




 
Instructions




The problems below have sample executions that suggest how to write answers. You have to use the same function name, but the name of the parameters that follow the function name need not be duplicated. That is, you are free to choose different names, or patterns, for the arguments to the functions from the ones given in the example execution. We will sometimes use let rec to begin the definition of a function that is allowed to use rec. You are not required to start your code with let rec, and you may use let rec when we do not.




For all these problems, you are allowed to write your own auxiliary functions, either internally to the function being defined or externally as separate functions. In fact, you will find it helpful to do so on several problems. In this assignment, you may only use library functions from the Pervasives module (the one that is loaded by default.) In particular, you must not use any functions from List.




 
Problems




 
(2 pts) Write closer to origin : float * float - float * float - int that takes two 2-dimensional float points and determines which is closer to the origin by Euclidean distance. If the first point is closer, it should evaluate to 1, if the second is closer, it should evaluate to 1, and if the points are equidistant from the origin, it should evaluate to 0.







# closer_to_origin p1 p2 = ...

val closer_to_origin : float * float - float * float - int = <fun




 
closer_to_origin (2., 0.) (0., -1.);; - : int = 1






















1
2. (2 pts) Write swap eq : ’a * ’b - ’b * ’a - bool that takes two pairs and determines whether the second is the left-right swap of the first.







# let swap_eq p1 p2 = ...

val swap_eq : ’a * ’b -> ’b * ’a -> bool = <fun




 
swap_eq (1., 0.) (0., 1.);; - : bool = true







3. (2 pts) Write a function two funs : (’a - ’b) * (’c - ’d) - ’a * ’c - ’b * ’d which




takes a pair of unary functions and a pair of inputs and returns the pair of the first function applied to the first input and the second function applied to the second input.




# let two_funs fns ins = ...

val two_funs : (’a - ’b) * (’c - ’d) - ’a * ’c - ’b * ’d = <fun




# two_funs (not, abs) (true, -5);; - : bool * int = (false, 5)







 
(3 pts) The Ackermann function A : N N ! N is a recursive function defined as follows:




A(m; n) =
8
A(m
1; 1)
if m 0 and n = 0


<
n + 1


if m = 0










: A(m
1; A(m; n 1))
otherwise
Write an OCaml function ackermann : int - int - int that takes the numbers m and n and returns the value of A(m; n). You can assume m and n will be non-negative.




# let rec ackermann m n = ...




val ackermann : int - int - int = <fun




# ackermann 3 4;; - : int = 125










 
(3 pts) The Collatz sequence for a positive integer n starts at n and repeats the following: if the number is even, divide by 2 to get the next number in the sequence. If it is odd, multiply by 3 and add 1. It is conjectured that the

Collatz sequence reaches 1 for any positive integer n. Write a function collatz : int - int which, given an integer n returns the number of steps its Collatz sequence takes to reach 1 (it takes 0 steps for 1 to reach itself.) You can assume n will be positive.




# let rec collatz n = ...




val collatz : int - int = <fun




# collatz 27;; - : int = 111







 
(3 pts) The Delannoy number dm;n counts the number of paths on a gridded m n rectangle from the origin (0; 0) (at the South-West corner of the rectangle) to the point (m; n) (at the North-East corner) where only North, East, and North-East steps are allowed. Note: the number of paths from (0; 0) to (0; 0) is 1. Write a function




delannoy : int * int - int that takes the point (m; n) and returns dm;n. You can assume m and n will be non-negative.







2



# let rec delannoy (m, n) = ...

val delannoy : int * int - int = <fun




 
delannoy (1, 2);; - : int = 5







 
(2 pts) Write a function product : float list - float to find the product of a list of floats. The




product of an empty list is 1:0.




 
let rec product l = ...




val product : float list - float = <fun




 
product [2.; 3.; 4.];; - : float = 24.







 
(2 pts) Write a function double all : float list - float list that takes a list of floats and re-turns back the list with all of the elements doubled.




 
let rec double_all l = ...




val double_all : float list - float list = <fun




 
double_all [1.5; -3.0; 0.; 2.2];; - : float list = [3.; -6.; 0.; 4.4]







 
(3 pts) Write a function upto : int - int list that takes an integer n and returns the list of natural numbers (starting from 0) up to, and including, n.




 
let rec upto n = ...




val upto : int - int list = <fun




# upto 8;;




- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8]







 
(4 pts) Write a function upuntil : (int - bool) - int list that takes a function f from inte-gers to booleans, and returns the list of natural numbers (starting from 0) up until the first number for which f evaluates to true. Do not include this number in the list. If f evaluates to false for the first 100 natural numbers, return the list of the first 100 natural numbers instead.




# let rec upuntil f = ...




val upuntil : (int - bool) - int list = <fun

# upuntil (fun n - n * n 200);;

- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14]







 
(3 pts) Write a function pair with all : ’a - ’b list - (’a * ’b) list that takes a value and a list, and creates a list of pairs where the given value is first in every pair, and the elements of the list are second in the pairs, in the same order as the original list.







# let rec pair_with_all x l = ...

val pair_with_all : ’a - ’b list - (’a * ’b) list = <fun

# pair_with_all 1 ["a"; "b"; "c"];;

- : (int * string) list = [(1, "a"); (1, "b"); (1, "c")]




3



12. (4 pts) Write a function insert by : (’a - ’a - int) - ’a - ’a list - ’a list that takes a comparison function comp, an element x and a list. It returns a list with the element inserted immediately before the first element that is “greater” than x. If no such position exists, insert x at the end of the list. Here “greater” is determined by comp: it takes two elements and returns 1 if the first is “greater”, -1 if the second is “greater”, and 0 if the two are considered equal. Note, if the list is sorted according to the order defined by comp, the order is preserved by the insertion.







# let rec insert_by comp x l = ...




val insert_by : (’a - ’a - int) - ’a - ’a list - ’a list = <fun




 
insert_by compare 3 [1; 2; 4];; - : int list = [1; 2; 3; 4]




 
insert_by closer_to_origin (2., 0.) [(0., -1.); (-3., 0.)];; - : (float * float) list = [(0., -1.); (2., 0.); (-3., 0.)]







 
(5 pts) For two lists L1 and L2, L2 is called a sub-list of L1 if: (a) all the elements of L2 occur in L1, and (b)

their order in L1 is exactly the same as their order in L2. Write a function sub list : ’a list - ’a list - bool that takes two lists as input and determines whether the second list is a sub-list of the first one. The function is required to use (only) tail recursion (no other form of recursion). You may not use any library functions.




 
let rec sub_list l1 l2 = ... ;;




val sub_list : ’a list - ’a list - bool = <fun




 
sub_list [1;1;2;1;1;4;1] [1;2;1;1;1];; - : bool = true













 
Extra Credit




 
(5 pts) Write a function collect adjacent : (’a * ’b) list - (’a * (’b list)) list that takes a list of (key, value) pairs and returns a list of (key, value list) pairs, where every maximal sublist whose pairs have the same key is collected into a single pair, pairing the shared key to the list of all associated values, in the order in which they appeared in the input list.







# let rec collect_adjacent l = ...

val collect_adjacent : (’a * ’b) list - (’a * ’b list) list = <fun




 
collect_adjacent [(1, "a"); (1, "d"); (1, "b"); (0, "b"); (0, "z"); (1, "a"); (1, "z"); (3, "t")];;




- : (int * string list) list =

[(1, ["a"; "d"; "b"]); (0, ["b"; "z"]); (1, ["a"; "z"]); (3, ["t"])]











































4