Copyright | [2016..2017] Trevor L. McDonell |
---|---|

License | BSD3 |

Maintainer | Trevor L. McDonell <tmcdonell@cse.unsw.edu.au> |

Stability | experimental |

Portability | non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell98 |

Combine folds in `Applicative`

style to generate multiple results with
a single pass over the array. Based on Max Rabkin's "Beautiful Folding" [1]
and talks by Gabriel Gonzalez [2].

# Documentation

`Fold`

describes how to process data of some `i`

nput type into some
`o`

utput type, via a reduction using some intermediate Monoid `w`

. For
example, both `sum`

and `length`

below use the `Sum`

monoid:

`>>>`

`let sum = Fold (lift . Sum) (getSum . unlift)`

`>>>`

`let length = Fold (\_ -> 1) (getSum . unlift)`

The key is that `Fold`

s can be combined using `Applicative`

in order to
produce multiple outputs from a *single* reduction of the array. For example:

`>>>`

`let average = (/) <$> sum <*> length`

This computes both the sum of the array as well as its length in a single traversal, then combines both results to compute the average.

Because `Fold`

has some numeric instances, this can also be defined more
succinctly as:

`>>>`

`let average = sum / length`

A more complex example:

`>>>`

`let sumOfSquares = Fold (lift . Sum . (^2)) (getSum . unlift)`

`>>>`

`let standardDeviation = sqrt ((sumOfSquares / length) - (sum / length) ^ 2)`

These will all execute with a single reduction kernel and a single map to summarise (combine) the results.