[Haskell-cafe] Matroids in Haskell

[Henning Thielemann]

On Fri, 14 Jan 2005, Michael Matsko wrote:

> Dimitri
> 
>      Matriods are generalization of vector spaces.  Basically, they are
> defined by a set of linear dependence axioms and basis exchange
> properties.  Oxley's "Matriod Theory" is the standard reference.  There
> are a multitude of equivalent formulations.

... and the most spectacular result is, that a greedy algorithm for a
problem is optimal if and only if the problem has Matroid structure.