Archive for 19th October 2008

Simpler, more efficient, functional linear maps

A previous post described a data type of functional linear maps. As Andy Gill pointed out, we had a heck of a time trying to get good performance. This note describes a new representation that is very simple and much more efficient. It’s terribly obvious in retrospect but took me a good while to stumble onto.

The Haskell module described here is part of the vector-space library (version 0.5 or later) and requires ghc version 6.10 or better (for associated types).

Edits:

  • 2008-11-09: Changed remarks about versions. The vector-space version 0.5 depends on ghc 6.10.
  • 2008-10-21: Fixed the vector-space library link in the teaser.

Continue reading ‘Simpler, more efficient, functional linear maps’ »

Vector space bases via type families

A basis B of a vector space V is a subset B of V, such that the elements of B are linearly independent and span V. That is to say, every element (vector) of V is a linear combination of elements of B, and no element of B is a linear combination of the other elements of B. Moreover, every basis determines a unique decomposition of any member of V into coordinates relative to B.

This post gives a simple Haskell implementation for a canonical basis of a vector space, and a means of decomposing vectors into coordinates. It uses [indexed type families] (associated types), and is quite general, despite its simplicity.

The Haskell module described here is part of the vector-space library (version 0.4 or later), which available on Hackage and a darcs repository. See the wiki page, interface documentation, and source code. The library version described below (0.5 or later) relies on ghc 6.10.

Edits:

  • 2008-11-09: Tweaked comment above about version.
  • 2008-02-09: just fiddling around

Continue reading ‘Vector space bases via type families’ »