99 Haskell Problems (https://wiki.haskell.org/99_questions) as solved and explained by Daniel Dušek

99 Haskell Problems with explanation.hs

-- #1
-- Find the last element of a list
-- Explanation:
-- Last element of one-element list is the element
-- General list last element is discovered by recursively calling myLast over
-- the tail of the list (xs). Once case myLast [x] is hit, we got our last 
-- element.
myLast :: [a] -> a
myLast [x] = x
myLast (x:xs) = myLast(xs)


-- #2
-- Find the last but one element of a list
-- Explanation: 
-- For empty list, error is raised (this is not how you do it in production though)
-- For one element list, error is raised
-- For list with 2+ elements, figure out the length of the list, then access
-- element on length-2th position, using '!!' operator
myButLast :: [a] -> a
myButLast [] = error "Empty list"
myButLast [x] = error "Not enough elements"
myButLast (x:xs) = (x:xs) !! ((length (x:xs))-2)


-- #3
-- Find the K'th element of a list. The first element in the list is number 1.
-- Explanation:
-- Empty list raises error
-- Other lists access k-1th element (remember, k=1 means we want index 0)
-- Again, operator '!!' is used.
kthElem :: [a] -> Int -> a
kthElem [] _ = error "List should not be empty"
kthElem (x:xs) k = (x:xs) !! (k-1)


-- #4
-- Find the number of elements of a list.
-- Explanation:
-- Empty list has length of 0
-- Lists that are not empty will count 1 (head) + length of the tail
-- which is achieved by recursivelly calling myLength on xs (tail of the list) 
myLength :: [a] -> Int
myLength [] = 0
myLength (x:xs) = 1 + myLength(xs)


-- #5
-- Reverse a list
-- Explanation:
-- Reversed empty list is an empty list
-- Reversed one element list is the very same one element list
-- When reversing general list, we recursively call myReverse with tail (xs)
-- as argument, which bubbles-down to one-element list, that is returned, after
-- that, lists are concatenated to one list by '++' operator.
-- Not the most efficient solution, but it works. There is built-in function
-- reverse, that works well.
myReverse :: [a] -> [a]
myReverse [] = []
myReverse [x] = [x]
myReverse (x:xs) = myReverse(xs) ++ [x] 


-- #6
-- Find out whether a list is a palindrome. A palindrome can be read forward
-- or backward; e.g. (x a m a x).
-- Explanation:
-- As stated, palindrome can be read forward or backward, so when we reverse
-- an input list, its reverse should be the same as original list. In that case
-- return true, otherwise, return false
-- Two new concepts are in this example:
-- 1st one: (Eq a) => 
-- To compare two lists, we have to make (explicitly) sure that instance of Eq 
-- which stands for "Equals" is mentioned in type of list. This is done as shown.
-- 2nd one: Guards (|)
-- We do not use equal sign for right side of the fucntion, we use enter and 
-- indentation and pipe (|) sign. Then we list boolean cases that might occur
-- and what should happen when it occurs (after '=')
-- Guards are evaluated in order in which they are written, the 'otherwise' is
-- basically 'True', so it always evaluates and has to be used as the last.
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome [] = False             -- General palindrome definition says no.
isPalindrome list
    | list == myReverse list = True
    | otherwise = False


-- #7 
-- Flatten a nested list structure.
-- Explanation:
-- Firstly, we have to define data type that will be able to hold nested lists
-- since normally, lists in Haskell are homogenous, therefore we use keyword 
-- 'data', first-letter-upper-case type name and type variable 'a' and we have
-- data NestedList a. Then we specify two constructors, first one is 'Elem a'
-- that represents standard list element, the second is List [NestedList a],
-- which says, that Elements of the NestedList constructed via List constru-
-- ctor will contain another NestedList (recursive data type).
--
-- We may then create test input like this:
-- (List [Elem 1, Elem 2, List [ Elem 3], Elem 4, List [ List [ Elem 5 ]]])
--
-- Note that all the values after 'Elem' are of same type - 'a', that's what
-- that type variable is for.
-- Data type is deriving show, so we are able to print the NestedList out.
--
-- Then we create a function declaration that says we will map 'NestedList a' to 
-- a list of 'a'
-- First function definition is pattern-matching case when only 'Elem a' is 
-- present, and in that case, it returns list containing only the 'a' element.
-- Second function definition pattern matches case with 'List xs' and applies
-- foldr function with list concatenation operator (++), starting with empty
-- list, over results of mapping recursivelly myFlatten funciton on the rest
-- of the list. What that basically does is nesting as long as possible, until
-- 'Elem a' type records are reached, returned back as list of 'a', and this is
-- then joined via foldr function.
--
-- Since foldr and map are function that you should understand deeply, here are
-- links for reference:
-- https://wiki.haskell.org/Fold
-- http://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html#v:map
data NestedList a = Elem a | List [NestedList a] 
    deriving Show

myFlatten :: NestedList a -> [a]
myFlatten (Elem a) = [a]
myFlatten (List xs) = foldr (++) [] $ map myFlatten xs 


-- #8 
-- Eliminate consecutive duplicates of list elements.
-- Explanation:
-- Again, function declaration tells us that type variable 'a' has instance
-- of 'Equals' on it, and that we map a list of 'a's to list of 'a's.
-- We define base cases [] = [], [x] = [x]
-- Then we pattern match list so we get first, second and the tail
-- Using guards we figure out whether first == second, if so, we 
-- recursively call myCompress on the tail again
-- otherwise, we only concatenate the first, 
myCompress :: (Eq a) => [a] -> [a]
myCompress [] = []
myCompress [x] = [x]
myCompress (x1:x2:xs) 
    | x1 == x2 = myCompress (x2:xs)
    | otherwise = [x1] ++ myCompress (x2:xs)


-- #9
-- Pack consecutive duplicates of list elements into sublists. If a list 
-- contains repeated elements they should be placed in separate sublists.
-- Explanation:
-- Declaration says we can use equals relation on list elements and that 
-- we map list of certain type to list of lists of certain type
-- Initial mapping saying that [] = []
-- Then we prepend 'x' to list generated by takeWhile function (as long
-- as element of 'xs' is equal to 'x' (==x), generate list). This list is
-- then packed with other lists that origins from recursive myPack calls
-- over the remainder of the list (function dropWhile is throwing every-
-- this away, until the first element is not equal to 'x', simply said,
-- it skips everything that we already packed in takeWhile part of code).
-- 
-- takeWhile and dropWhile are important function, links for reference:
-- http://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html#v:takeWhile
-- http://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html#v:dropWhile
myPack :: (Eq a) => [a] -> [[a]]
myPack [] = []
myPack (x:xs) = ( x : takeWhile (==x) xs ) : myPack (dropWhile (==x) xs)


-- #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.
-- Explanation:
-- Declaration states that on 'a' can be used Equals relation, and that we will
-- map list of 'a' to tuples of Int and 'a'
-- Encoding of an empty list will return empty list (which si by declaration 
-- pretty much possible)
-- Encoding of general list will construct a tuple (most-outer parentheses), 
-- where first tuple element will be length of prefix where elements equal to
-- 'x' preppended to list of other tuples that are generated by recursive call
-- to myEncode. On the very end, the myEncode [] is called which finally creates
-- a list.
-- Again in recursive call, dropWhile is used to catch up with what has already
-- been processed.
--
-- It goes something like this
-- aaabbcc => (3, 'a') : (2, 'b') : (2,'c') : []
-- Which evaluates to [(3, 'a'), (2, 'b'), (2,'c')]
myEncode :: (Eq a) => [a] -> [(Int, a)]
myEncode [] = []
myEncode (x:xs) =   ((length $ takeWhile (==x) (x:xs)), x) 
                    : myEncode (dropWhile (==x) (x:xs))

-- TO BE CONTINUED