5 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: /// 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

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

| [] -> []

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

[ 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 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 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 =

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

let diff = e - s

xs |> drop (s - 1) |> take (diff + 1)

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

let diff = e - s

xs |> drop (s - 1) |> take (diff + 1)

let slice' xs s e = [ for (x,j) in Seq.zip xs [1..e] do

if s <= j then

yield x ]

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

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

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

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: |
3 years ago |

Author: |
Cesar Mendoza (website) |

Tags: |
Ninety-Nine F# Problems, tutorial, F#, lists |