{- |
Description: Flatten a nested list structure
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P07" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P07 (flatten, flatten') where

import           Problems.Lists

-- | Transform a list, possibly holding lists as elements,
-- into a "flat" list by replacing each list with its elements recursively.
--
-- Recursively flatten lists and concatenate them together.
flatten :: NestedList a -> [a]
flatten :: forall a. NestedList a -> [a]
flatten (Elem a
x)  = [a
x]
flatten (List [NestedList a]
xs) = (NestedList a -> [a]) -> [NestedList a] -> [a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap NestedList a -> [a]
forall a. NestedList a -> [a]
flatten [NestedList a]
xs

-- | Transform a list, possibly holding lists as elements,
-- into a "flat" list by replacing each list with its elements recursively.
--
-- Build the list starting from the last one, prepending each element one at a time.
flatten' :: NestedList a -> [a]
flatten' :: forall a. NestedList a -> [a]
flatten' NestedList a
l = NestedList a -> [a] -> [a]
forall a. NestedList a -> [a] -> [a]
prepend' NestedList a
l []

-- | For each element from front to back, flatten the rest of the list and prepend the element.
prepend' :: NestedList a -> [a] -> [a]
prepend' :: forall a. NestedList a -> [a] -> [a]
prepend' (Elem a
x) [a]
xs      = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs
prepend' (List []) [a]
xs     = [a]
xs
prepend' (List (NestedList a
x:[NestedList a]
xs)) [a]
ys = NestedList a -> [a] -> [a]
forall a. NestedList a -> [a] -> [a]
prepend' NestedList a
x ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ NestedList a -> [a] -> [a]
forall a. NestedList a -> [a] -> [a]
prepend' ([NestedList a] -> NestedList a
forall a. [NestedList a] -> NestedList a
List [NestedList a]
xs) [a]
ys