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. OK, I Understand
 
Top