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 rec 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"]]