module Sol7 where

import Data.List
import HL07IAR

-- | 7.38
-- >>>
buildTree :: [a] -> Tr a
buildTree [] = Nil
buildTree xs = T m (buildTree left) (buildTree right)
  where
    (left, m, right) = split xs

-- | 7.39
-- >>>
mapLT :: (a -> b) -> LeafTree a -> LeafTree b
mapLT f (Leaf x) = Leaf (f x)
mapLT f (Node left right) = Node (mapLT f left) (mapLT f right)

-- | 7.40
-- >>>
reflect :: LeafTree a -> LeafTree a
reflect (Leaf x) = Leaf x
reflect (Node left right) = Node (reflect right) (reflect left)

-- | 7.42
-- >>>
mapR :: (a -> b) -> Rose a -> Rose b
mapR f (Bud x) = Bud (f x)
mapR f (Br roses) = Br (map (mapR f) roses)

-- | 7.46
-- >>>
genUnion :: (Eq a) => [[a]] -> [a]
genUnion = foldr union []

genIntersect :: (Eq a) => [[a]] -> [a]
genIntersect = foldr1 intersect

-- | 7.47
-- >>>
insrt :: (Ord a) => a -> [a] -> [a]
insrt x [] = [x]
insrt x (y : ys) = if x <= y then x : y : ys else y : insrt x ys

srt :: (Ord a) => [a] -> [a]
srt = foldr insrt []

-- | 7.51
-- >>>
ln' :: [a] -> Natural
ln' = foldl (\n _ -> S n) Z

-- Skipped questions about Tower of Hanoi