On Fri, 28 Jun 2013, Brent Yorgey wrote:
How would people feel about adding a function
foldb :: (a -> a -> a) -> a -> [a] -> a
to Data.List which performs a *balanced* fold of a list? Right now I have this function in the Diagrams.Util module of diagrams-lib but it seems generally useful. Here's a (strawman) implementation:
foldb :: (a -> a -> a) -> a -> [a] -> a foldb _ z [] = z foldb f _ as = foldb' as where foldb' [x] = x foldb' xs = foldb' (go xs) go [] = [] go [x] = [x] go (x1:x2:xs) = f x1 x2 : go xs
I could also stick it in a separate package but it seems silly to have a whole package for such a small function.
For a commutative accumulation function I have an even more balanced fold: foldNested :: (a -> a -> a) -> a -> [a] -> a foldNested _ x [] = x foldNested f _ xs@(_:rs) = let reduce (z0:z1:zs) = f z0 z1 : reduce zs reduce zs = zs ys = xs ++ zipWith (flip const) rs (reduce ys) in last ys