7 people like it.
Like the snippet!

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: 
 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 11 : Modified run-length encoding.

 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: 
/// * (encode-modified '(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)

() Problem 12 : Decode a run-length encoded list.

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

/// Given a run-length 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)

() Problem 13 : Run-length encoding of a list (direct solution).

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

/// Implement the so-called run-length 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: 
/// * (encode-direct '(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)

(*) Problem 14 : Duplicate the elements of a list.

 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)

() Problem 15 : Replicate the elements of a list a given number of times.

 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)

() Problem 16 : Drop every N'th element from a list.

 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)

(*) Problem 17 : Split a list into two parts; the length of the first part is given.

 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)

() Problem 18 : Extract a slice from a list.

 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)

() Problem 19 : Rotate a list N places to the left.

 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)

(*) Problem 20 : Remove the K'th element from a list.

 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: 
/// * (remove-at '(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 (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

Previous Version Raw view Test code New version

More information

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