In Ocaml, write a recursive function that takes two lists as arguments and retur

Question

In Ocaml, write a recursive function that takes two lists as arguments and returns a list containing all items that appear in either list with no duplicates. ( You can assume that each of the arguments contains no duplicates, but there mat be items that appear in both lists). DO NOT USE ANY BUILT IN LIST FUNCTIONS

Explanation / Answer

* P01 [+] Find the last box of a list. * Example: * (my-last '(a b c d)) * (D) *) let rec last l = match l with | [] -> None | [a] -> Some a | _::b -> last b ;; assert (last [`a; `b; `c; `d] = Some `d) ;; assert (last [] = None) ;; (* * or using exceptions: which isn't a good idea here *) let rec last_ex l = match l with | [] -> raise (Failure "empty list") | [a] -> a | _::b -> last_ex b ;; assert (last_ex [`a; `b; `c; `d] = `d) ;; try assert (last_ex [] == [`never_happens]) with | Failure "empty list" -> assert true ;; (* * * P02 [+] Find the last but one box of a list. * Example: * (my-but-last '(a b c d)) * (C) *) let rec last_but_one l = match l with | [] | [_] -> None | [x;_] -> Some x | _::t -> last_but_one t ;; assert (last_but_one [1;2;3;4] = Some 3);; assert (last_but_one [1;2] = Some 1);; assert (last_but_one [1] = None);; assert (last_but_one [] = None);; (* * P03: Find the K'th element of a list. * * Example: * kth [1; 2; 3; 4] 3 * 4 *) let rec kth l i = match l with | [] -> None | a::b -> if 1 = i then Some a else kth b (i-1);; assert ((kth [1; 2] 2) = Some 2);; assert ((kth [1; 2] 3) = None);; (* P04 Find the number of elements of a list. *) let rec len l = match l with | [] -> 0 | _::t -> 1 + (len t) ;; assert (len [] = 0);; assert (len [`a] = 1);; assert (len [1;2;3] = 3);; (* * P05 Reverse a list. *) let rec reverse l = match l with | [] -> [] | h::t -> (reverse t) @ [h] ;; assert (reverse [1; 2; 3] = [3; 2; 1]);; assert (reverse [] = []);; (* above example isn't tail recusive optimized *) (* optimized version: *) let reverse l = let rec aux acc l = match l with | [] -> acc | h::t -> aux (h::acc) t in aux [] l ;; assert (reverse [1; 2; 3] = [3; 2; 1]);; assert (reverse [] = []);; (* * P06 Find out whether a list is a palindrome. * A palindrome can be read forward or backward; e.g. (x a m a x). *) let is_palindrome = function s -> s = (reverse s) ;; assert (is_palindrome ["l"; "o"; "l"]);; assert (not (is_palindrome ["l"; "o"; "l"; "o"]));; (* P07 Flatten a nested list structure. * Transform a list, possibly holding lists as elements into a `flat' list by replacing each list with its elements (recursively). * * Example: * flatten (a (b (c d) e)) * (a b c d e) * * Hint: Use the predefined functions list and append. *) type 'a node = One of 'a | Many of 'a node list;; (* unoptimized version *) let rec _flatten l = match l with | [] -> [] | One x::t -> x :: _flatten t | Many x::t -> (_flatten x) @ (_flatten t) ;; let rec flatten l = let rec aux acc l = match l with | [] -> acc | (One x)::t -> x :: aux acc t | (Many x)::t ->( aux acc x) @ (aux [] t) in aux [] l ;; let e07 = [One `a; Many [One `b; Many [One `c; One `d]; One `e]];; let r07 = [`a; `b; `c; `d; `e];; assert (_flatten e07 = r07);; assert ( flatten e07 = r07);; let _pack = function l -> let rec aux acc l = match l with | a::b::t -> (if a = b then (aux (a::acc) (b::t)) else (a::acc)::(aux [] (b::t))) | [a] -> [a::acc] | [] -> [] in aux [] l ;; let pack = function l -> let rec aux q acc l = match l with | a::b::t -> (if a = b then (aux (a::q) acc (b::t)) else (aux [] (acc @ [a::q] ) (b::t))) | [a] -> acc @ [a::q] | [] -> [] in aux [] [] l ;; let e09 = [`a; `a; `a; `a; `b; `c; `c; `a; `a; `d; `e; `e; `e; `e];; let r09= [[`a; `a; `a; `a]; [`b]; [`c; `c]; [`a; `a]; [`d]; [`e; `e; `e; `e]];; assert (_pack e09 = r09);; assert (pack e09 = r09);; (* * P10 Run-length encoding of a list. * Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E. * * Example: * (encode '(a a a a b c c a a d e e e e)) * ((4 a) (1 b) (2 c) (2 a) (1 d)(4 e)) *) let encode = function l -> let rec count cnt l = match l with | h::t -> count (cnt + 1) t | [] -> cnt in let rec aux acc l = match l with | (a::_ as h)::t -> aux (acc @ [((count 0 h), a)]) t | []::t -> aux (acc) t | [] -> acc in aux [] (pack l) ;; let e10 = [`a; `a; `a; `a; `b; `c; `c; `a; `a; `d; `e; `e; `e; `e];; let r10 = [(4, `a); (1, `b); (2, `c); (2, `a); (1, `d); (4, `e)];; assert (encode e10 = r10);; (* * P11 Modified run-length encoding. * Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists. * * Example: * * (encode-modified '(a a a a b c c a a d e e e e)) * ((4 A) B (2 C) (2 A) D (4 E)) *) type 'a entry = Single of 'a | Pair of (int * 'a);; let encode_mod = function l -> let mk_entry q a = if q = 1 then Single a else Pair(q,a) in let rec aux acc l = match l with | (c,a)::t -> (aux (acc @ [mk_entry c a]) t) | [] -> acc in aux [] (encode l) ;; let e11 = [`a; `a; `a; `a; `b; `c; `c; `a; `a; `d; `e; `e; `e; `e];; let r11 = [Pair (4, `a); Single `b; Pair (2, `c); Pair (2, `a); Single `d; Pair (4, `e)];; assert (encode_mod e11 = r11);; (* * P12 Decode a run-length encoded list. * Given a run-length code list generated as specified in problem P11. Construct its uncompressed version. *) let decode l = let rec mul acc n c = match n with | 0 -> acc | n -> mul (c::acc) (n - 1) c in let rec aux acc l = match l with | Pair(i, a)::t -> aux (acc @ (mul [] i a)) t | Single(a) ::t -> aux (acc @ [a]) t | [] -> acc in aux [] l ;; let e12 = [`a; `a; `a; `a; `b; `c; `c; `a; `a; `d; `e; `e; `e; `e];; assert (decode (encode_mod e12) = e12);; (* * P13 [**] Run-length encoding of a list (direct solution). * Implement the so-called run-length encoding data compression method directly. * I.e. don't explicitly create the sublists containing the duplicates, as in * problem P09, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X. * * Example: * * (encode-direct '(a a a a b c c a a d e e e e)) * ((4 A) B (2 C) (2 A) D (4 E)) *) type 'a entry = Single of 'a | Pair of (int * 'a);; let encode_direct = function l -> let mk_entry q a = if q = 1 then Single a else Pair(q,a) in let rec aux q acc l = match l with | a::b::t -> (if a = b then (aux (q+1) acc (b::t)) else (aux 0 (acc @ [(mk_entry (q+1) a)]) (b::t))) | [a] -> acc @ [(mk_entry (q+1) a)] | [] -> [] in aux 0 [] l ;; let e13 = [`a; `a; `a; `a; `b; `c; `c; `a; `a; `d; `e; `e; `e; `e];; let r13 = [Pair (4, `a); Single `b; Pair (2, `c); Pair (2, `a); Single `d; Pair (4, `e)];; assert (encode_direct e13 = r13);;

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.