28 Jun 2013 23:44

## balanced fold for Data.List

```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.

Also, does this already exist anywhere?  Can it be implemented more
simply in terms of existing machinery? etc.?

-Brent
```
29 Jun 2013 00:04

### Re: balanced fold for Data.List

```
On Fri, 28 Jun 2013, Brent Yorgey wrote:

>
>  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 <at> (_:rs) =
let reduce (z0:z1:zs) = f z0 z1 : reduce zs
reduce zs = zs
```