haskell.hs

import Debug.Trace

-- Problem 0
helloWorld :: [Char]
helloWorld = "Hello World"

-- Problem 1
myLast :: [a] -> a
myLast = head . reverse

-- Problem 2
myButLast :: [a] -> a
myButLast = head . tail . reverse

-- Problem 3
elementAt :: [a] -> Int -> a
elementAt []     _ = error "Index past array end"
elementAt (x:_)  0 = x
elementAt (_:xs) i
  | i < 0     = error "Index before array beginning"
  | otherwise = elementAt xs (i-1)

-- Problem 4
myLength :: [a] -> Int
myLength [] = 0
myLength (_:xs) = 1 + myLength xs

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

-- Problem 6
isPalindrome :: Eq a => [a] -> Bool
isPalindrome []     = True
isPalindrome (_:[]) = True
isPalindrome (x:xs)
  | x == (myLast xs) = (isPalindrome . tail . reverse) xs
  | otherwise      = False

-- Problem 7
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
compress :: Eq a => [a] -> [a]
compress [] = []
compress (x:[]) = [x]
compress (x1:x2:xs)
  | x1 == x2  = x1:(compress xs)
  | otherwise = x1:(compress (x2:xs))

-- Problem 9
pack :: Eq a => [a] -> [[a]]
pack = reverse . pack' []

pack' :: Eq a => [[a]] -> [a] -> [[a]]
pack' bins [] = bins
pack' [] (x:xs) = pack' [[x]] xs
pack' (bin:bins) (x:xs)
  | x == head bin = pack' ((x:bin):bins) xs
  | otherwise     = pack' ([x]:bin:bins) xs


-- Problem 10
encode :: Eq a => [a] -> [(a, Int)]
encode = map (encode') . pack

encode' :: [a] -> (a, Int)
encode' (x:xs) = (x, myLength xs + 1)


-- Problem 11
data Encoding a = Single a | Multiple a Int
  deriving Show

encodeModified :: Eq a => [a] -> [Encoding a]
encodeModified = map (encodeModified') . pack

encodeModified' :: [a] -> Encoding a
encodeModified' (x:[]) = Single x
encodeModified' (x:xs) = Multiple x (myLength xs + 1)

-- Problem 12
decodeModified :: [Encoding a] -> [a]
decodeModified xs = foldl (++) [] $ map (decodeEncoding) xs

decodeEncoding :: Encoding a -> [a]
decodeEncoding (Single x) = [x]
decodeEncoding (Multiple x n) = take n $ repeat x


-- Problem 13
encodeDirect :: Eq a => [a] -> [Encoding a]
encodeDirect = reverse . encodeDirect' []

encodeDirect' :: Eq a => [Encoding a] -> [a] -> [Encoding a]
encodeDirect' es [] = es
encodeDirect' [] (x:xs) = encodeDirect' [Single x] xs
encodeDirect' ((Single y):es) (x:xs)
  | x == y    = encodeDirect' ((Multiple x 2):es) xs
  | otherwise = encodeDirect' ((Single x):(Single y):es) xs
encodeDirect' ((Multiple y n):es) (x:xs)
  | x == y    = encodeDirect' ((Multiple y $ n+1):es) xs
  | otherwise = encodeDirect' ((Single x):(Multiple y n):es) xs