# 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];  ]
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]; ]

> 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]; ]

> 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)
```