[Haskell-cafe] Circular pure data structures?

John Dorsey haskell at colquitt.org
Tue Jul 14 18:55:18 EDT 2009


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



More information about the Haskell-Cafe mailing list