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

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

import           Problems.MultiwayTrees

-- | Determine the internal path length of a tree.
--
-- We define the internal path length of a multiway tree as
-- the total sum of the path lengths from the root to all nodes of the tree.
-- By this definition, 'multitree5' has an internal path length of 9.
internalPathLength :: MultiwayTree a -> Int
internalPathLength :: forall a. MultiwayTree a -> Int
internalPathLength = Int -> MultiwayTree a -> Int
forall a. Int -> MultiwayTree a -> Int
internalPathLength' Int
0

internalPathLength' :: Int -> MultiwayTree a -> Int
internalPathLength' :: forall a. Int -> MultiwayTree a -> Int
internalPathLength' Int
l (MultiwayTree a
_ []) = Int
l
internalPathLength' Int
l (MultiwayTree a
_ [MultiwayTree a]
ts) = Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int
l (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Int] -> Int) -> [Int] -> Int
forall a b. (a -> b) -> a -> b
$ (MultiwayTree a -> Int) -> [MultiwayTree a] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int -> MultiwayTree a -> Int
forall a. Int -> MultiwayTree a -> Int
internalPathLength' (Int -> MultiwayTree a -> Int) -> Int -> MultiwayTree a -> Int
forall a b. (a -> b) -> a -> b
$ Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) [MultiwayTree a]
ts