module MyList (
       compress,
       elementAt,
       encode,
       flatten,
       isPalindrome,
       myButLast,
       myLast,
       myLength,
       myReverse,
       pack
       )where

-- | 01. Find the last element of a list.
--
-- Examples:
--
-- >>> myLast [1,2,3,4]
-- 4
--
-- >>> myLast ['x','y','z']
-- 'z'
--
-- >>> myLast []
-- *** Exception: Empty list has no last element!
--
-- >>> myLast [2]
-- 2
myLast :: [a] -> a
myLast [] = error "Empty list has no last element!"
myLast ([x]) = x
myLast (_:xs) = myLast xs

-- | 02. Find the last but one element of a list.
--
-- Examples:
--
-- >>> myButLast [1,2,3,4]
-- 3
--
-- >>> myButLast ['a'..'z']
-- 'y'
--
-- >>> myButLast []
-- *** Exception: Empty list has no last but one element!
--
-- >>> myButLast [2]
-- *** Exception: List with one element has no last but element!
--
-- >>> myButLast [2, 3]
-- 2
myButLast :: [a] -> a
myButLast [] = error "Empty list has no last but one element!"
myButLast ([_]) = error "List with one element has no last but element!"
myButLast ([x, _]) = x
myButLast (_:xs) = myButLast xs

-- | 03. Find the k-th element of a list. The
--
-- Examples:
--
-- >>> elementAt [1,2,3] 2
-- 2
--
-- >>> elementAt "haskell" 5
-- 'e'
--
-- >>> elementAt [1, 2] 3
-- *** Exception: Out of bounds!
--
-- >>> elementAt [] 1
-- *** Exception: Out of bounds!
--
-- >>> elementAt [1,2,3] (-1)
-- *** Exception: Negative positions not supported!
elementAt :: [a] -> Int -> a
elementAt [] _ = error "Out of bounds!"
elementAt (x:xs) position
  | length (x:xs) < position = error "Out of bounds!"
  | position < 0 = error "Negative positions not supported!"
  | position == 1 = x
  | otherwise = elementAt xs (position - 1)

-- | 04. Find the number of elements of a list
--
-- Examples:
--
-- >>> myLength [123, 456, 789]
-- 3
--
-- >>> myLength "Hello, world!"
-- 13
myLength :: [a] -> Int
myLength = foldr (\ _ -> (+) 1) 0

-- | 05. Reverse a list
--
-- Examples:
--
-- >>> myReverse "A man, a plan, a canal, panama!"
-- "!amanap ,lanac a ,nalp a ,nam A"
--
-- >>> myReverse [1,2,3,4]
-- [4,3,2,1]
myReverse :: [a] -> [a]
myReverse = foldr (\v sofar -> sofar ++ [v]) [] 

-- | 06. Find out whether a list is a palindrome. A palindrome can be read
-- |     forward or backward; e.g. (x a m a x).
--
-- Examples:
--
-- >>> isPalindrome [1,2,3]
-- False
--
-- >>> isPalindrome "madamimadam"
-- True
--
-- >>> isPalindrome [1,2,4,8,16,8,4,2,1]
-- True
isPalindrome :: Eq a => [a] -> Bool
isPalindrome word = isPalindrome' word (reverse word)
  where isPalindrome' :: Eq a => [a] -> [a] -> Bool
        isPalindrome' [] [] = True
        isPalindrome' (x:xs) (y:ys) = x == y && isPalindrome' xs ys

-- | 07. Flatten a nested list structure.
--
-- Examples:
--
-- >>> flatten (Elem 5)
-- [5]
--
-- >>> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
-- [1,2,3,4,5]
--
-- >>> flatten (List [])
-- []
data NestedList a = Elem a | List [NestedList a]

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

-- | 08. Eliminate consecutive duplicates of list elements.
--
-- Examples:
--
-- >>> compress "aaaabccaadeeee"
-- "abcade"
compress :: Eq a => [a] -> [a]
compress = reverse . foldl (\sofar v ->
                             if sofar /= [] && v == head sofar then sofar
                             else v:sofar) []

-- | 09. Pack consecutive duplicates of list elements into sublists.
-- |     If a list contains repeated elements they should be placed in
-- |     separate sublists.
--
-- Examples:
--
-- >>> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e']
-- ["aaaa","b","cc","aa","d","eee"]
pack :: Eq a => [a] -> [[a]]
pack [] = [[]]
pack (x:xs) =
  let packed = pack xs in
  if x `elem` head packed then
    (x:head packed):tail packed
  else
    if [] `elem` packed then [[x]] else [x]:packed

-- | 10. 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.
--
-- Examples:
--
-- >>> encode "aaaabccaadeeee"
-- [(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]
encode :: (Eq a) => [a] -> [(Int, a)]
encode = count . pack

-- | Helper function
--
-- Examples:
--
-- >>> count ["aaa", "b", "cc", "aa"]
-- [(3,'a'),(1,'b'),(2,'c'),(2,'a')]
--
-- >>> count [[]]
-- []
count :: [[a]] -> [(Int, a)]
count = foldr (\v sofar -> if null v then [] else (length v, head v):sofar) []
