[Haskell-cafe] Circular pure data structures?

[John Ky]

Hello,

If I use zippers, do all my nodes need to be the same type?  My tree doesn't
have the same type for every node.  For example:

Modules -> Module -> Types -> Type -> Members -> Member -> Type -> ...

Thanks

-John

On Wed, Jul 15, 2009 at 2:41 PM, Miguel Mitrofanov <miguelimo38 at yandex.ru>wrote:

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