19th October 2008, 05:26 pm
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’ »
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...
19th October 2008, 05:23 pm
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’ »
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,...
15th October 2008, 06:18 pm
15th October 2008, 06:17 pm
Function memoization goes back at least as far as Donald Michie’s 1968 paper. The idea is to stash away results of a function call for reuse when a function is called more than once with the same argument. Given an argument, the memoized function looks up the argument in the internal memo table (often a hash table). If found, the previously computed result is reused. Otherwise, the function is applied, and the result is stored in the table, keyed by the argument. The table and its mutation are kept private from clients of the memo function.
Perhaps surprisingly, memoization can be implemented simply and purely functionally in a lazy functional language. Laziness allows the implementation to build the memo table once and for all, filling in all the results for the function at all domain values. Thanks to laziness, the values don’t actually get computed until they’re used. As usual with lazy data structures, once a component has been evaluated, future accesses come for free.
The implementation described in this post is based one I got from Spencer Janssen. It uses the essential idea of Ralf Hinze’s paper Generalizing Generalized Tries. The library is available on Hackage and a darcs repository. See the wiki page and hackage page for documentation and source code. I’ve compiled it successfully with ghc versions 6.8.2 through 6.10.3.
Edits:
- 2009-02-12: Fixed typo.
- 2009-11-14: Hackage page pointer.
- 2009-11-20: Fixed source code pointer.
Continue reading ‘Elegant memoization with functional memo tries’ »
Function memoization goes back at least as far as Donald Michie’s 1968 paper. The idea is to stash away results of a function call for reuse when a function is...