[Haskell-beginners] library for lattice data structure

[Brent Yorgey]

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