comp302 hw3 ocaml
String to Characters to String
We need to implement two functions to simplify the manipulation of
o string_explode : string
-> char list
string_implode
string_explode turns a string into a list of characters and
string_implode turns a list of characters back into a string. To
implement these two functions, use a selection of the following higher-
order functions: List.map, List. fold_right, List. fold_left and
tabulate. tabulate is implemented for you in the prelude.
You may also find the following functions from the OCaml string and
char libraries usetu:
o String.get : string -> int -> char returns the character at
index n in string s.
o String.length
:string -> int returns the length (number of
characters) of the given string
• Char. escaped : char
string returns the string
representation of the given character
In order to get full marks for each question, you must use higher-order
unctions. Solutions using manual recursion will be capped at half
2. Untolding is like folding in reverse.
Whereas folding is about collapsing a list into some value, unfolding is
about generating a list given some initial value called a seed. The
connection between folds and unfolds is the beginning of a wonderful
tale in computer science, but let’s not get ahead of ourselves.
unfold takes three arguments.
1. A function f
“seed which given a seed
generates the next element of the list, as well as the next seed.
2. A function stop
‘seed -> bool which decides when to stop
unfolding.
3. The current seed value b
Take a look at the implementation of unfold is given in the prelude.
With unfold, it’s easy to generate the list of all the natural numbers
up to a certain exclusive limit max. Take a look in the prelude at the
implementation of nats.
Using unfold, write the following functions.
1. Implement evens : int
-› int list such that evens max
computes a list of successive even integers, starting at zero, up to
the given exclusive limit max
2. The Fibonacci sequence is a sequence of integers that begins with
two ones, and such that each successive number is the addition of
the two before it. The beginning of the sequence is 1, 1, 2, 3, 5, 8,
Implement fib : int -> int list. The given integer is not the
length of the sequence to generate, but rather the upper exclusive
limit on how large the numbers in the sequence are allowed to
3. Pascal’s triangle is a number triangle with numbers arranged in
staggered rows such that each number in the triangle is the sum
of the two numbers above it.
In general, row n of Pascal’s triangle is computed from row n – 1 as
– The first and last element of row n is simply 1.
The second element of row n is obtained by adding the tirst
and second elements of row n – 1.
– In general, the ith element of row n is obtained by adding
the i-1th and ith element of row n – 1.
Implement the function pascal : int -> int list list such
that pascal max returns the first n rows of Pascal’s triangle that
are no longer than max.
Hint: you should try to use List.map2 (+) to compute the next
row in the triangle.
4. Finally consider the function zip : ‘a list
‘a list ->
“b) list which “tuples up” the elements of two lists. It
can be implemented by the following recursive tunction.
x::xS,y::ys
=(x,y::zip xsys
‘a list) (12 : ‘b list) : (‘a * ‘b) list
Notice that if one of the lists is shorter than the other, then the
resulting list has the same length as the shorter list.
As in the previous 3 sub-questions, your task is to implement zip
using unfold
3. Let’s *safely
* have cupcakes!
Your task is to implement a function allergy_free : ingredient
list -> cupcake list -> cupcake list. It takes a list of
ingredients allergens and a list of cupcakes cupcakes as input, and
returns the cupcakes from the list that do not contain any of the listed
allergens. Cupcakes in the returned list should appear in the same
order that they did in the input list. Note that none of the ingredient
lists are sorted.
allergy_free [Nuts; Gluten] cupcakes;
cupcake list = [Cupcake (2.75, 90.5, 275, [Dairy; Soy])]
In order to get full marks, you must use each of the following higher
order functions:
o List.filter :
o List.exists
• List. for all: (‘a
(*————————————————————–*)
(* Question 1 : String to Characters to String *)
(*————————————————————–*)
(* 1.1 Turn a string into a list of characters. *)
let string_explode (s : string) : char list =
raise NotImplemented
(* 1.2 Turn a list of characters into a string. *)
let string_implode (l : char list) : string =
raise NotImplemented
(*————————————————————–*)
(* Question 2: unfolding is like folding in reverse *)
(*————————————————————–*)
(* 2.1 Compute the even natural numbers up to an exclusive limit. *)
let evens (max : int) : int list =
raise NotImplemented
(* 2.2 Compute the fibonacci sequence up to an exclusive limit. *)
let fib (max : int) : int list =
raise NotImplemented
(* 2.3 Compute Pascal’s triangle up to a maximum row length. *)
let pascal (max : int) : int list list =
raise NotImplemented
(* 2.4 Implement zip, which converts two lists into a list of tuples.
e.g. zip [1; 2] [‘a’; ‘c’] = [(1, ‘a’); (2, ‘c’)]
Note that if one list is shorter than the other, then the
resulting list should have the length of the smaller list. *)
let zip (l1 : ‘a list) (l2 : ‘b list) : (‘a * ‘b) list =
raise NotImplemented
(*————————————————————–*)
(* Question 3 : Let’s *safely* have cake! *)
(*————————————————————–*)
(* 3. Return the cupcakes from the cupcake list that contain none of the
allergens. *)
let allergy_free (allergens : ingredient list) (cupcakes : cupcake list)
: cupcake list =
raise NotImplemented