| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Smawk
Description
This module implements a generalized version of the SMAWK algorithm for computing row minima in totally ordered matrices.
I do not require rows or column numbers to be actual numbers, or even ordered, instead comparing columns using occurrence order.
Unlike Map-based implementations, the runtime of this is actually linear.
Synopsis
- smawk :: (Traversable f, Foldable g, Ord a) => f r -> g c -> (r -> c -> a) -> Maybe (f c)
- smawk1 :: (Traversable f, Foldable1 g, Ord a) => f r -> g c -> (r -> c -> a) -> f c
Documentation
Arguments
| :: (Traversable f, Foldable g, Ord a) | |
| => f r | rows (in any desired ascending order) |
| -> g c | columns (in any desired ascending order) |
| -> (r -> c -> a) | a monotone matrix |
| -> Maybe (f c) | each of the row minima |
O(|rows| + |cols|).
Computes row minima in totally monotone matrices using the SMAWK algorithm.
Returns Nothing if we have no columns.
Arguments
| :: (Traversable f, Foldable1 g, Ord a) | |
| => f r | rows (in any desired ascending order) |
| -> g c | columns (in any desired ascending order) |
| -> (r -> c -> a) | a monotone matrix |
| -> f c | each of the row minima |
O(|rows| + |cols|).
Computes row minima in totally monotone matrices using the SMAWK algorithm.