Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

This module provides folds which try to combine elements in a balanced way. These can be useful for constructing balanced binary trees, or more stable summation.

Adapted from here.

For a strict version see Data.TreeFold.Strict.

- treeFold :: (a -> a -> a) -> a -> [a] -> a
- treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a
- treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a
- treeFoldMapNonEmpty :: (b -> a) -> (a -> a -> a) -> NonEmpty b -> a

# Documentation

`>>>`

data Tree a = Empty | Leaf a | Tree a :*: Tree a deriving Show :}`:{`

treeFold :: (a -> a -> a) -> a -> [a] -> a Source #

Reduces a list of values using a binary operation, trying as much as possible to balance. For instance, given the above binary tree type, the operation:

`>>>`

(Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)`(treeFold (:*:) Empty . map Leaf) [1,2,3,4]`

Will construct a balanced binary tree, whereas the equivalent using a normal fold:

`>>>`

Leaf 1 :*: (Leaf 2 :*: (Leaf 3 :*: (Leaf 4 :*: Empty)))`foldr ((:*:) . Leaf) Empty [1,2,3,4]`

Will construct a right-heavy tree.

`>>>`

((Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)) :*: Leaf 5`(treeFold (:*:) Empty . map Leaf) [1,2,3,4,5]`

Other uses for this function include more stable floating-point summation. The following sum algorithm:

`>>>`

99.0`treeFold (+) 0 (replicate 10 9.9)`

Will have O(log n) error growth for summing n numbers, in comparison to O(n) for:

`>>>`

99.00000000000001`sum (replicate 10 9.9)`

For a strict version of this function see `treeFold`

.

treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a Source #

Perform a tree fold after a map.

`>>>`

(Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)`treeFoldMap Leaf (:*:) Empty [1,2,3,4]`

For a strict version of this function see `treeFoldMap`

.

treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a Source #

Perform a tree fold on a non empty input. For a strict version of this
function see `treeFoldNonEmpty`

.

treeFoldMapNonEmpty :: (b -> a) -> (a -> a -> a) -> NonEmpty b -> a Source #

Perform a tree fold after a map on non-empty input. For a strict version of
this function see `treeFoldMapNonEmpty`

.