module MoreTrees exposing (..) type Tree a = Empty | Node a (Tree a) (Tree a) height t = case t of Empty -> 0 Node _ t1 t2 -> 1 + max (height t1) (height t2) ------------------------------------------------------------------------------ isFull tree = let h = height tree foo depth subtree = if depth == h {- && subtree == Empty -} then True else case subtree of Empty -> False Node _ t1 t2 -> foo (depth+1) t1 && foo (depth+1) t2 in foo 0 tree ------------------------------------------------------------------------------ isFullTree : Tree a -> Bool isFullTree t = case maybeFullTreeHeight t of Just _ -> True Nothing -> False maybeFullTreeHeight : Tree a -> Maybe Int maybeFullTreeHeight t = case t of Empty -> Just 0 Node _ left right -> maybeFullTreeHeight left |> maybeAndThen (\h1 -> maybeFullTreeHeight right |> maybeAndThen (\h2 -> maybeGuard (h1 == h2) |> maybeAndThen (\() -> maybePure (1 + h1) ))) {- case maybeFullTreeHeight left of Nothing -> Nothing Just h1 -> case maybeFullTreeHeight right of Nothing -> Nothing Just h2 -> if h1 == h2 then Just (1 + h1) else Nothing -} ------------------------------------------------------------------------------ maybeAndThen : (a -> Maybe b) -> Maybe a -> Maybe b maybeAndThen f mx = case mx of Nothing -> Nothing Just x -> f x maybePure : a -> Maybe a maybePure x = Just x maybeGuard : Bool -> Maybe () maybeGuard b = if b then Just () else Nothing