module Ch6 (
  (^!),
  myand, myconcat, myreplicate2, (!!!), myelem,
  merge,
  msort,
  mysum, mytake, mylast,
) where

-- 1.
(^!) :: Int -> Int -> Int
m ^! 0 = 1
m ^! n= m * (m ^! (n-1))

-- 2.
{-
length [1, 2, 3]
  = 1 + (length [2, 3])
  = 1 + (1 + (length [3]))
  = 1 + (1 + (1 + length []))
  = 1 + (1 + (1 + 0))
  = 3

drop 3 [1, 2, 3, 4, 5]
  = drop 2 [2, 3, 4, 5]
  = drop 1 [3, 4, 5]
  = drop 0 [4, 5]
  = [4, 5]

init [1, 2, 3]
  = 1 : init [2, 3]
  = 1 : 2 : init [3]
  = 1 : 2 : []
  = [1, 2]
-}

-- 3.
myand :: [Bool] -> Bool
myand [] = True
myand (x:xs) | x = myand xs
             | otherwise = False

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

myreplicate2 :: Int -> a -> [a]
myreplicate2 0 x = []
myreplicate2 n x = x : myreplicate2 (n-1) x

(!!!) :: [a] -> Int -> a
(x:xs) !!! 0 = x
(x:xs) !!! n = xs !!! (n-1)

myelem :: Eq a => a -> [a] -> Bool
myelem v [] = False
myelem v (x:xs) | v == x = True
              | otherwise = myelem v xs

-- 4.
merge :: Ord a => [a] -> [a] -> [a]
merge x [] = x
merge [] y = y
merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys

-- 5.
halve :: [a] -> ([a], [a])
halve xs = splitAt n xs
  where n = length xs `div` 2

msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort ms) (msort ns)
  where (ms, ns) = halve xs

-- 6.
mysum :: Num a => [a] -> a
-- mysum [] = 0
-- mysum (x:xs) = x + mysum xs
mysum xs = foldr (+) 0 xs

mytake :: Int -> [a] -> [a]
mytake 0 _ = []
mytake n [] = []
mytake n (x:xs) = x : mytake (n-1) xs

mylast :: [a] -> a
mylast [x] = x
mylast (_:xs) = mylast xs
