[Haskell-cafe] Circular pure data structures?

John Ky 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:

> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090715/1fa6fb95/attachment.html

More information about the Haskell-Cafe mailing list