ok! (i didn't mean it as personal criticism - i am currently debugging/tuning my own recursive descent library (lepl) and am having a world of pain with memoisation, which is a similar problem...).
bryan, if you see this, more info on what makes that lib so fast would be greatly appreciated!
If you need to do any sort of benchmarking for Haskell libraries, I can't recommend Criterion (and Neil Brown's package Progression[1]) enough. It handles all the details for lazy evaluation (NF vs WHNF, pure vs IO, etc) quietly behind the scenes, and uses a well-designed statistics analysis library to calculate the final numbers. Don Stewart has written a short introduction, Modern Benchmarking in Haskell[2].
It's worth mentioning that Criterion can be used for anything that can be called via the FFI -- I'm using it for benchmarking Python libraries, for example.
bryan, if you see this, more info on what makes that lib so fast would be greatly appreciated!