[Haskell-cafe] Solving integer equations in Haskell

Arie Peterson ariep at xs4all.nl
Mon Oct 15 17:29:20 CEST 2012

> Can anyone suggest a library written in Haskell which can solve equations of
> the form xM(transpose(x)) = y, where x should be an integer vector, M is an
> integer matrix and y is an integer? I'm aware that Mathematica can do this,
> but I would like something written in Haskell. I haven't been sure of what
> exact keywords I should be searching for, hence my asking here.

You may interpret the function x ↦ x M transpose(x) as a quadratic form on the 
additive group of vectors. The group of integer vectors, together with such a 
quadratic form, is usually called a /lattice/ (not to be confused with its 
other meaning, of a set with a partial order and some meet/join operators).

A vector x satisfying your equation is sometimes said to /represent/ the 
number y, with respect to the quadratic form.

On hackage, a quick search gives the "Lattices" package, which seems related. 
(There is also the "lattices" package, but this is about the other lattices.)

Incidentally, I also have use for this functionality, but specifically for 
vectors with 2 components (so the quadratic form is then binary). The equation 
is then a generalised Pell equation, and I think I have read somewhere how to 
solve it. If such code does not exist yet, I will probably write it, but this 
might not be very soon.



More information about the Haskell-Cafe mailing list