F Sharp Programming/Solutions/Lists

Pair and Unpair.
Write two functions with the following definitions:
val pair : 'a list -&gt; ('a * 'a) list
val unpair : ('a * 'a) list -&gt; 'a list
The codice_1 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 codice_2 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:
&gt; let pair l =
 let rec loop acc = function
 | [] | [_] -&gt; List.rev acc
 | h1 :: h2 :: tl -&gt; loop ((h1, h2) :: acc) tl
 loop [] l
let unpair l =
 let rec loop acc = function
 | [] -&gt; List.rev acc
 | (h1, h2) :: tl -&gt; loop (h2 :: h1 :: acc) tl
 loop [] l;;
val pair : 'a list -&gt; ('a * 'a) list
val unpair : ('a * 'a) list -&gt; 'a list
// Alternative implementations of unpair:
&gt; let unpair2 l = List.foldBack (fun (x,y) s -&gt; x::y::s) l [];;
val unpair2 : ('a * 'a) list -&gt; 'a list
&gt; let unpair2' xs = List.fold (fun acc x -&gt; acc @ (fst x)::(snd x)::[]) [] xs;;
val unpair2' : ('a * 'a) list -&gt; 'a list
&gt; pair [ 1 .. 10 ];;
val it : (int * int) list = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)]
&gt; pair [ "one"; "two"; "three"; "four"; "five" ];;
val it : (string * string) list = [("one", "two"); ("three", "four")]
&gt; unpair [(1, 2); (3, 4); (5, 6)];;
val it : int list = [1; 2; 3; 4; 5; 6]
&gt; unpair [("one", "two"); ("three", "four")];;
val it : string list = ["one"; "two"; "three"; "four"]
&gt; unpair (pair [ 1 .. 11 ]);;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
&gt; 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 -&gt; 'a list list
The codice_3 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:
&gt; let rec expand_not_tail_recursive = function
 | hd :: tl -&gt; (hd :: tl) :: expand_not_tail_recursive tl
let expand_tail_recursive l =
 let rec loop acc = function
 | [] -&gt; List.rev acc
 | hd :: tl -&gt; loop ( (hd :: tl) :: acc ) tl
 loop [] l;;
val expand_not_tail_recursive : 'a list -&gt; 'a list list
val expand_tail_recursive : 'a list -&gt; 'a list list
&gt; 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
&gt; expand_tail_recursive [ "monkey"; "kitty"; "bunny"; "rat" ];;
val it : string list list
= "monkey"; "kitty"; "bunny"; "rat"]; ["kitty"; "bunny"; "rat"];
 ["bunny"; "rat"]; ["rat"
&gt; 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
&gt; 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.
codice_4 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)
codice_5 can be implemented like this:
let gcdl x = 
 match x with
 | [] -&gt; 0
 | (a::r) -&gt; List.fold gcd a x
Basic Mergesort.
codice_6 can be implemented like this:
// This is the recursive split implementation
let rec split = function
 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
codice_7 can be implemented like this:
let rec merge = function
 | ( [], ys ) -&gt; ys
 | ( xs, [] ) -&gt; xs
 | ( x::xr, y::yr ) -&gt; if x&lt;=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 -&gt; 'a list when 'a : comparison
// The reason for this is because we're using the &lt;= 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
codice_8 can be implemented like this:
let rec msort = function
 | [x] -&gt; [x]
 | xs -&gt; let (ys, zs) = split xs
 in merge(msort ys, msort zs)