module Data.TreeFold.Strict where
import Data.List.NonEmpty (NonEmpty(..))
treeFold :: (a -> a -> a) -> a -> [a] -> a
treeFold _ z [] = z
treeFold f _ (x:xs) = treeFoldNonEmpty f (x :| xs)
treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a
treeFoldMap _ _ z [] = z
treeFoldMap c f _ (x:xs) = treeFoldMapNonEmpty c f (x :| xs)
treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a
treeFoldNonEmpty f = go
where
go (x :| []) = x
go (x :| y:rest) =
let z = f x y
in z `seq` go (z :| pairFold rest)
pairFold (x:y:rest) =
let z = f x y
in z `seq` (z : pairFold rest)
pairFold xs = xs
treeFoldMapNonEmpty :: (b -> a) -> (a -> a -> a) -> NonEmpty b -> a
treeFoldMapNonEmpty c f = go
where
go (x :| []) = c x
go (a :| b:l) =
let z = f (c a) (c b)
in z `seq` treeFoldNonEmpty f (z :| pairFoldMap l)
pairFoldMap (x:y:rest) =
let z = f (c x) (c y)
in z `seq` (z : pairFoldMap rest)
pairFoldMap [] = []
pairFoldMap [x] =
let z = c x
in z `seq` [z]