{- |
Description: Binary search trees
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P57" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P57 (construct, addedTo) where

import           Problems.BinaryTrees

-- | Construct a binary search tree from a list of ordered elements.
construct :: Ord a => [a] -> Tree a
construct :: forall a. Ord a => [a] -> Tree a
construct [a]
l = [a] -> Tree a -> Tree a
forall {a}. Ord a => [a] -> Tree a -> Tree a
build [a]
l Tree a
forall a. Tree a
Empty
  where build :: [a] -> Tree a -> Tree a
build [] Tree a
tree     = Tree a
tree
        build (a
x:[a]
xs) Tree a
tree = [a] -> Tree a -> Tree a
build [a]
xs (a
x a -> Tree a -> Tree a
forall a. Ord a => a -> Tree a -> Tree a
`addedTo` Tree a
tree)

-- | Return a binary search tree with an element added to another binary search tree.
addedTo :: Ord a => a -> Tree a -> Tree a
addedTo :: forall a. Ord a => a -> Tree a -> Tree a
addedTo a
x Tree a
Empty                 = a -> Tree a -> Tree a -> Tree a
forall a. a -> Tree a -> Tree a -> Tree a
Branch a
x Tree a
forall a. Tree a
Empty Tree a
forall a. Tree a
Empty
addedTo a
x (Branch a
y Tree a
left Tree a
right)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y = a -> Tree a -> Tree a -> Tree a
forall a. a -> Tree a -> Tree a -> Tree a
Branch a
y (a
x a -> Tree a -> Tree a
forall a. Ord a => a -> Tree a -> Tree a
`addedTo` Tree a
left) Tree a
right
  | Bool
otherwise = a -> Tree a -> Tree a -> Tree a
forall a. a -> Tree a -> Tree a -> Tree a
Branch a
y Tree a
left (a
x a -> Tree a -> Tree a
forall a. Ord a => a -> Tree a -> Tree a
`addedTo` Tree a
right)