// [snippet: Ninety-Nine F# Problems - Problems 1 - 10 - Lists] /// These are F# solutions of Ninety-Nine Haskell Problems /// (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems), /// which are themselves translations of Ninety-Nine Lisp Problems /// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html) /// and Ninety-Nine Prolog Problems /// (https://sites.google.com/site/prologsite/prolog-problems). /// /// 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 /// 30-90 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. // [/snippet] // [snippet: (*) Problem 1 : Find the last element of a list.] /// Example in F#: /// > myLast [1; 2; 3; 4];; /// val it : int = 4 /// > myLast ['x';'y';'z'];; /// val it : char = 'z' (*[omit:(Solution 1)]*) // Solution using recursion let rec myLast xs = match xs with | [] -> failwith "empty list you fool!" | [x] -> x | _::xs -> myLast xs (*[/omit]*) (*[omit:(Solution 2)]*) // Solution using higher-order functions let myLast' xs = xs |> List.rev |> List.head (*[/omit]*) (*[omit:(Solution 3)]*) // ignore the acumulator using reduce let myLast'' xs = List.reduce(fun _ x -> x) xs (*[/omit]*) // [/snippet] // [snippet: (*) Problem 2 : Find the last but one element of a list.] /// (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' (*[omit:(Solution 1)]*) // Solution with pattern matching let rec myButLast = function | [] -> failwith "empty list you fool!" | [x] -> failwith "singleton list you fool!" | [x;_] -> x | _::xs -> myButLast xs (*[/omit]*) (*[omit:(Solution 2)]*) let myButLast' xs = xs |> List.rev |> List.tail |> List.head (*[/omit]*) (*[omit:(Solution 3)]*) let myButLast'' xs = let flip f a b = f b a xs |> List.rev |> flip List.nth 1 (*[/omit]*) // [/snippet] // [snippet: (*) Problem 3 : Find the K'th element of a list. The first element in the list is number 1.] /// Example: /// * (element-at '(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' (*[omit:(Solution 1)]*) // List.nth is zero based let elementAt xs n = List.nth xs (n - 1) (*[/omit]*) (*[omit:(Solution 2)]*) // 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) (*[/omit]*) // [/snippet] // [snippet: (*) Problem 4 : Find the number of elements of a list.] /// Example in F#: /// /// > myLength [123; 456; 789];; /// val it : int = 3 /// > myLength <| List.ofSeq "Hello, world!" /// val it : int = 13 (*[omit:(Solution 1)]*) // Solution using the library method let myLength = List.length (*[/omit]*) (*[omit:(Solution 2)]*) // replace the elemt with 1 and sum all the ones let myLength' xs = xs |> List.sumBy(fun _ -> 1) (*[/omit]*) (*[omit:(Solution 3)]*) // Solution using tail-recursion let myLength'' xs = let rec length acc = function | [] -> acc | _::xs -> length (acc+1) xs length 0 xs (*[/omit]*) // [/snippet] // [snippet: (*) Problem 5 : Reverse a list.] /// 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] (*[omit:(Solution 1)]*) // Using tail-recursion let reverse xs = let rec rev acc = function | [] -> acc | x::xs -> rev (x::acc) xs rev [] xs (*[/omit]*) (*[omit:(Solution 2)]*) let reverse' xs = List.fold(fun acc x -> x::acc) [] xs (*[/omit]*) (*[omit:(Solution 3)]*) let reverse'' = List.rev (*[/omit]*) // [/snippet] // [snippet: (*) Problem 6 : Find out whether a list is a palindrome.] /// 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 (*[omit:(Solution)]*) // A list is a palindrome is the list is equal to its reverse let isPalindrome xs = xs = List.rev xs (*[/omit]*) // [/snippet] // [snippet: (**) Problem 7 : Flatten a nested list structure.] /// Transform a list, possibly holding lists as elements into a `flat' list by replacing each /// list with its elements (recursively). /// /// Example: /// * (my-flatten '(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 = [] (*[omit:(Solution 1)]*) 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 (*[/omit]*) (*[omit:(Solution 2)]*) #nowarn "40" let flatten' x = let rec loop = List.collect(function | Elem x -> [x] | List xs -> loop xs) loop [x] (*[/omit]*) // [/snippet] // [snippet: (**) Problem 8 : Eliminate consecutive duplicates of list elements.] /// 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"] (*[omit:(Solution 1)]*) 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 [] (*[/omit]*) (*[omit:(Solution 2)]*) let compress' = function | [] -> [] | x::xs -> List.fold(fun acc x -> if x = List.head acc then acc else x::acc) [x] xs |> List.rev (*[/omit]*) // [/snippet] // [snippet: (**) Problem 9 : Pack consecutive duplicates of list elements into sublists.] /// 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']] (*[omit:(Solution)]*) let pack xs = let collect x = function | (y::xs)::xss when x = y -> (x::y::xs)::xss | xss -> [x]::xss List.foldBack collect xs [] (*[/omit]*) // [/snippet] // [snippet: (*) Problem 10 : Run-length encoding of a list.] /// Use the result of problem P09 to implement the so-called run-length /// 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')] (*[omit:(Solutions 1)]*) let encode xs = xs |> pack |> List.map (Seq.countBy id >> Seq.head >> fun(a,b)-> b,a) (*[/omit]*) (*[omit:(Solutions 2)]*) let encode' xs = xs |> pack |> List.map(fun xs -> List.length xs, List.head xs) (*[/omit]*) (*[omit:(Solutions 3)]*) 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 [] (*[/omit]*) // [/snippet]