module Exercises.ChapterSix
  ( and
  , concat
  , replicate
  , (!!)
  , elem
  , merge
  , msort
  , sum
  , take
  , last
  ) where

import Prelude
       hiding (and, concat, replicate, (!!), elem, sum, take, last)

and :: [Bool] -> Bool
-- and = foldr (&&) True
and [] = True
and (x:xs) = x && and xs

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

replicate :: Int -> a -> [a]
replicate n x
  | n <= 0 = []
  | otherwise = x : replicate (n - 1) x

(!!) :: [a] -> Int -> a
[] !! _ = error "(!!) called on empty list"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n - 1)

elem
  :: Eq a
  => a -> [a] -> Bool
elem _ [] = False
elem n (x:xs) = (n == x) || elem n xs

-- merge two already sorted lists
merge
  :: Ord a
  => [a] -> [a] -> [a]
merge [] xs = xs
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y = x : merge xs (y : ys)
  | x > y = y : merge (x : xs) ys
merge (_:_) (_:_) = error "can't happen"

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

-- do a merge sort
msort
  :: Ord a
  => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort as) (msort bs)
  where
    (as, bs) = halve xs

sum
  :: Num a
  => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

take :: Int -> [a] -> [a]
take _ [] = []
take n [x]
  | n <= 0 = []
  | otherwise = [x]
take n (x:xs)
  | n <= 0 = []
  | n == 1 = [x]
  | otherwise = x : take (n - 1) xs

last :: [a] -> a
last [x] = x
last (_:xs) = last xs
last [] = error "last called on empty list"
