F Sharp Programming/Solutions/Lists

F# : 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)