Posts tagged ‘Haskell’

Operads in Haskell

Mikael Vejdemo Johansson, who was at the Operads conference in Luminy (which I also attended), wrote in only one week a Haskell module computing Gröbner bases for operads. Nice work !


11 May 2009 at 8:25 pm Leave a comment

Computing Gröbner bases in Haskell

I wrote a small package to compute Gröbner bases in Haskell with the Buchberger algorithm (with applications to variable elimination). Performance is quite bad compared to specialised software like Macaulay, but it seems to work ! I put a Cabal package here. Maybe I’ll add several functions afterwards.

A testcase :
import Data.Polynomial
import Data.Ring
import Algebra.GroebnerBasis
import Algebra.Elimination
type R = Polynom QQ VarXYZ
[x,y,z,t,u,v] = map returnp [X,Y,Z,T,U,V] :: [R]
-- projection from a point on the intersection of quadrics
main = do
print $ step_eliminate [T] $ MakeIdeal
[x^2 - 3*y*z + z*t + 2*x*t,
z^2 + 5*y^2 + z*x - 2*t*z]

The output should be :

20 March 2009 at 7:47 pm Leave a comment

Monads in mathematics 3 : monads from adjunctions

The adjunction property between two functors, T: C_1 \to C_2 and U: C_2 \to C_1, says that there is a natural bijection between morphisms \mathrm{Hom}_1(A, UB) (in the first category) and \mathrm{Hom}_2(TA, B) (in the second category). Here natural means that these bijection is compatible with composition with morphisms B \to B', UB \to UB' or A' \to A and TA' \to TA.

Adjunctions are naturally created by the use of monads or operads. For example, the functor V_k: \mathrm{Set} \to \mathrm{Vect}_k mapping a set X to the free vector space V_k(X) = k^{(X)} with basis X, has a adjoint, U: \mathrm{Vect}_k \to \mathrm{Set}, mapping a vector space to the set of its elements. The meaning of the adjunction is that a morphism V_k(X) \to W is equivalent to the choice X \to W of images of basis vectors where W is considered as as set. Similar adjunctions exist for other free objects (free algebras, free groups, free modules).

2 March 2009 at 12:13 am 1 comment

Laver tables and “unprovable” statements

Laver tables are combinatorial objets whose definition is surprisingly simple. However, they do have somewhat weird properties, which come from their relationship with questions of set theorists (namely, how do elementary embeddings of models of set theory behave). It also have connections with braid group theory, which I do not know. The Wikipedia article gives the basic facts, a survey by Patrick Dehornoy will give relevant bibliography, and friends of mine wrote an undergraduate thesis on the subject (in French).

The most basic definition of Laver tables is the Cayley table of a self-distributive binary operation. This means we define an exotic operation \star on a set of numbers, and fill a square table with the outcomes of this operation. The required property of this operation is a \star (b \star c) = (a \star b) \star (a \star c). This operation does not share properties with our usual operations, which are often associative of commutative. Suppose the set of numbers is \{0, 1, ..., n-1\} and that 1 acts on the right by shifts : i \star 1 = i+1 and (n-1) \star 1 = 0. (more…)

20 February 2009 at 4:51 pm 4 comments