```{- |
Description: Supporting definitions for binary tree problems
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Supporting definitions for binary tree problems.
-}
module Problems.BinaryTrees (
Tree (Empty, Branch),
-- * Support functions
treeSize,
treeHeight,
printTreeList,
) where

import           Control.DeepSeq
import           Data.List       (intercalate, sort)
import           GHC.Generics    (Generic)

-- | A binary tree.
--
-- A 'Tree' of type @a@ consists of either an 'Empty' node,
-- or a 'Branch' containing one value of type @a@ with exactly two subtrees of type @a@.
--
-- === __Notes__
--
-- This is not the problem 54A from the original Ninety-Nine Haskell Problems.
-- As it also mentions, there is nothing to do here except making sure code
-- compiles correctly, thanks to Haskell's strict typing and the way 'Tree'
-- is defined.
--
-- Instead, the problem was replaced by the simple problems of implementing
-- given binary trees as Haskell values.  I.e., turn the examples from
-- the original problem into simple problems to solve.
data Tree a = Empty | Branch a (Tree a) (Tree a)
deriving (Tree a -> Tree a -> Bool
forall a. Eq a => Tree a -> Tree a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Tree a -> Tree a -> Bool
\$c/= :: forall a. Eq a => Tree a -> Tree a -> Bool
== :: Tree a -> Tree a -> Bool
\$c== :: forall a. Eq a => Tree a -> Tree a -> Bool
Eq, Int -> Tree a -> ShowS
forall a. Show a => Int -> Tree a -> ShowS
forall a. Show a => [Tree a] -> ShowS
forall a. Show a => Tree a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Tree a] -> ShowS
\$cshowList :: forall a. Show a => [Tree a] -> ShowS
show :: Tree a -> String
\$cshow :: forall a. Show a => Tree a -> String
showsPrec :: Int -> Tree a -> ShowS
\$cshowsPrec :: forall a. Show a => Int -> Tree a -> ShowS
Show, forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Tree a) x -> Tree a
forall a x. Tree a -> Rep (Tree a) x
\$cto :: forall a x. Rep (Tree a) x -> Tree a
\$cfrom :: forall a x. Tree a -> Rep (Tree a) x
Generic, forall a. NFData a => Tree a -> ()
forall a. (a -> ()) -> NFData a
rnf :: Tree a -> ()
\$crnf :: forall a. NFData a => Tree a -> ()
NFData)

-- | Returns the number of nodes in a binary tree.
treeSize :: Tree a -> Int
treeSize :: forall a. Tree a -> Int
treeSize Tree a
Empty          = Int
0
treeSize (Branch a
_ Tree a
l Tree a
r) = Int
1 forall a. Num a => a -> a -> a
+ forall a. Tree a -> Int
treeSize Tree a
l forall a. Num a => a -> a -> a
+ forall a. Tree a -> Int
treeSize Tree a
r

-- | Returns the height of a binary tree.
treeHeight :: Tree a -> Int
treeHeight :: forall a. Tree a -> Int
treeHeight Tree a
Empty          = Int
0
treeHeight (Branch a
_ Tree a
l Tree a
r) = Int
1 forall a. Num a => a -> a -> a
+ forall a. Ord a => a -> a -> a
max (forall a. Tree a -> Int
treeHeight Tree a
l) (forall a. Tree a -> Int
treeHeight Tree a
r)

-- | An arbitrary total ordering for 'Tree'.
--
-- Defines an order for a set of 'Tree's.  Not intended to support solving problems.
instance Ord a => Ord (Tree a) where
compare :: Tree a -> Tree a -> Ordering
compare Tree a
t Tree a
v = forall a. Ord a => a -> a -> Ordering
compare (forall a. Tree a -> [Bool] -> [([Bool], a)]
encodeTree Tree a
t []) (forall a. Tree a -> [Bool] -> [([Bool], a)]
encodeTree Tree a
v [])

-- | Encodes 'Tree' in a form more obviously ordered,
-- in a way which avoids distinct trees being encoded the same.
encodeTree :: Tree a -> [Bool] -> [([Bool], a)]
encodeTree :: forall a. Tree a -> [Bool] -> [([Bool], a)]
encodeTree Tree a
Empty [Bool]
_ = []
encodeTree (Branch a
x Tree a
left Tree a
right) [Bool]
trail =
[([Bool]
trail, a
x)] forall a. [a] -> [a] -> [a]
++ forall a. Tree a -> [Bool] -> [([Bool], a)]
encodeTree Tree a
left (Bool
False forall a. a -> [a] -> [a]
: [Bool]
trail) forall a. [a] -> [a] -> [a]
++ forall a. Tree a -> [Bool] -> [([Bool], a)]
encodeTree Tree a
right (Bool
True forall a. a -> [a] -> [a]
: [Bool]
trail)

-- | Prints a list of 'Tree's.
--
-- For two lists with the same trees, except for perhaps different order,
-- the output will be the same.
--
-- Not intended to support solving problems.
printTreeList :: (Show a, Ord a) => [Tree a] -> IO ()
printTreeList :: forall a. (Show a, Ord a) => [Tree a] -> IO ()
printTreeList [Tree a]
ts = String -> IO ()
putStrLn forall a b. (a -> b) -> a -> b
\$ String
"[ " forall a. [a] -> [a] -> [a]
++ String
content forall a. [a] -> [a] -> [a]
++ String
" ]"
where content :: String
content = forall a. [a] -> [[a]] -> [a]
intercalate String
"\n, " forall a b. (a -> b) -> a -> b
\$ forall a b. (a -> b) -> [a] -> [b]
map forall a. Show a => a -> String
show (forall a. Ord a => [a] -> [a]
sort [Tree a]
ts)
```