[Haskell-cafe] Circular pure data structures?

[Eugene Kirpichov]

Zippers come up as the "derivative" of the type; if you haven't yet
encountered this trick, then first find it :)

Try differentiating your datastructure.

2009/7/15 John Ky <newhoggy at gmail.com>:
> 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
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru