Safe Haskell	None
Language	Haskell2010

Factory.Math.DivideAndConquer

Contents

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.

Synopsis

Types

Type-synonyms

The list-length beneath which to terminate bisection.

Arguments

:: 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; https://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 https://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.

Arguments

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

Arguments

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