Hi James, On Tue, Mar 11, 2014 at 07:51:23PM -0500, James Toll wrote:
Hi,
I have a general question regarding data structures, maybe functional data structures, in Haskell and I’m hoping for some advice. I would like to implement the binomial option pricing model in Haskell.
https://en.wikipedia.org/wiki/Binomial_options_pricing_model
Given its lattice structure, I originally thought of trying a recursive implementation, but because it’s recombining, the interior nodes would be calculated twice.
It's even worse than that---a naive implementation will end up doing exponentially too much work. The interior nodes are recalculated much more than just twice. I once had a student who implemented exactly this, and did it in a clever way---they constructed an actual binary tree data structure, but using some "knot-tying" techniques (http://www.haskell.org/haskellwiki/Tying_the_Knot) to result in all the internal nodes actually being shared in memory. So it really was a binary tree data structure but in memory it looked like a lattice.
lattices package http://hackage.haskell.org/package/lattices From the name I thought this might be perfect, but the documentation is very terse and there doesn’t appear to be any other documentation so I’m not even sure how to get started with constructing a lattice with this package.
This package is actually about the mathematical abstraction of lattices; it has nothing to do with data structures. Matrices and vectors are definitely too low-level for this problem.
I thought this example implementation in Haskell was intriguing but it doesn’t sound as though it’s very quick. http://www.thulasidas.com/2009-03/a-new-kind-of-binomial-tree.htm
You're right; this implementation has the exponential blowup problem. However, it's actually possible to take this code and make some simple modifications so that it runs quickly, by memoizing the function f. One simple way to do that is to replace the function f with lookups into an array---the trick is that you can construct the array recursively, and thanks to laziness the entries in the array will automatically be computed in the right order, so you don't have to worry about that like you would in, say, R. For an example, see the very last section (titled "Dynamic Programming") on this page: http://www.cis.upenn.edu/~cis194/lectures/06-laziness.html -Brent