6 people like it.
Like the snippet!
NinetyNine F# Problems  Problems 11  20  List, continued]
These are F# solutions of NinetyNine Haskell Problems which are themselves translations of NinetyNine Lisp Problems and NinetyNine Prolog Problems. The solutions are hidden so you can try to solve them yourself.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

/// These are F# solutions of NinetyNine Haskell Problems
/// (http://www.haskell.org/haskellwiki/H99:_NinetyNine_Haskell_Problems),
/// which are themselves translations of NinetyNine Lisp Problems
/// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L99_NinetyNine_Lisp_Problems.html)
/// and NinetyNine Prolog Problems
/// (https://sites.google.com/site/prologsite/prologproblems).
///
/// If you would like to contribute a solution or fix any bugs, send
/// an email to paks at kitiara dot org with the subject "99 F# problems".
/// I'll try to update the problem as soon as possible.
///
/// The problems have different levels of difficulty. Those marked with a single asterisk (*)
/// are easy. If you have successfully solved the preceeding problems you should be able to
/// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of
/// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than
/// 3090 minutes to solve them. Problems marked with three asterisks (***) are more difficult.
/// You may need more time (i.e. a few hours or more) to find a good solution
///
/// Though the problems number from 1 to 99, there are some gaps and some additions marked with
/// letters. There are actually only 88 problems.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

/// Modify the result of problem 10 in such a way that if an element has no duplicates it
/// is simply copied into the result list. Only elements with duplicates are transferred as
/// (N E) lists.
///
/// Example:
/// * (encodemodified '(a a a a b c c a a d e e e e))
/// ((4 A) B (2 C) (2 A) D (4 E))
///
/// Example in F#:
///
/// > encodeModified < List.ofSeq "aaaabccaadeeee"
/// val it : char Encoding list =
/// [Multiple (4,'a'); Single 'b'; Multiple (2,'c'); Multiple (2,'a');
/// Single 'd'; Multiple (4,'e')]
type 'a Encoding = Multiple of int * 'a  Single of 'a
(Solution)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

/// Given a runlength code list generated as specified in problem 11. Construct its
/// uncompressed version.
///
/// Example in F#:
///
/// > decodeModified
/// [Multiple (4,'a');Single 'b';Multiple (2,'c');
/// Multiple (2,'a');Single 'd';Multiple (4,'e')];;
/// val it : char list =
/// ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']
(Solution)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

/// Implement the socalled runlength encoding data compression method directly. I.e.
/// don't explicitly create the sublists containing the duplicates, as in problem 9,
/// but only count them. As in problem P11, simplify the result list by replacing the
/// singleton lists (1 X) by X.
///
/// Example:
/// * (encodedirect '(a a a a b c c a a d e e e e))
/// ((4 A) B (2 C) (2 A) D (4 E))
///
/// Example in F#:
///
/// > encodeDirect < List.ofSeq "aaaabccaadeeee"
/// val it : char Encoding list =
/// [Multiple (4,'a'); Single 'b'; Multiple (2,'c'); Multiple (2,'a');
/// Single 'd'; Multiple (4,'e')]
(Solution)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

/// Example:
/// * (dupli '(a b c c d))
/// (A A B B C C C C D D)
///
/// Example in F#:
///
/// > dupli [1; 2; 3]
/// [1;1;2;2;3;3]
(Solution 1)
(Solution 2)
(Solution 3)
(Solution 4)
(Solution 5)
(Solution 6)
(Solution 7)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

/// Example:
/// * (repli '(a b c) 3)
/// (A A A B B B C C C)
///
/// Example in F#:
///
/// > repli (List.ofSeq "abc") 3
/// val it : char list = ['a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'c'; 'c'; 'c']
(Solution 1)
(Solution 2)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

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

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

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

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

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

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

/// Hint: Use the predefined functions length and (@)
///
/// Examples:
/// * (rotate '(a b c d e f g h) 3)
/// (D E F G H A B C)
///
/// * (rotate '(a b c d e f g h) 2)
/// (G H A B C D E F)
///
/// Examples in F#:
///
/// > rotate ['a';'b';'c';'d';'e';'f';'g';'h'] 3;;
/// val it : char list = ['d'; 'e'; 'f'; 'g'; 'h'; 'a'; 'b'; 'c']
///
/// > rotate ['a';'b';'c';'d';'e';'f';'g';'h'] (2);;
/// val it : char list = ['g'; 'h'; 'a'; 'b'; 'c'; 'd'; 'e'; 'f']
(Solution 1)
(Solution 2)

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

/// Example in Prolog:
/// ? remove_at(X,[a,b,c,d],2,R).
/// X = b
/// R = [a,c,d]
///
/// Example in Lisp:
/// * (removeat '(a b c d) 2)
/// (A C D)
///
/// (Note that this only returns the residue list, while the Prolog version also returns
/// the deleted element.)
///
/// Example in F#:
///
/// > removeAt 1 < List.ofSeq "abcd";;
/// val it : char * char list = ('b', ['a'; 'c'; 'd'])
(Solution 1)
(Solution 2)

union case Encoding.Multiple: int * 'a > 'a Encoding
Multiple items
val int : value:'T > int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int

type int = int32
Full name: Microsoft.FSharp.Core.int

type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
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 (n1) xs
let rec drop n xs =
match xs,n with
 xs,0 > xs
 [],_ > []
 _::xs,n > drop (n1) 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 (n1) xs
let rec drop n xs =
match xs,n with
 xs,0 > xs
 [],_ > []
 _::xs,n > drop (n1) 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
More information