[Haskell-cafe] Re: Finding zipper for custom tree

[Sergey Mironov]

2010/7/2 Heinrich Apfelmus <apfelmus at quantentunnel.de>:
> Sergey Mironov wrote:
>>
>> Hello list!
>> I am trying to understand zipper concept using papers like [1] and [2].
>> Though main idea looks clear, I still have a problem in applying it for
>> custom data types.
>>
>> Please help me with deriving Zipper-type from
>>
>>> data DTree a = P | D [(a, DTree)]
>>
>> Looking in [1] ('Zippers via Differentiation' chapter) I tried to do
>> the following:
>>
>> 1. Find a DTreeF type which is a pattern functor ([2], chapter 2.1) of my
>> DTree
>> 2. Write DTreeF in 'algebraic' form (using '+' and '*')
>> 3. Find DTreeF' - "derivative" of DTreeF
>> 4. Define my zipper type using list of DTreeF'
>
> These are the right steps.
>
>> Step 1 likely ends with
>>
>>> data DTreeF a x = P | D [(a,x)]
>>
>> [2] says that using this pattern functor one could build a fixed-point
>> version of DTree:
>>
>>> data Fix f = In {out :: (f (Fix f))}
>>> data DTreeFP = Fix DTreeF
>>
>> but seems that I have nothing to do with it right now.
>
> The fixed point is just another way to write  DTree .
>
>    DTreeFP a = DTree a
>
>> Step 2 is my main question:
>>
>> In [1] authors did it for binary tree:
>>
>> data Tree a = Leaf a | Bin (Tree a) (Tree a)
>>
>> data TreeF a x = Leaf a | Bin x x
>>
>> and thus
>>
>> TreeF = a + x * x
>>
>> TreeF' = x + x
>>
>> My DTree has inner list of tuples. How should I rewrite it in terms of
>> '+' and '*' ?
>
> Ah, you can't write it in terms of only '+' and '*' because you also have
> the list type in there:
>
>    DTreeF = 1 + List (a * x)
>                 ^^ List involves a fixed point
>
> So, to find the derivate, you have to calculate the derivative of  List
>  first:
>
>    List' x = List x * List x
>
> and then you can use the chain rule to find  DTreeF .
>
>
> Regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

Sorry for late answer. Luke, Heinrich - thank you very much for explanations.
I feel that I need more reading to get familiar with differentiation
of functors and chain rule. Could you suggest some books or papers?

-- 
Thanks,
Sergey