[Haskell-cafe] Circular pure data structures?
newhoggy at gmail.com
Wed Jul 15 00:29:44 EDT 2009
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.
On Wed, Jul 15, 2009 at 8:55 AM, John Dorsey <haskell at colquitt.org> wrote:
> > 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
> 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?
> it enough to know that ones and (tail ones) are equal?
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe