• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# recursive types exercises

a guest May 1st, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. (*In this exercise, we implement a queue with a pair of two lists (front, back) such that front @ List.rev back represents the sequence of elements in the queue.
2.
3. Write a function is_empty : queue -> bool such that is_empty q is true if and only if q has no element. *)
4.
5. let is_empty (q : queue) : bool =
6.   match q with
7.   | ([], []) -> true
8.   | _ -> false
9. ;;
10.
11. (*Write a function enqueue : int -> queue -> queue such that enqueue x q is the queue as q except that x is at the end of the queue. *)
12.
13. let rec append i l =
14.   match l with
15.   | [] -> [i]
16.   | hd :: tl -> hd :: (append i tl);;
17.
18. let enqueue (x: int) (q: queue) : queue =
19.   match (x, q) with
20.   | (_, (a, b)) -> (a, (append x b));;
21.
22. (* Write a function split : int list -> int list * int list such that split l = (front, back) where l = back @ List.rev front and the length of back and front is List.length l / 2 or List.length l / 2 + 1 *)
23.
24. let rec take (x: int) (l: 'a list) =
25.   match x with
26.   | 0 -> []
27.   | x -> match l with
28.          | [] -> failwith "take"
29.          | hd :: tl -> hd :: (take (x - 1) tl);;
30.
31. let rec drop (x: int) (l: 'a list) =
32.   if x = 0 then l
33.   else
34.     match l with
35.     | [] -> failwith "drop"
36.     | hd :: tl -> drop (x - 1) tl;;
37.
38. let split (x: int list) : int list * int list =
39.   let left = (drop (List.length x / 2) x) in
40.   let right = (take (List.length x / 2) x) in
41.   ((List.rev left), right);;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top