Question 5
High on higher-order function
1. (10 points)
In class, we have seen binary trees, which are fixed to having two subtrees, and n-ary trees, which have a list of subtrees. In this question, we will consider (potentially) infinitely-branching trees, which could furthermore be infinitely deep, too.
We define such a tree like this.
type (‘i, ‘a) itree =
| Node of ‘a * (‘i -> (‘i, ‘a) itree) option
I use the name ‘i for the type variable that is the input type of the function ‘i → (‘i, ‘a) itree since it represents some kind of index.
For example, we recover binary trees by using the type bool for ‘i. We obtain infinitely branching trees by using the type int for ‘i (pretending that int is infinite).
Perhaps unremarkably, this definition admits the possibility of defining a map function, which transforms all the data, of type ‘a, into something else, of type ‘b.
Complete the definition of map below, using the following two higher-order helper functions for full marks – a maximum of half marks is allowed if you don’t use either; partial marks are awarded for using just one.
let omap (f: ‘a -> ‘b)(o: ‘a option) : ‘b option = match o with
| None -> None
| Some x -> Some (f x)
let imap (f : ‘a -> ‘b) (g : ‘i -> ‘a) : ‘i -> ‘b = fun x -> f (g x)
Question 5 1
程序代写 CS代考 加QQ: 749389476
let rec map (f : ‘a -> ‘b)(t :(‘i, ‘a) itree):(‘i,’b) itree =
(* Hint: the solution should be two or three lines long. *)
2. (15 points)
Since this tree is computed on demand as we provide values of type ‘i, it doesn’t really represent a data structure. Instead, we can understand it as a kind of state machine. The value of type ‘a contained within a Node corresponds to a state, and the function ‘i – > (‘i, ‘a) tree corresponds to a transition function, which given a choice of a label ‘i takes the machine to a new state. When the option that holds the transition action is None, then we interpret this to mean the machine has reached a final state and stopped running.
We would like to run such a state machine, and obtain the final state that the machine **. However, the machine could actually run forever, so a straightforward implementation of such a runner could loop forever. Instead, the runner will be given an input: int which which represents how many steps it should run the machine for at most. If the machine does not reach a final state before the runner is out of fuel, the runner should out put None. Finally, the runner is equipped with an input next: ‘a → ‘i which state ‘a decides which transition ‘i should be taken.
Complete the implementation of run below.
let rec run (next : ‘a -> ‘i) (fuel : int) (t:(‘i,’a) itree): ‘a option =
*Hint 1:the solution should be around 5 lineslong.*)
*Hint 2:there are three cases to consider:
the machine is in a final state -> we succeed
it is not in a final state and out of fuel-> we fail
in on-final state and non-zero fuel-> run the machine one more step*
3. (15 points)
It turns out that the nature of the state machines we’re running makes it difficult to come up with suitable values to provide for the function next, as next can only return a single
Question 5 2
Code Help, Add WeChat: cstutorcs
value of type ‘i in the above implementation of run.
In this part, you will implement a generalization of run, called search, in which the input function next can return a list of possible transitions to make. The runner should try each
of them in turn, performing a backtracking search through the state machine.
The challenge of this problem lies in the case where the fuel is non-zero and the machine is not in a final state. In that case, applying next to the current state will produce some xs : ‘i list.
Hint: you can define a recursive helper funtion to process this list; it would make a recursive call to search on the head of the list; and if the call to search fails, then it would make a recursive call to the helper to try the next list item. If we run out of list items to
try, then that’s a failure.
For full marks, you must implement this backtracking search using separate success and failure continuations. For half marks, you can implement the backtracking search using option or exceptions. A good strategy, if you have the time, is to write
the search first using option, and then translate it to CPS. Recall that in translating a backtracking search from option to CPS, the type option should disappear completely.
Complete the implementation of run below. You also have the following page to work on. You do not need to consider what to supply as the initial continuations.
(* search: (‘a -> ‘i list) -> int -> (‘i, ‘a) itree ->
(‘a ->’r) -> (unit -> ‘r) -> ‘r *)
let rec search next fuel t return fail =
(* Hint 1: the solution should be around a dozen lines long. *)
(* Hint 2: the structure of the solution is very similar to the previous part. That is, the pattern-matching cases are the same. *)
Question 5 3
Computer Science Tutoring