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.

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

 1: /// These are F# solutions of Ninety-Nine Haskell Problems 
 2: /// (http://www.haskell.org/haskellwiki/H-99:_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
 6: /// (https://sites.google.com/site/prologsite/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 = [ 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

Link:	http://fssnip.net/ao
Posted:	1 years ago
Author:	Cesar Mendoza (website)
Tags:	Ninety-Nine F# Problems, tutorial, F#, lists