{- |
Description: Post-order sequence of a tree
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

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

import           Problems.MultiwayTrees

-- | Construct the post-order sequence of the tree nodes.
postOrderSequence :: MultiwayTree a -> [a]
postOrderSequence :: forall a. MultiwayTree a -> [a]
postOrderSequence MultiwayTree a
t = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ MultiwayTree a -> [a] -> [a]
forall a. MultiwayTree a -> [a] -> [a]
addToList MultiwayTree a
t []

-- | Add each node once to a list in post-order sequence.
-- List will end up as reverse post-order sequence.
addToList :: MultiwayTree a -> [a] -> [a]
addToList :: forall a. MultiwayTree a -> [a] -> [a]
addToList (MultiwayTree a
x [MultiwayTree a]
ts) [a]
xs = a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs'
  where xs' :: [a]
xs' = [MultiwayTree a] -> [a] -> [a]
forall a. [MultiwayTree a] -> [a] -> [a]
addToList' [MultiwayTree a]
ts [a]
xs

addToList' :: [MultiwayTree a] -> [a] -> [a]
addToList' :: forall a. [MultiwayTree a] -> [a] -> [a]
addToList' [] [a]
xs = [a]
xs
addToList' (MultiwayTree a
t:[MultiwayTree a]
ts) [a]
xs = [MultiwayTree a] -> [a] -> [a]
forall a. [MultiwayTree a] -> [a] -> [a]
addToList' [MultiwayTree a]
ts [a]
xs'
  where xs' :: [a]
xs' = MultiwayTree a -> [a] -> [a]
forall a. MultiwayTree a -> [a] -> [a]
addToList MultiwayTree a
t [a]
xs