99 haskell problems

p99.lhs

Ninety-Nine Haskell Problems
============================

[Original page](https://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems) 


> import Data.List

Lists
-----

* P01. Find the last element of a list.

Example in Haskell:
```haskell
Prelude> myLast [1,2,3,4]
4
Prelude> myLast ['x','y','z']
'z'
```

> myLast :: [a] -> a
> myLast []     = error "myLast: empty list"
> myLast (x:[]) = x
> myLast (x:xs) = myLast xs

* P02. Find the last but one element of a list.

Example in Haskell:
```haskell
Prelude> myButLast [1,2,3,4]
3
Prelude> myButLast ['a'..'z']
'y'
```

> myButLast :: [a] -> a
> myButLast (x:y:[]) = x
> myButLast (x:xs)   = myButLast xs
> myButLast _        = error "myButLast: not found"

* P03. Find the K'th element of a list. The first element in the list is number 1.

Example in Haskell:
```haskell
Prelude> elementAt [1,2,3] 2
2
Prelude> elementAt "haskell" 5
'e'
```

> elementAt :: [a] -> Int -> a
> elementAt (x:xs) n | n == 1    = x
>                    | n >  1    = elementAt xs (n - 1)
>                    | otherwise = error "elementAt: invalid index"
> elementAt [] _     = error "elementAt: invalid index"

* P04. Find the number of elements of a list.

Example in Haskell:
```haskell
Prelude> myLength [123, 456, 789]
3
Prelude> myLength "Hello, world!"
13
```

> myLength :: [a] -> Int
> myLength = foldr (\_ len -> len + 1) 0

* P05. Reverse a list.

Example in Haskell:
```haskell
Prelude> myReverse "A man, a plan, a canal, panama!"
"!amanap ,lanac a ,nalp a ,nam A"
Prelude> myReverse [1,2,3,4]
[4,3,2,1]
```

> myReverse :: [a] -> [a]
> myReverse = foldl (\xs x -> x :  xs) []

* P06. 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 Haskell:
```haskell
Prelude> isPalindrome [1,2,3]
False
Prelude> isPalindrome "madamimadam"
True
Prelude> isPalindrome [1,2,4,8,16,8,4,2,1]
True
```

> isPalindrome :: (Eq a) => [a] -> Bool
> isPalindrome xs = xs == reverse xs

* P07. 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 in Haskell:

We have to define a new data type, because lists in Haskell are homogeneous.
```haskell
data NestedList a = Elem a | List [NestedList a]
Prelude> flatten (Elem 5)
[5]
Prelude> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
[1,2,3,4,5]
Prelude> flatten (List [])
[]
```

> data NestedList a = Elem a | List [NestedList a]
>     deriving (Show)

> flatten :: (NestedList a) -> [a]
> flatten (Elem x)      = [x]
> flatten (List (x:xs)) = (flatten x) ++ (flatten (List xs))
> flatten (List [])     = []

* P08. 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 in Haskell:
```haskell
Prelude> compress "aaaabccaadeeee"
"abcade"
```

> compress :: (Eq a) => [a] -> [a]
> compress (x:ys@(y:_)) = if x == y
>                         then     compress ys
>                         else x : compress ys
> compress xs           = xs

> compress' :: (Eq a) => [a] -> [a]
> compress' xs = map head $ group xs

* P09. Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

Example in Haskell:
```haskell
Prelude> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
["aaaa","b","cc","aa","d","eeee"]
```

> pack :: (Eq a) => [a] -> [[a]]
> pack []      = [[]]
> pack (x:xs)  = reverse $ compact xs [[x]]
>     where compact []     zss      = zss
>           compact (y:ys) l@(zs:zss) = if y == head zs
>                                       then compact ys ((y : zs) : zss)
>                                       else compact ys ([y] : l)

> pack' :: (Eq a) => [a] -> [[a]]
> pack' xs = foldr (compact') [[]] xs
>     where compact' x [[]]              = [[x]]
>           compact' x l@(ys@(z:zs):yss) | z == x    = (x : ys) : yss
>                                        | otherwise = [x] : l

* P10. 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 in Haskell:
```haskell
Prelude> encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]
```

> encode :: (Eq a) => [a] -> [(Int, a)]
> encode xs = map enc $ pack xs
> 	  where enc l@(x : _) = (length l, x	)

* P11. Modified run-length encoding.

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 in Haskell:
```haskell
Prelude> encodeModified "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',
Multiple 2 'a',Single 'd',Multiple 4 'e']
```

> data Encoding a = Multiple Int a | Single a
>     deriving (Show)

> encodePair :: (Eq a) => (Int, a) -> Encoding a
> encodePair (1, x) = Single x
> encodePair (n, x) = Multiple n x

> encodeModified :: (Eq a) => [a] -> [Encoding a]
> encodeModified xs = map encodePair $ encode xs

* P12. Decode a run-length encoded list.

Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.

Example in Haskell:
```haskell
Prelude> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c', Multiple 2 'a',Single 'd',Multiple 4 'e']
"aaaabccaadeeee"
```

> decodeModified :: (Eq a) => [Encoding a] -> [a]
> decodeModified []                  = []
> decodeModified ((Single x):xs)     = x : decodeModified xs
> decodeModified ((Multiple n x):xs) = (replicate n x) ++ decodeModified xs

* P13. Run-length encoding of a list (direct solution).

Implement the so-called run-length encoding data compression method directly.
I.e. don't explicitly create the sublists containing the duplicates, as in P09,
but only count them. As in problem P11, simplify the result list by replacing
the singleton lists (1 X) by X.

Example in Haskell:
```haskell
Prelude> encodeDirect "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
```

> encodeDirect :: (Eq a) => [a] -> [Encoding a]
> encodeDirect = foldr encode []
>    where encode x (y:ys)   | x == valueOf y = (incr y) : ys
>          encode x xs       = Single x : xs
>          valueOf (Single el)     = el
>          valueOf (Multiple _ el) = el
>          incr enc = enc `plus` 1
>          (Single el) `plus` n         = Multiple (n + 1) el
>          (Multiple count el) `plus` n = Multiple (n + count) el

* P14. Duplicate the elements of a list.

Example in Haskell:
```haskell
Prelude> dupli [1, 2, 3]
[1,1,2,2,3,3]
```

> dupli :: [a] -> [a]
> dupli (x:xs) = x : x : dupli xs
> dupli []     = []

* P15. Replicate the elements of a list a given number of times.

Example in Haskell:
```haskell
Prelude> repli "abc" 3
"aaabbbccc"
```

> repli :: [a] -> Int -> [a]
> repli xs n = repl xs n
>     where repl (y:ys)   0 = repl ys n
>           repl l@(y:ys) n = y : repl l (n - 1)
>           repl []       _ = []

* P16. Drop every N'th element from a list.

Example in Haskell:
```haskell
Prelude> dropEvery "abcdefghik" 3
"abdeghk"
```

> dropEvery :: [a] -> Int -> [a]
> dropEvery xs n = every xs n
>    where every (y:ys)  1 = every ys n
>          every (y:ys)  n = y : every ys (n - 1)
>          every []      _ = []

> dropEvery' :: [a] -> Int -> [a]
> dropEvery' xs n = fst $ foldl (every