-- Break the Loop. Part 4. All examples in one file.
-- Uncomment the desired main call and run.

-- ============================================================
-- Optional type (introduced in Part 2)
-- ============================================================

data Optional a = Empty | Result a deriving (Show)

-- ============================================================
-- Tree type (introduced in Part 3)
-- ============================================================

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = Node x EmptyTree EmptyTree
treeInsert x (Node val left right)
    | x == val = Node val left right
    | x < val  = Node val (treeInsert x left) right
    | x > val  = Node val left (treeInsert x right)

listToTree :: (Ord a) => [a] -> Tree a
listToTree []     = EmptyTree
listToTree (x:xs) = treeInsert x (listToTree xs)

-- Task 11
printTree :: (Show a) => Tree a -> Int -> IO ()
printTree EmptyTree _depth = return ()                             -- empty tree — empty action
printTree (Node val left right) depth = do
    printTree right (depth + 1)                                    -- right subtree — goes up
    putStrLn (replicate (depth * 4) ' ' ++ show val)               -- current node with indent
    printTree left  (depth + 1)                                    -- left subtree — goes down

-- Task 12
treeToList :: Tree a -> [a]
treeToList EmptyTree = []                                          -- empty tree — empty list
treeToList (Node val left right) =
    treeToList left ++ [val] ++ treeToList right                   -- smaller on the left, node, larger on the right

-- Task 13
myZip :: [a] -> [b] -> [(a, b)]
myZip [] _           = []                                          -- first list empty — stop
myZip _ []           = []                                          -- second list empty — stop
myZip (x:xs) (y:ys)  = (x, y) : myZip xs ys                      -- pair the heads, recurse on tails

myZipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
myZipWith _ [] _          = []                                     -- first list empty — stop
myZipWith _ _ []          = []                                     -- second list empty — stop
myZipWith f (x:xs) (y:ys) = f x y : myZipWith f xs ys             -- apply f to heads, recurse on tails

numbers :: [Int]
numbers = [2, 3, 4, 5, 1]

names :: [String]
names = ["Britannia", "Gallia", "Hispania", "Italia", "Aegyptus"]

provinces :: [(Int, String)]
provinces = myZip numbers names

-- Task 14
lookupProvince :: Int -> [(Int, String)] -> Optional String
lookupProvince _ []                 = Empty                        -- list exhausted — province not found
lookupProvince n ((num, name):rest)
    | n == num  = Result name                                      -- match — return the name
    | otherwise = lookupProvince n rest                            -- no match — keep searching

andThen :: Optional a -> (a -> Optional b) -> Optional b
andThen Empty      _ = Empty                                       -- box is empty — emptiness propagates
andThen (Result x) f = f x                                         -- there's a value — pass it to the next function

-- Task 15
myTail :: [a] -> [a]
myTail []     = error "myTail: empty list"                         -- empty list — error
myTail (_:xs) = xs                                                 -- drop the head, return the tail

myAdd :: Int -> Int -> Int
myAdd x y = x + y

fibs :: [Int]
fibs = 1 : 1 : myZipWith myAdd fibs (myTail fibs)                 -- the sequence defines itself

myTake :: Int -> [a] -> [a]
myTake n _      | n <= 0 = []                                      -- taken enough — stop
myTake _ []              = []                                      -- list exhausted — stop
myTake n (x:xs)          = x : myTake (n - 1) xs                  -- take the head, recurse on the tail

-- ============================================================
-- Function sumList (introduced in Part 1)
-- ============================================================

sumList :: Num a => [a] -> a                                       -- function: list of numbers → number (sum)
sumList []     = 0                                                 -- base case: empty list → 0
sumList (x:xs) = x + sumList xs                                    -- head + result for the tail

-- Run examples. Uncomment the desired main call.

main :: IO ()
main = runPrintTree
-- main = runTreeToList
-- main = runProvinces
-- main = runLookup
-- main = runFibs

runPrintTree :: IO ()
runPrintTree = do
    putStrLn "=== Task 11: pretty-print a tree ==="
    printTree (listToTree [3, 5, 3, 1, 4, 1, 2, 2]) 0

runTreeToList :: IO ()
runTreeToList = do
    putStrLn "=== Task 12: tree to sorted list ==="
    print (treeToList (listToTree [3, 5, 3, 1, 4, 1, 2, 2]))

runProvinces :: IO ()
runProvinces = do
    putStrLn "=== Task 13: province dictionary ==="
    print provinces

runLookup :: IO ()
runLookup = do
    putStrLn "=== Task 14: lookup by province number ==="
    print (lookupProvince 3 provinces)   -- Result "Hispania"
    print (lookupProvince 7 provinces)   -- Empty

runFibs :: IO ()
runFibs = do
    putStrLn "=== Task 15: first 20 Fibonacci numbers ==="
    print (myTake 20 fibs)
    putStrLn "=== Task 15: sum of first 20 Fibonacci numbers ==="
    print (sumList (myTake 20 fibs))