Data.RangeMin

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]

To be precise, the implementation this module supplies for sufficiently large n has asymptotics O(n log* n) 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 Ints, and performing 1,000 uniformly distributed range-min queries on each, with +RTS -H128m, consistently takes approximately 6 CPU seconds on a Dell Latitude D630 with dual 2.5GHz Intel Core Duo processors.

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.

Documentation

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

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 -> Ordering

lowestCommonAncestor

Arguments

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

lowestCommonAncestorBy

Arguments

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

lowestCommonAncestorBy'

Arguments

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

rangeMinBy

Arguments

:: (IArray a e, Ix i, Num i, Enum 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, Ix i, Num i, Enum i, Ord e) => a i e -> RangeMin i e

A version of rangeMinBy on elements with their default ordering.

rangeMinByM :: (Monad m, MArray a e m, Ix i, Num i, Enum i) => Comparator e -> a i e -> m (RangeMin i e)

rangeMinM :: (Monad m, MArray a e m, Ix i, Num i, Enum i, Ord e) => a i e -> m (RangeMin i e)

rangeMinBy'

Arguments

:: (Ix i, Num i, Enum 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.

rangeMin'

Arguments

:: (Ix i, Num i, Enum i, Ord e)

=> (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.

A version of rangeMinBy' on elements with their default ordering.