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

Some solutions to "Problems.P59" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P59 (heightBalancedTrees) where

import           Problems.BinaryTrees

-- | Construct a list of all height-balanced binary trees with the given maximum height.
heightBalancedTrees :: Int -> [Tree ()]
heightBalancedTrees :: Int -> [Tree ()]
heightBalancedTrees Int
0 = [Tree ()
forall a. Tree a
Empty]
heightBalancedTrees Int
1 = [() -> Tree () -> Tree () -> Tree ()
forall a. a -> Tree a -> Tree a -> Tree a
Branch () Tree ()
forall a. Tree a
Empty Tree ()
forall a. Tree a
Empty]
heightBalancedTrees Int
n =
  [Tree ()] -> [Tree ()] -> [Tree ()]
combine (Int -> [Tree ()]
heightBalancedTrees (Int -> [Tree ()]) -> Int -> [Tree ()]
forall a b. (a -> b) -> a -> b
$ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int -> [Tree ()]
heightBalancedTrees (Int -> [Tree ()]) -> Int -> [Tree ()]
forall a b. (a -> b) -> a -> b
$ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) [Tree ()] -> [Tree ()] -> [Tree ()]
forall a. [a] -> [a] -> [a]
++
  [Tree ()] -> [Tree ()] -> [Tree ()]
combine (Int -> [Tree ()]
heightBalancedTrees (Int -> [Tree ()]) -> Int -> [Tree ()]
forall a b. (a -> b) -> a -> b
$ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int -> [Tree ()]
heightBalancedTrees (Int -> [Tree ()]) -> Int -> [Tree ()]
forall a b. (a -> b) -> a -> b
$ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2) [Tree ()] -> [Tree ()] -> [Tree ()]
forall a. [a] -> [a] -> [a]
++
  [Tree ()] -> [Tree ()] -> [Tree ()]
combine (Int -> [Tree ()]
heightBalancedTrees (Int -> [Tree ()]) -> Int -> [Tree ()]
forall a b. (a -> b) -> a -> b
$ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2) (Int -> [Tree ()]
heightBalancedTrees (Int -> [Tree ()]) -> Int -> [Tree ()]
forall a b. (a -> b) -> a -> b
$ Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

combine :: [Tree ()] -> [Tree ()] -> [Tree ()]
combine :: [Tree ()] -> [Tree ()] -> [Tree ()]
combine [Tree ()]
ls [Tree ()]
rs = [() -> Tree () -> Tree () -> Tree ()
forall a. a -> Tree a -> Tree a -> Tree a
Branch () Tree ()
l Tree ()
r | Tree ()
l <- [Tree ()]
ls, Tree ()
r <- [Tree ()]
rs]