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

[Heinrich Apfelmus]

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