## Ninety-Nine F# Problems - Problems 11 - 20 - List, continued]

These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.

Tools:

### Ninety-Nine F# Problems - Problems 11 - 20 - List, continued

``` 1: /// These are F# solutions of Ninety-Nine Haskell Problems
3: /// which are themselves translations of Ninety-Nine Lisp Problems
4: /// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
5: /// and Ninety-Nine Prolog Problems
7: ///
8: /// If you would like to contribute a solution or fix any bugs, send
9: /// an email to paks at kitiara dot org with the subject "99 F# problems".
10: /// I'll try to update the problem as soon as possible.
11: ///
12: /// The problems have different levels of difficulty. Those marked with a single asterisk (*)
13: /// are easy. If you have successfully solved the preceeding problems you should be able to
14: /// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of
15: /// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than
16: /// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult.
17: /// You may need more time (i.e. a few hours or more) to find a good solution
18: ///
19: /// Though the problems number from 1 to 99, there are some gaps and some additions marked with
20: /// letters. There are actually only 88 problems.```

### (*) Problem 11 : Modified run-length encoding.

``` 1: /// Modify the result of problem 10 in such a way that if an element has no duplicates it
2: /// is simply copied into the result list. Only elements with duplicates are transferred as
3: /// (N E) lists.
4: ///
5: /// Example:
6: /// * (encode-modified '(a a a a b c c a a d e e e e))
7: /// ((4 A) B (2 C) (2 A) D (4 E))
8: ///
9: /// Example in F#:
10: ///
11: /// > encodeModified <| List.ofSeq "aaaabccaadeeee"
12: /// val it : char Encoding list =
13: ///   [Multiple (4,'a'); Single 'b'; Multiple (2,'c'); Multiple (2,'a');
14: ///    Single 'd'; Multiple (4,'e')]
15:
16: type 'a Encoding = Multiple of int * 'a | Single of 'a
17:
18: (Solution)```

### (**) Problem 12 : Decode a run-length encoded list.

``` 1: /// Given a run-length code list generated as specified in problem 11. Construct its
2: /// uncompressed version.
3: ///
4: /// Example in F#:
5: ///
6: /// > decodeModified
7: ///     [Multiple (4,'a');Single 'b';Multiple (2,'c');
8: ///      Multiple (2,'a');Single 'd';Multiple (4,'e')];;
9: /// val it : char list =
10: ///   ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']
11:
12: (Solution)```

### (**) Problem 13 : Run-length encoding of a list (direct solution).

``` 1: /// Implement the so-called run-length encoding data compression method directly. I.e.
2: /// don't explicitly create the sublists containing the duplicates, as in problem 9,
3: /// but only count them. As in problem P11, simplify the result list by replacing the
4: /// singleton lists (1 X) by X.
5: ///
6: /// Example:
7: /// * (encode-direct '(a a a a b c c a a d e e e e))
8: /// ((4 A) B (2 C) (2 A) D (4 E))
9: ///
10: /// Example in F#:
11: ///
12: /// > encodeDirect <| List.ofSeq "aaaabccaadeeee"
13: /// val it : char Encoding list =
14: ///   [Multiple (4,'a'); Single 'b'; Multiple (2,'c'); Multiple (2,'a');
15: ///    Single 'd'; Multiple (4,'e')]
16:
17: (Solution)```

### (*) Problem 14 : Duplicate the elements of a list.

``` 1: /// Example:
2: /// * (dupli '(a b c c d))
3: /// (A A B B C C C C D D)
4: ///
5: /// Example in F#:
6: ///
7: /// > dupli [1; 2; 3]
8: /// [1;1;2;2;3;3]
9:
10: (Solution 1)
11:
12: (Solution 2)
13:
14: (Solution 3)
15:
16: (Solution 4)
17:
18: (Solution 5)
19:
20: (Solution 6)
21:
22: (Solution 7)```

### (**) Problem 15 : Replicate the elements of a list a given number of times.

``` 1: /// Example:
2: /// * (repli '(a b c) 3)
3: /// (A A A B B B C C C)
4: ///
5: /// Example in F#:
6: ///
7: /// > repli (List.ofSeq "abc") 3
8: /// val it : char list = ['a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'c'; 'c'; 'c']
9:
10: (Solution 1)
11:
12: (Solution 2)```

### (**) Problem 16 : Drop every N'th element from a list.

``` 1: /// Example:
2: /// * (drop '(a b c d e f g h i k) 3)
3: /// (A B D E G H K)
4: ///
5: /// Example in F#:
6: ///
7: /// > dropEvery (List.ofSeq "abcdefghik") 3;;
8: /// val it : char list = ['a'; 'b'; 'd'; 'e'; 'g'; 'h'; 'k']
9:
10: (Solution 1)
11:
12: (Solution 2)```

### (*) Problem 17 : Split a list into two parts; the length of the first part is given.

``` 1: /// Do not use any predefined predicates.
2: ///
3: /// Example:
4: /// * (split '(a b c d e f g h i k) 3)
5: /// ( (A B C) (D E F G H I K))
6: ///
7: /// Example in F#:
8: ///
9: /// > split (List.ofSeq "abcdefghik") 3
10: /// val it : char list * char list =
11: ///   (['a'; 'b'; 'c'], ['d'; 'e'; 'f'; 'g'; 'h'; 'i'; 'k'])
12:
13: (Solution)```

### (**) Problem 18 : Extract a slice from a list.

``` 1: /// Given two indices, i and k, the slice is the list containing the elements between the
2: /// i'th and k'th element of the original list (both limits included). Start counting the
3: /// elements with 1.
4: ///
5: /// Example:
6: /// * (slice '(a b c d e f g h i k) 3 7)
7: /// (C D E F G)
8: ///
9: /// Example in F#:
10: ///
11: /// > slice ['a';'b';'c';'d';'e';'f';'g';'h';'i';'k'] 3 7;;
12: /// val it : char list = ['c'; 'd'; 'e'; 'f'; 'g']
13:
14: (Solution 1)
15:
16: (Solution 2)
17:
18: (Solution 3)```

### (**) Problem 19 : Rotate a list N places to the left.

``` 1: /// Hint: Use the predefined functions length and (@)
2: ///
3: /// Examples:
4: /// * (rotate '(a b c d e f g h) 3)
5: /// (D E F G H A B C)
6: ///
7: /// * (rotate '(a b c d e f g h) -2)
8: /// (G H A B C D E F)
9: ///
10: /// Examples in F#:
11: ///
12: /// > rotate ['a';'b';'c';'d';'e';'f';'g';'h'] 3;;
13: /// val it : char list = ['d'; 'e'; 'f'; 'g'; 'h'; 'a'; 'b'; 'c']
14: ///
15: /// > rotate ['a';'b';'c';'d';'e';'f';'g';'h'] (-2);;
16: /// val it : char list = ['g'; 'h'; 'a'; 'b'; 'c'; 'd'; 'e'; 'f']
17:
18: (Solution 1)
19:
20: (Solution 2)```

### (*) Problem 20 : Remove the K'th element from a list.

``` 1: /// Example in Prolog:
2: /// ?- remove_at(X,[a,b,c,d],2,R).
3: /// X = b
4: /// R = [a,c,d]
5: ///
6: /// Example in Lisp:
7: /// * (remove-at '(a b c d) 2)
8: /// (A C D)
9: ///
10: /// (Note that this only returns the residue list, while the Prolog version also returns
11: /// the deleted element.)
12: ///
13: /// Example in F#:
14: ///
15: /// > removeAt 1 <| List.ofSeq "abcd";;
16: /// val it : char * char list = ('b', ['a'; 'c'; 'd'])
17:
18: (Solution 1)
19:
20: (Solution 2)```
union case Encoding.Multiple: int * 'a -> 'a Encoding
Multiple items
val int : 'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------

type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type: int<'Measure>
implements: System.IComparable
implements: System.IConvertible
implements: System.IFormattable
implements: System.IComparable<int<'Measure>>
implements: System.IEquatable<int<'Measure>>
inherits: System.ValueType

--------------------

type int = int32

Full name: Microsoft.FSharp.Core.int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
union case Encoding.Single: 'a -> 'a Encoding
/// From problem 9
let pack xs =
let collect x = function
| [] -> failwith "empty list you fool!"
| []::xss -> [x]::xss
| (y::xs)::xss as acc ->
if x = y then
(x::y::xs)::xss
else
[x]::acc
List.foldBack collect xs [[]]

let encodeModified xs = xs |> pack |> List.map (Seq.countBy id >> Seq.head >> fun(x,n)-> if n = 1 then Single x else Multiple (n,x))
let decodeModified xs =
let expand = function
| Single x -> [x]
| Multiple (n,x) -> List.replicate n x
xs |> List.collect expand
let encodeDirect xs =
let collect x = function
| [] -> [Single x]
| Single y::xs when x = y -> Multiple(2, x)::xs
| Single _::_ as xs -> Single x::xs
| Multiple(n,y)::xs when y = x -> Multiple(n + 1, x)::xs
| xs -> Single x::xs
List.foldBack collect xs []
let dupli xs = xs |> List.map (fun x -> [x; x]) |> List.concat
let rec dupli' = function
| [] -> []
| x::xs -> x::x::dupli' xs
let dupli'' xs = [ for x in xs do yield x; yield x ]
let dupli''' xs = xs |> List.collect (fun x -> [x; x])
let dupli'''' xs = (xs,[]) ||> List.foldBack(fun x xs -> x::x::xs)
let dupli''''' xs = ([], xs) ||> List.fold(fun xs x -> xs @ [x; x])
let dupli'''''' xs = xs |> List.collect (List.replicate 2)
let repli xs n = xs |> List.collect (List.replicate n)
let repli' xs n=
[ for x in xs do
for i=1 to n do
yield x ]
let dropEvery xs n = xs |> List.mapi (fun i x -> (i + 1,x)) |> List.filter(fun (i,_) -> i % n <> 0) |> List.map snd
let dropEvery' xs n =
let rec drop xs count =
match xs,count with
| [], _ -> []
| _::xs, 1 -> drop xs n
| x::xs, _ -> x::drop xs (count - 1)
drop xs n
let split xs n =
let rec take n xs =
match xs,n with
| _,0 -> []
| [],_ -> []
| x::xs,n -> x::take (n-1) xs
let rec drop n xs =
match xs,n with
| xs,0 -> xs
| [],_ -> []
| _::xs,n -> drop (n-1) xs
take n xs, drop n xs
let slice xs s e =
let rec take n xs =
match xs,n with
| _,0 -> []
| [],_ -> []
| x::xs,n -> x::take (n-1) xs
let rec drop n xs =
match xs,n with
| xs,0 -> xs
| [],_ -> []
| _::xs,n -> drop (n-1) xs
let diff = e - s
xs |> drop (s - 1) |> take (diff + 1)
let slice' xs s e = [ for (x,j) in Seq.zip xs [1..e] do
if s <= j then
yield x ]
let slice'' xs s e = xs |> Seq.zip (seq {1 .. e}) |> Seq.filter(fst >> (<=) s) |> Seq.map snd
// using problem 17
let rotate xs n =
let at = let ln = List.length xs in abs <| (ln + n) % ln
let st,nd = split xs at
nd @ st
let rec rotate' xs n =
match xs, n with
| [], _ -> []
| xs, 0 -> xs
| x::xs, n when n > 0 -> rotate' (xs @ [x]) (n - 1)
| xs, n -> rotate' xs (List.length xs + n)
let removeAt n xs =
let rec rmAt acc xs n =
match xs, n with
| [], _ -> failwith "empty list you fool!"
| x::xs, 0 -> (x, (List.rev acc) @ xs)
| x::xs, n -> rmAt (x::acc) xs (n - 1)
rmAt [] xs n
// using problem 17
let removeAt' n xs =
let front,back = split xs n
List.head back, front @ List.tail back