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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
