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

On Mar 11, 2014, at 9:57 PM, Kim-Ee Yeoh wrote:

Looks like a case of Finite Language Syndrome. 'Lattice' has a pretty specific technical meaning in math, which isn't what's referred to here. If something on hackage mentions lattice, it's invariably the math meaning.

Yes, I was concerned there might be some conflict between the finance, math and/or physics terminology. I gave a fair amount of thought to how to refer to the structure, but in the end just picked lattice because that’s how it’s referred to in the wikipedia link I included and because I had already read a lot of quibbling over the use of “tree”, mostly in the context of binary trees and binary heaps. Coming from a finance background, differences in terminology between finance, physics, math, and statistics is par for the course. I’ll have to be better about understanding the terminology from a math perspective and will try to keep that in mind when posting to this list. Thanks, James

On 3/12/14 1:19 AM, Kim-Ee Yeoh wrote:

On Wed, Mar 12, 2014 at 11:35 AM, James Toll mailto:james@jtoll.com> wrote:

...

Coming from a finance background, differences in terminology between finance, physics, math, and statistics is par for the course. I’ll have to be better about understanding the terminology from a math perspective and will try to keep that in mind when posting to this list.

On deeper reflection, I realize it's more complicated than that. Because there are at least two meanings in math.

The lattices on hackage are all about posets and meets and joins, tracing back to the work of Birkhoff in that subspecialization of algebra known as order theory.

Then there are the lattices in sphere packings and geometric number theory and 'lattice'-based cryptography, cf ntru.

One could say that the geometric lattices are closer to binomial lattices, but not really. I wonder why 'binomial tree' isn't perfectly cromulent.

Thanks. Your comments have embiggened our understanding. -- Dudley