[Haskell-beginners] library for lattice data structure

[James Toll]

On Mar 11, 2014, at 8:40 PM, Brent Yorgey  wrote:

> 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.
> 
>> 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


Brent,

Wow, thank you.  I really appreciate your taking the time to provide so much guidance on the subject.  I’m vaguely familiar with memoization, but had not even heard of “knot-tying" techniques.  So I’ll really have to look into both topics.

Again, thanks for the guidance.  As they say, you don’t know what you don’t know, so it’s just so helpful to be pointed in the right direction.

Thanks,


James