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

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

import           Problems.BinaryTrees
import qualified Solutions.P57        as Solution

-- $setup
-- >>> import Problems.BinaryTrees
-- >>> import Problems.P56

-- | Write an 'addedTo' function which adds an element to
-- a [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree)
-- to obtain another binary search tree.
-- Use this function to construct a binary search tree from a list of ordered elements.
-- Each element should be added from the front to the back of the list.
--
-- === Examples
--
-- >>> construct [3, 2, 5, 7, 1]
-- Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty))
--
-- >>> symmetric . construct $ [5, 3, 18, 1, 4, 12, 21]
-- True
--
-- >>> symmetric . construct $ [3, 2, 5, 7, 1]
-- True
--
-- === __Notes__
--
-- The original problem refers to a predicate which had not appeared in previous
-- problems: /Use the predicate add\/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers./
-- This is presumably a reference to course material used at the time the problems were written.
-- Given the different context, the problem was revised to also implement the function that would
-- have taken the role that the @add\/3@ predicate would have had in the original context.
--
-- For consistent examples, the condition to also use naive binary search tree insertion was imposed.
-- For the same reason, the order for which elements in a list are added to the tree is also specified.
-- Of course, anyone is free to implement whatever they want, although that could mean they would not pass the available tests.
construct :: Ord a => [a] -> Tree a
construct :: forall a. Ord a => [a] -> Tree a
construct = [a] -> Tree a
forall a. Ord a => [a] -> Tree a
Solution.construct

-- | Return a binary search tree with an element added to another binary search tree.
--
-- Use a simple insertion algorithm which leaves the tree mostly the same except
-- for the new element in a leaf node.  In particular, no balancing should be done.
--
-- === Examples
--
-- >>> 8 `addedTo` Branch 5 Empty (Branch 7 Empty (Branch 9 Empty Empty))
-- Branch 5 Empty (Branch 7 Empty (Branch 9 (Branch 8 Empty Empty) Empty))
addedTo :: Ord a => a -> Tree a -> Tree a
addedTo :: forall a. Ord a => a -> Tree a -> Tree a
addedTo = a -> Tree a -> Tree a
forall a. Ord a => a -> Tree a -> Tree a
Solution.addedTo