34 people like it.
Like the snippet!

Ninety-Nine F# Problems - Problems 1 - 10 - Lists

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.

Ninety-Nine F# Problems - Problems 1 - 10 - Lists

 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 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.

(*) Problem 1 : Find the last element of a list.

 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)

(*) Problem 2 : Find the last but one element of a list.

 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)

(*) Problem 3 : Find the K'th element of a list. The first element in the list is number 1.

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

/// 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'

(Solution 1)

(Solution 2)

(*) Problem 4 : Find the number of elements of a list.

 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)

(*) Problem 5 : Reverse a list.

 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)

(*) Problem 6 : Find out whether a list is a palindrome.

 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)

() Problem 7 : Flatten a nested list structure.

 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: 
/// * (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 = []

(Solution 1)

(Solution 2)

() Problem 8 : Eliminate consecutive duplicates of list elements.

 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)

() Problem 9 : Pack consecutive duplicates of list elements into sublists.

 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)

(*) Problem 10 : Run-length encoding of a list.

 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 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')]

(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 higher-order 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 tail-recursion
let myLength'' xs =
    let rec length acc = function
        | [] -> acc
        | _::xs -> length (acc+1) xs
    length 0 xs

// Using tail-recursion
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:
* (my-flatten '(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 []

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/an
Posted:	12 years ago
Author:	Cesar Mendoza
Tags:	ninety-nine f# problems , tutorial , f# , lists