F Sharp Programming/Solutions/Lists

List Solutions Pair and Unpair Write two functions with the following definitions: val pair : 'a list -> ('a * 'a) list val unpair : ('a * 'a) list -> 'a list The pair function should convert a list into a list of pairs as follows: pair [ 1 .. 10 ] = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)] pair [ "one"; "two"; "three"; "four"; "five" ] = [("one", "two"); ("three", "four")] The unpair function should convert a list of pairs back into a traditional list as follows: unpair [(1, 2); (3, 4); (5, 6)] = [1; 2; 3; 4; 5; 6] unpair [("one", "two"); ("three", "four")] = ["one"; "two"; "three"; "four"] Solution Using fsi: > let pair l = let rec loop acc = function | [] | [_] -> List.rev acc | h1 :: h2 :: tl -> loop ((h1, h2) :: acc) tl loop [] l let unpair l = let rec loop acc = function | [] -> List.rev acc | (h1, h2) :: tl -> loop (h2 :: h1 :: acc) tl loop [] l;; val pair : 'a list -> ('a * 'a) list val unpair : ('a * 'a) list -> 'a list // Alternative implementations of unpair: > let unpair2 l = List.foldBack (fun (x,y) s -> x::y::s) l [];; val unpair2 : ('a * 'a) list -> 'a list > let unpair2' xs = List.fold (fun acc x -> acc @ (fst x)::(snd x)::[]) [] xs;; val unpair2' : ('a * 'a) list -> 'a list > pair [ 1 .. 10 ];; val it : (int * int) list = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)] > pair [ "one"; "two"; "three"; "four"; "five" ];; val it : (string * string) list = [("one", "two"); ("three", "four")] > unpair [(1, 2); (3, 4); (5, 6)];; val it : int list = [1; 2; 3; 4; 5; 6] > unpair [("one", "two"); ("three", "four")];; val it : string list = ["one"; "two"; "three"; "four"] > unpair (pair [ 1 .. 11 ]);; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] > unpair2 (pair [1..11]);; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] Expand a List Write a function with the following type definition: val expand : 'a list -> 'a list list The expand function should expand a list as follows: expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5] ] expand [ "monkey"; "kitty"; "bunny"; "rat" ] = [ ["monkey"; "kitty"; "bunny"; "rat"]; ["kitty"; "bunny"; "rat"]; ["bunny"; "rat"]; ["rat"] ] Solution This function can be written easily with or without tail recursion. Here are both functions in fsi: > let rec expand_not_tail_recursive = function | [] -> [] | hd :: tl -> (hd :: tl) :: expand_not_tail_recursive tl let expand_tail_recursive l = let rec loop acc = function | [] -> List.rev acc | hd :: tl -> loop ( (hd :: tl) :: acc ) tl loop [] l;; val expand_not_tail_recursive : 'a list -> 'a list list val expand_tail_recursive : 'a list -> 'a list list > expand_tail_recursive [ 1 .. 5 ];; val it : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]] > expand_tail_recursive [ "monkey"; "kitty"; "bunny"; "rat" ];; val it : string list list = [["monkey"; "kitty"; "bunny"; "rat"]; ["kitty"; "bunny"; "rat"]; ["bunny"; "rat"]; ["rat"]] > expand_not_tail_recursive [ 1 .. 5 ];; val it : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]] > expand_not_tail_recursive [ "monkey"; "kitty"; "bunny"; "rat" ];; val it : string list list = [["monkey"; "kitty"; "bunny"; "rat"]; ["kitty"; "bunny"; "rat"]; ["bunny"; "rat"]; ["rat"]] Greatest common divisor on lists gcd can be implemented like this using Euler's algorithm: let rec gcd a b = if a%b=0 then b else gcd b (a%b) gcdl can be implemented like this: let gcdl x = match x with | [] -> 0 | (a::r) -> List.fold gcd a x Basic Mergesort split can be implemented like this: // This is the recursive split implementation let rec split = function | [] -> ([], []) | [a] -> ([a], []) | a::b::cs -> let (r,s) = split cs in (a::r, b::s) // Alternatively fold can be used to implement split // f is used to create the tupel of 2 lists. It inserts the current element in a split and changes the order of them, so the next element will be inserted in the other split. let f (a,b) c = (b, c::a) let split xs = List.fold f ( [], [] ) xs merge can be implemented like this: let rec merge = function | ( [], ys ) -> ys | ( xs, [] ) -> xs | ( x::xr, y::yr ) -> if x<=y then x::merge( xr, y::yr ) else y::merge( x::xr, yr ) // This implementation will result in a type like this // val merge : 'a list * 'a list -> 'a list when 'a : comparison // The reason for this is because we're using the <= operator which can only be used on values that allow comparison (e.g. numbers). // If you wanted to create your own datatype and implement mergesort for this datatype, you would have to use a more complex implementation msort can be implemented like this: let rec msort = function | [] -> [] | [x] -> [x] | xs -> let (ys, zs) = split xs in merge(msort ys, msort zs)