Daily Haskell Exercise: Column Minima in a totally monotone matrix

Daily Haskell Exercise: Column Minima in a totally monotone matrix

Column Minima in a totally monotone matrix

Let type Matrix a = Int->Int->a to denote a matrix. $A=\{a_{i,j}\}$ for $1\leq i\leq n, 1\leq j\leq m$ is a totally monotone matrix is if for all $i < i'$ and $j < j'$, we have $a_{i,j} > a_{i',j} \Rightarrow a_{i,j'} > a_{i',j'}$. We want an algorithm that uses $O(n+m)$ evaluation of the entries of the matrix to find out the row position of each column's minima.

The SMAWK algorithm solves this problem. Here is an video which features the algorithm around 37 minutes into the video. David Eppstein have a python implementation of the algorithm.

Implement columnMinima :: Ord a => Matrix a->Int->Int->[Int], which takes a totally monotone matrix with it's width and height, it find the list of column minima's row position.

Read full article from Daily Haskell Exercise: Column Minima in a totally monotone matrix