Hello,
Actually, I wanted to be able to create a tree structure when I can navigate
both leaf-ward and root-ward. I didn't actually care for equality.
I think the tying the knot technique as mentioned by others is sufficient
for this purpose.
Cheers,
-John
On Wed, Jul 15, 2009 at 8:55 AM, John Dorsey
John,
Is it possible to create a circular pure data structure in Haskell? For example:
Creating the data structure is easy; as other respondents have pointed out. A simple example is this...
ones = 1 : ones ones' = 1 : ones'
Comparing these values is harder. All of (ones), (ones'), (tail ones), and so forth are equal values. But I don't know how to compare them. My Spidey-sense tells me there's probably a simple proof that you can't, if you care about the comparison terminating.
"Pointer equality" (ie. testing if the values are represented by the same bits in memory) is no good, since it's entirely up to the compiler whether ones and ones' use the same bits. (They won't, but that's not important.) In general "pointer equality" of Haskell values, such as ones and (tail ones) interferes with referential transparency, which is held in high regard around here. Although, for the record, when pointer equality is really what you want, I'm sure there's ways to Force It.
For your purposes, does it matter if you can actually do the comparison? Is it enough to know that ones and (tail ones) are equal?
Regards, John
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe