My solutions to Ninety-Nine Haskell Problems

h-99.lhs

H-99: Ninety-Nine Haskell Problems
==================================

Taken from http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems

Problem 1
---------

Find the last element of a list.

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

Problem 2
---------

Find the last but one element of a list.

> myButLast :: [a] -> a
> myButLast []     = error "myButLast: empty list"
> myButLast [x]    = error "myButLast: singleton list"
> myButLast [x,_]  = x
> myButLast (_:xs) = myButLast xs

Problem 3
---------

Find the kth element of a list. The first element in the list is number 1.

> elementAt :: [a] -> Int -> a
> elementAt []     _ = error "elementAt: empty list"
> elementAt (x:_)  1 = x
> elementAt (_:xs) k = elementAt xs (k-1)

Problem 4
---------

Find the number of elements in a list.

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

Problem 5
---------

Reverse a list.

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

Problem 6
---------

Find out whether a list is a palindrome. A palindrome can be read forward or
backward.

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

Problem 7
---------

Flatten a nested list structure.

Transform a list, possibly holding lists as elements into a 'flat' list by
replacing each list with its elements.

> data NestedList a = Elem a | List [NestedList a]

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

Problem 8
---------

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.

> compress :: (Eq a) => [a] -> [a]
> compress []     = []
> compress (x:xs) = x : (compress $ dropWhile (== x) xs)

Problem 9
---------

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

> pack :: (Eq a) => [a] -> [[a]]
> pack []     = []
> pack (x:xs) = takeWhile (== x) (x:xs) : (pack $ dropWhile (== x) xs)

Problem 10
----------

Run-length encoding of a list. Use the result of problem 9 to implement the
so-called run-length encoding data compression method. Consecutive duplicates of
elements are encoded as tuples (N E) where N is the number of duplicates of the
element E.

> encode :: (Eq a) => [a] -> [(Int,a)]
> encode = encode' . pack
>     where encode' []       = []
>           encode' (xs:xss) = (length xs, head xs) : encode' xss

Problem 11
----------

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

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

> encodeModified :: (Eq a) => [a] -> [ListItem a]
> encodeModified = map modify . encode
>     where modify (1,x) = Single x
>           modify (n,x) = Multiple n x

Problem 12
----------

Decode a run-length encoded list.

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

> decodeModified :: [ListItem a] -> [a]
> decodeModified = concatMap decodeItem
>     where decodeItem (Single x)     = [x]
>           decodeItem (Multiple n x) = replicate n x

Problem 14
----------

Duplicate the elements of a list.

> dupli :: [a] -> [a]
> dupli = concatMap (replicate 2)

Problem 15
----------

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

> repli :: [a] -> Int -> [a]
> repli xs n = concatMap (replicate n) xs

Problem 16
----------

Drop every nth element from a list.

> dropEvery :: [a] -> Int -> [a]
> dropEvery [] _ = []
> dropEvery xs n = take (n-1) xs ++ dropEvery (drop n xs) n

Problem 17
----------

Split a list into two parts; the length of the first part is given.

Do not use any predefined predicates.

> split :: [a] -> Int -> ([a],[a])
> split []     _ = ([],[])
> split xs     0 = ([],xs)
> split (x:xs) n = (x : ys, zs)
>     where (ys,zs) = split xs (n-1)

Problem 18
----------

Extract a slice from a list.

Given two indices i and k the slice is the list containing the elements between
the ith and the kth element of the origion list (both limits included). Start
counting the elements with 1.

> slice :: [a] -> Int -> Int -> [a]
> slice xs i k = drop (i-1) $ take k xs