[Haskell-cafe] Circular pure data structures?

Miguel Mitrofanov miguelimo38 at yandex.ru
Wed Jul 15 00:41:34 EDT 2009


Sufficient, but not good.

Try zippers instead.

On 15 Jul 2009, at 08:29, John Ky wrote:

> 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 <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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



More information about the Haskell-Cafe mailing list