30 people like it.
Like the snippet!
NinetyNine F# Problems  Problems 1  10  Lists
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:

/// Example in F#:
/// > myLast [1; 2; 3; 4];;
/// val it : int = 4
/// > myLast ['x';'y';'z'];;
/// val it : char = 'z'
(Solution 1)
(Solution 2)
(Solution 3)

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

/// (Note that the Lisp transcription of this problem is incorrect.)
///
/// Example in F#:
/// myButLast [1; 2; 3; 4];;
/// val it : int = 3
/// > myButLast ['a'..'z'];;
/// val it : char = 'y'
(Solution 1)
(Solution 2)
(Solution 3)

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

/// Example:
/// * (elementat '(a b c d e) 3)
/// c
///
/// Example in F#:
/// > elementAt [1; 2; 3] 2;;
/// val it : int = 2
/// > elementAt (List.ofSeq "fsharp") 5;;
/// val it : char = 'r'
(Solution 1)
(Solution 2)

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

/// Example in F#:
///
/// > myLength [123; 456; 789];;
/// val it : int = 3
/// > myLength < List.ofSeq "Hello, world!"
/// val it : int = 13
(Solution 1)
(Solution 2)
(Solution 3)

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

/// Example in F#:
///
/// > reverse < List.ofSeq ("A man, a plan, a canal, panama!")
/// val it : char list =
/// ['!'; 'a'; 'm'; 'a'; 'n'; 'a'; 'p'; ' '; ','; 'l'; 'a'; 'n'; 'a'; 'c'; ' ';
/// 'a'; ' '; ','; 'n'; 'a'; 'l'; 'p'; ' '; 'a'; ' '; ','; 'n'; 'a'; 'm'; ' ';
/// 'A']
/// > reverse [1,2,3,4];;
/// val it : int list = [4; 3; 2; 1]
(Solution 1)
(Solution 2)
(Solution 3)

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

/// A palindrome can be read forward or backward; e.g. (x a m a x).
///
/// Example in F#:
/// > isPalindrome [1;2;3];;
/// val it : bool = false
/// > isPalindrome < List.ofSeq "madamimadam";;
/// val it : bool = true
/// > isPalindrome [1;2;4;8;16;8;4;2;1];;
/// val it : bool = true
(Solution)

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

/// Transform a list, possibly holding lists as elements into a `flat' list by replacing each
/// list with its elements (recursively).
///
/// Example:
/// * (myflatten '(a (b (c d) e)))
/// (A B C D E)
///
/// Example in F#:
///
type 'a NestedList = List of 'a NestedList list  Elem of 'a
///
/// > flatten (Elem 5);;
/// val it : int list = [5]
/// > flatten (List [Elem 1; List [Elem 2; List [Elem 3; Elem 4]; Elem 5]]);;
/// val it : int list = [1;2;3;4;5]
/// > flatten (List [] : int NestedList);;
/// val it : int list = []
(Solution 1)
(Solution 2)

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

/// If a list contains repeated elements they should be replaced with a single copy of the
/// element. The order of the elements should not be changed.
///
/// Example:
/// * (compress '(a a a a b c c a a d e e e e))
/// (A B C A D E)
///
/// Example in F#:
///
/// > compress ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
/// val it : string list = ["a";"b";"c";"a";"d";"e"]
(Solution 1)
(Solution 2)

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

/// If a list contains repeated elements they should be placed
/// in separate sublists.
///
/// Example:
/// * (pack '(a a a a b c c a a d e e e e))
/// ((A A A A) (B) (C C) (A A) (D) (E E E E))
///
/// Example in F#:
///
/// > pack ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a';
/// 'a'; 'd'; 'e'; 'e'; 'e'; 'e']
/// val it : char list 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:
18:
19:

/// Use the result of problem P09 to implement the socalled runlength
/// encoding data compression method. Consecutive duplicates of elements
/// are encoded as lists (N E) where N is the number of duplicates of the element E.
///
/// Example:
/// * (encode '(a a a a b c c a a d e e e e))
/// ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))
///
/// Example in F#:
///
/// encode < List.ofSeq "aaaabccaadeeee"
/// val it : (int * char) list =
/// [(4,'a');(1,'b');(2,'c');(2,'a');(1,'d');(4,'e')]
(Solutions 1)
(Solutions 2)
(Solutions 3)

// Solution using recursion
let rec myLast xs =
match xs with
 [] > failwith "empty list you fool!"
 [x] > x
 _::xs > myLast xs
// Solution using higherorder functions
let myLast' xs = xs > List.rev > List.head
// ignore the acumulator using reduce
let myLast'' xs = List.reduce(fun _ x > x) xs
// Solution with pattern matching
let rec myButLast = function
 [] > failwith "empty list you fool!"
 [x] > failwith "singleton list you fool!"
 [x;_] > x
 _::xs > myButLast xs
let myButLast' xs = xs > List.rev > List.tail > List.head
let myButLast'' xs =
let flip f a b = f b a
xs > List.rev > flip List.nth 1
// List.nth is zero based
let elementAt xs n = List.nth xs (n  1)
// Recursive solution with pattern matching
let rec elementAt' xs n =
match xs,n with
 [],_ > failwith "empty list you fool!"
 x::_,1 > x
 _::xs,n > elementAt' xs (n  1)
// Solution using the library method
let myLength = List.length
// replace the elemt with 1 and sum all the ones
let myLength' xs = xs > List.sumBy(fun _ > 1)
// Solution using tailrecursion
let myLength'' xs =
let rec length acc = function
 [] > acc
 _::xs > length (acc+1) xs
length 0 xs
// Using tailrecursion
let reverse xs =
let rec rev acc = function
 [] > acc
 x::xs > rev (x::acc) xs
rev [] xs
let reverse' xs = List.fold(fun acc x > x::acc) [] xs
let reverse'' = List.rev
// A list is a palindrome is the list is equal to its reverse
let isPalindrome xs = xs = List.rev xs
type 'a NestedList =
 List of 'a NestedList list
 Elem of 'a
Full name: Script.NestedList<_>
Transform a list, possibly holding lists as elements into a `flat' list by replacing each
list with its elements (recursively).
Example:
* (myflatten '(a (b (c d) e)))
(A B C D E)
Example in F#:
Multiple items
union case NestedList.List: 'a NestedList list > 'a NestedList

module List
from Microsoft.FSharp.Collections

type List<'T> =
 ( [] )
 ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member Head : 'T
member IsEmpty : bool
member Item : index:int > 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list > 'T list
static member Empty : 'T list
Full name: Microsoft.FSharp.Collections.List<_>
type 'T list = List<'T>
Full name: Microsoft.FSharp.Collections.list<_>
union case NestedList.Elem: 'a > 'a NestedList
let flatten ls =
let rec loop acc = function
 Elem x > x::acc
 List xs > List.foldBack(fun x acc > loop acc x) xs acc
loop [] ls
#nowarn "40"
let flatten' x =
let rec loop = List.collect(function
 Elem x > [x]
 List xs > loop xs)
loop [x]
let compress xs = List.foldBack(fun x acc > if List.isEmpty acc then [x] elif x = List.head acc then acc else x::acc) xs []
let compress' = function
 [] > []
 x::xs > List.fold(fun acc x > if x = List.head acc then acc else x::acc) [x] xs > List.rev
let pack xs =
let collect x = function
 (y::xs)::xss when x = y > (x::y::xs)::xss
 xss > [x]::xss
List.foldBack collect xs []
let encode xs = xs > pack > List.map (Seq.countBy id >> Seq.head >> fun(a,b)> b,a)
let encode' xs = xs > pack > List.map(fun xs > List.length xs, List.head xs)
let encode'' xs =
let collect x = function
 [] > [(1, x)]
 (n,y)::xs as acc>
if x = y then
(n+1, y)::xs
else
(1,x)::acc
List.foldBack collect xs []
More information