import Data.Maybe (fromMaybe)

notThe :: String -> Maybe String
notThe "the" = Nothing
notThe s = Just s

replaceThe :: String -> String
replaceThe "" = ""
replaceThe (' ':s) = ' ':replaceThe s
replaceThe s =
    let
        (word, words) = span(/=' ') s
        head = fromMaybe "a" $ notThe word
    in
        head ++ (replaceThe words)

vowels = "aeuioy"
isVowel :: Char -> Bool
isVowel = flip elem vowels

countTheBeforeVowel :: String -> Integer
countTheBeforeVowel (' ':s) = countTheBeforeVowel s
countTheBeforeVowel "" = 0
countTheBeforeVowel s =
    let
        (word, words) = span(/=' ') s
        headCount = case (word, words) of
            ("the", (' ':a:_)) | isVowel a-> 1
            _ -> 0
    in
        headCount + (countTheBeforeVowel words)


countVowels :: String -> Integer
countVowels = toInteger . length . filter isVowel

newtype Word' = Word' String deriving (Eq, Show)

mkWord :: String -> Maybe Word'
mkWord s = if numVowels > numConsonants then Nothing else Just $ Word' s
    where
        numVowels = countVowels s
        numConsonants = (toInteger $ length s) - numVowels

data Nat = Zero | Succ Nat deriving (Eq, Show)

natToInteger :: Nat -> Integer
natToInteger Zero = 0
natToInteger (Succ n) = 1 + (natToInteger n)

integerToNat :: Integer -> Maybe Nat
integerToNat 0 = Just Zero
integerToNat n | n > 0 =  integerToNat (n - 1) >>= Just . Succ
integerToNat _ = Nothing

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust Nothing = False

isNothing :: Maybe a -> Bool
isNothing = not . isJust

maybbee :: b -> (a -> b) -> Maybe a -> b
maybbee _ f (Just a) = f a
maybbee b _ Nothing = b

listToMaybe :: [a] -> Maybe a
listToMaybe (h:_) = Just h
listToMaybe [] = Nothing

maybeToList :: Maybe a -> [a]
maybeToList (Just h) = [h]
maybeToList Nothing = []

catMaybes :: [Maybe a] -> [a]
catMaybes [] = []
catMaybes (Just x:xs) = x:catMaybes xs
catMaybes (Nothing:xs) = catMaybes xs

flipMaybe :: [Maybe a] -> Maybe [a]
flipMaybe [] = Just []
flipMaybe (Nothing:_) = Nothing
flipMaybe ((Just x):xs)= (flipMaybe xs) >>=  Just . (x:)



eitherLeftToList :: Either a b -> [a]
eitherLeftToList (Left a) = [a]
eitherLeftToList (Right _) = []

reverseEither :: Either a b -> Either b a
reverseEither (Left a) = Right a
reverseEither (Right a) = Left a

lefts' :: [Either a b] -> [a]
lefts' l = foldr (\e l-> (eitherLeftToList e) ++ l) [] l

rights' :: [Either a b] -> [b]
rights' = lefts' . map reverseEither

either' :: (a -> c) -> (b -> c) -> Either a b -> c
either' lf _ (Left l) = lf l
either' _ rf (Right r) = rf r

eitherMaybe'' :: (b -> c) -> Either a b -> Maybe c
eitherMaybe'' f = either' (const Nothing) (Just . f)

myIterate :: (a -> a) -> a -> [a]
myIterate f start = start:myIterate f (f start)

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
myUnfoldr f start = case f start of
    Nothing -> []
    Just (elem, newStart) -> elem:(myUnfoldr f newStart)

betterIterate :: (a -> a) -> a -> [a]
betterIterate f = myUnfoldr (\e -> Just (f e, f e))

data BinaryTree a = Leaf | Node (BinaryTree a) a (BinaryTree a) deriving Show

unfold :: (a -> Maybe (a, b, a)) -> a -> BinaryTree b
unfold f start = case f start of
    Nothing -> Leaf
    Just (ls, r, rs) -> Node (unfold f ls) r (unfold f rs)

treeBuild :: Integer -> BinaryTree Integer
treeBuild n = unfold (\n' -> if n == n' then Nothing else Just (n' + 1, n' , n' + 1)) 0