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

Language | Haskell98 |

`AUTHOR`

- Dr. Alistair Ward
`DESCRIPTION`

- Provides a polymorphic algorithm, to
*unfold*a list into a tree, to which an*associative binary operator*is then applied to re-*fold*the tree to a*scalar*. - Implementations of this strategy have been provided for
*addition*and*multiplication*, though other associative binary operators, like`gcd`

or`lcm`

could also be used. - Where the contents of the list are consecutive, a more efficient implementation is available in
*Factory.Data.Interval*.

- type BisectionRatio = Ratio Int
- type MinLength = Int
- divideAndConquer :: Monoid monoid => BisectionRatio -> MinLength -> [monoid] -> monoid
- product' :: Num n => BisectionRatio -> MinLength -> [n] -> n
- sum' :: Num n => BisectionRatio -> MinLength -> [n] -> n

# Types

## Type-synonyms

type BisectionRatio = Ratio Int Source

- The ratio of the original list-length at which to bisect.
- CAVEAT: the value can overflow.

# Functions

:: Monoid monoid | |

=> BisectionRatio | The ratio of the original list-length at which to bisect. |

-> MinLength | For efficiency, the list will not be bisected, when it's length has been reduced to this value. |

-> [monoid] | The list on which to operate. |

-> monoid | The resulting scalar. |

- Reduces a list to a single scalar encapsulated in a
`Monoid`

, using a*divide-and-conquer*strategy, bisecting the list and recursively evaluating each part; http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm. - By choosing a
`bisectionRatio`

other than`(1 % 2)`

, the bisection can be made asymmetrical. The specified ratio represents the length of the left-hand portion, over the original list-length; eg.`(1 % 3)`

results in the first part, half the length of the second. - This process of recursive bisection, is terminated beneath the specified minimum list-length,
after which the
*monoid*'s binary operator is directly*folded*over the list. - One can view this as a http://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29,
in which the list is exploded into a binary tree-structure
(each leaf of which contains a list of up to
`minLength`

integers, and each node of which contains an associative binary operator), and then collapsed to a scalar, by application of the operators.

:: Num n | |

=> BisectionRatio | The ratio of the original list-length at which to bisect. |

-> MinLength | For efficiency, the list will not be bisected, when it's length has been reduced to this value. |

-> [n] | The numbers whose product is required. |

-> n | The resulting product. |

- Multiplies the specified list of numbers.
- Since the result can be large,
`divideAndConquer`

is used in an attempt to form operands of a similar order of magnitude, which creates scope for the use of more efficient multiplication-algorithms.

:: Num n | |

=> BisectionRatio | The ratio of the original list-length at which to bisect. |

-> MinLength | For efficiency, the list will not be bisected, when it's length has been reduced to this value. |

-> [n] | The numbers whose sum is required. |

-> n | The resulting sum. |

- Sums the specified list of numbers.
- Since the result can be large,
`divideAndConquer`

is used in an attempt to form operands of a similar order of magnitude, which creates scope for the use of more efficient multiplication-algorithms.*Multiplication*is required for the*addition*of`Rational`

numbers by cross-multiplication; this function is unlikely to be useful for other numbers.