COMP302 OCaml HW3
String to Characters to String
We need to implement two functions to simplify the manipulation of words:
Copyright By PowCoder代写 加微信 powcoder
string_explode : string -> char list
string_implode : char list -> string
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 useful:
String.get : string -> int -> char returns the character at index n in string s.
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 functions. Solutions using manual recursion will be capped at half marks.
Unfolding 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.
A function f : ‘seed -> ‘a * ‘seed which given a seed generates the next element of the list, as well as the next seed.
A function stop : ‘seed -> bool which decides when to stop unfolding.
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.
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
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, 13,…
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 become.
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 follows.
The first and last element of row n is simply 1.
The second element of row n is obtained by adding the first and second elements of row n – 1.
In general, the i th element of row n is obtained by adding the i – 1 th and i th 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.
Finally consider the function zip : ‘a list -> ‘b list -> (‘a * ‘b) list which “tuples up” the elements of two lists. It can be implemented by the following recursive function.
let rec zip (l1 : ‘a list) (l2 : ‘b list) : (‘a * ‘b) list =
match l1, l2 with
| [], _ -> []
| _, [] -> []
| x::xs, y::ys -> (x, y) :: zip xs ys
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
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:
List.filter : (‘a -> bool) -> ‘a list -> ‘a list
List.exists : (‘a -> bool) -> ‘a list -> bool
List.for_all : (‘a -> bool) -> ‘a list -> bool
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com