smawk-0: Linear time row minima for totally monotone matrices

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

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.