Programming in Haskell, ch6 solutions

06-recursive-functions.hs

-- 1: Define the exponentiation operator ↑ for non-negative integers
-- using the same pattern of recursion as the multiplication operator ∗,
-- and show how 2 ↑ 3 is evaluated using your definition.
power base 0 = 1
power base exponent = base * power base (exponent-1)

-- 3: Without looking at the definitions from the standard prelude in Appendix B,
-- define the following library functions using recursion:
-- • Decide if all logical values in a list are True:
myAnd              :: [Bool] -> Bool
myAnd []           = True
myAnd (False:rest) = False
myAnd (True:rest)  = myAnd rest

-- • Concatenate a list of lists:
myConcat :: [[a]] -> [a]
myConcat []           = []
myConcat (list:lists) = list ++ concat lists

-- • Produce a list with n identical elements:
myReplicate :: Int -> a -> [a]
myReplicate 0 obj = []
myReplicate size obj = obj : myReplicate (size-1) obj

-- • Select the nth element of a list:
myAt :: [a] -> Int -> a
myAt (element:elements) 0 = element
myAt (element:elements) n = myAt elements (n-1)

-- • Decide if a value is an element of a list:
myElem :: Eq a => a -> [a] -> Bool
myElem target [] = False
myElem target (element:elements) | target == element  =  True
                                 | otherwise          =  myElem target elements

-- 4: Define a recursive function merge :: Ord a ⇒ [a] → [a] → [a]
-- that merges two sorted lists to give a single sorted list.
myMerge [] list         = list
myMerge list []         = list
myMerge first@(element1:list1) second@(element2:list2)
  | element1 < element2 = element1 : myMerge list1 second
  | otherwise           = element2 : myMerge first list2

-- 5: Using merge, define a recursive function msort ::Ord a ⇒ [a ] → [a ]
-- that implements merge sort , in which the empty list and lists with one
-- element are already sorted, and any other list is sorted by merging together
-- the two lists that result from sorting the two halves of the list separately.
msort []        = []
msort [element] = [element]
msort list      = myMerge left right
                  where
                    left        = msort $ take middleIndex list
                    right       = msort $ drop middleIndex list
                    middleIndex = (length list) `div` 2

-- 6: define the library functions that calculate the sum of a list of numbers,
-- take a given number of elements from the start of a list,
-- and select the last element of a non-empty list.
mySum [] = 0
mySum (n:ns) = n + mySum ns

myTake 0 _                  = []
myTake n []                 = []
myTake n (element:elements) = element : myTake (n-1) elements

-- probably needs the maybe monad?
myLast (element:[])       = element
myLast (element:elements) = myLast elements