This module is designed to implement high-speed versions of the function

rangeMinBy :: (Ix i, IArray a e) => (e -> e -> Ordering) -> a i e -> ((i, i) -> (i, e)) rangeMinBy cmp arr = \r -> minimumBy (\ (i1, e1) (i2, e2) -> cmp e1 e2) [(i, arr ! i) | i <- range r]

for indices that are, in a sense, scalars -- that is, the array is one-dimensional. This restriction is
encapsulated in the simultaneous type restrictions `(`

, which are together aliased
to a typeclass called `Ix`

i, `Num`

i, `Enum`

i)`ScalarIx`

.

To be precise, the implementation this module supplies for sufficiently large n
(lazily) performs `O(n log* n)`

in preprocessing and answers queries in `O(log* n)`

time,
where `log* n`

is defined as

log* n | n <= 2 = 0 | otherwise = 1 + log* (log2 n)

While there is an asymptotically O(n) algorithm, the overhead associated with certain conversions in that algorithm take considerably longer than this implementation for all reasonable n. Note that log* n grows extraordinarily slowly with n: log* n < 5 for n<10^19729.

Using Test.QuickCheck, generating and processing 100 arrays of 20,000 `Int`

s, and performing 1,000
uniformly distributed range-min queries on each, with `+RTS -H512m`

, consistently takes approximately 3.5
CPU seconds on a Dell Latitude D630 with dual 2.5GHz Intel Core Duo processors. (Parallelism is not
currently used by this module, but may be included in a later distribution.)

This module also includes implementations of a lowest-common-ancestor algorithm on trees with identical asymptotics.

Warning: the internal libraries of this module include several nonstandard list fusions. For details, see http://hackage.haskell.org/packages/archive/rangemin/1.0.1/doc/html/src/Data-RangeMin-Internal-HandyList.html.

- type RangeMin i e = (i, i) -> (i, e)
- class (Num i, Enum i, Ix i) => ScalarIx i
- type Comparator e = e -> e -> Ordering
- lowestCommonAncestor :: Ix i => (i, i) -> Tree i -> (i, i) -> i
- lowestCommonAncestorBy :: Ix i => (a -> Maybe i) -> (i, i) -> Tree a -> (a, a) -> a
- lowestCommonAncestorBy' :: Ix i => (a -> Maybe i) -> (i, i) -> Tree a -> (i, i) -> a
- rangeMinBy :: (IArray a e, ScalarIx i) => Comparator e -> a i e -> RangeMin i e
- rangeMin :: (IArray a e, ScalarIx i, Ord e) => a i e -> RangeMin i e
- rangeMinByM :: (Monad m, MArray a e m, ScalarIx i) => Comparator e -> a i e -> m (RangeMin i e)
- rangeMinM :: (Monad m, MArray a e m, ScalarIx i, Ord e) => a i e -> m (RangeMin i e)
- rangeMinBy' :: ScalarIx i => Comparator e -> (i, i) -> [e] -> RangeMin i e
- rangeMin' :: (ScalarIx i, Ord e) => (i, i) -> [e] -> RangeMin i e

# Documentation

type RangeMin i e = (i, i) -> (i, e)Source

The type of a range-min function. Takes as an argument a range of indices and returns the position and value of the smallest element in that range.

type Comparator e = e -> e -> OrderingSource

:: Ix i | |

=> (i, i) | Bounds on node labels. |

-> Tree i | The tree to provide lowest-common-ancestor service for. |

-> (i, i) -> i | A function that takes two node labels and returns the label of their lowest common ancestor. |

Given a tree of indexed nodes, returns a function that takes two nodes and returns their lowest common ancestor.

:: Ix i | |

=> (a -> Maybe i) | An index on tree labels so they can be indexed on an array. Need not account for every node label, hence the Maybe. |

-> (i, i) | Bounds on indices of tree labels. |

-> Tree a | The tree to provide lowest-common-ancestor service for. |

-> (a, a) -> a | Given two node labels, returns the label of their lowest common ancestor. |

Given an indexing function on node labels, returns a function that takes two node labels and returns the label of their lowest common ancestor.

:: Ix i | |

=> (a -> Maybe i) | An index on tree labels, so they can be indexed in an array. Need not account for every node label, hence the Maybe. |

-> (i, i) | Bounds on indices of tree labels. |

-> Tree a | The tree to provide lowest-common-ancestor service for. |

-> (i, i) -> a | Given two indices, return the label of the associated nodes' lowest common ancestor. The behavior of this method is not specified if these indices do not correspond to any trees. |

Given an indexing function on node labels, returns a function that takes two indices and returns the label of the associated nodes' lowest common ancestor.

:: (IArray a e, ScalarIx i) | |

=> Comparator e | A comparator function on elements. |

-> a i e | An array of elements. |

-> RangeMin i e | Given a subrange, returns the index and value at the minimum in that range. |

Given a comparator and an array, returns a function that takes a subrange of the array and
returns the index and value at the minimum in that subrange. *NOT* necessarily faster than `rangeMinBy'`

,
primarily because most of the algorithms used are based upon careful list folding.

rangeMin :: (IArray a e, ScalarIx i, Ord e) => a i e -> RangeMin i eSource

A version of `rangeMinBy`

on elements with their default ordering.

rangeMinByM :: (Monad m, MArray a e m, ScalarIx i) => Comparator e -> a i e -> m (RangeMin i e)Source

:: ScalarIx i | |

=> Comparator e | A comparator function on elements. |

-> (i, i) | Index range. |

-> [e] | List of elements in index order. |

-> RangeMin i e | Given a subrange, returns the index and value at the minimum in that range. |

Given a comparator, an index range and a list of elements in index order, returns a function that takes two indices and returns the index and the value at the minimum value between those two indices inclusive.