[Haskell-cafe] Re: Finding zipper for custom tree
Sergey Mironov wrote: 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? For differentiation of data types, there is for example Conor McBride The Derivative of a Regular Type is its Type of One-Hole Contexts. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8611 but I'm not sure whether it's easier to understand than the wikibook. For more on using functors to model algebraic data types, see also R Backhouse, P Jansson, J Jeuring, L Meertens Generic Programming - An Introduction - http://www.cse.chalmers.se/~patrikj/poly/afp98/ A corresponding chapter in the wikibook (Datatype algebra) has not been written, so far. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Finding zipper for custom tree
2010/7/2 Heinrich Apfelmus apfel...@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@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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finding zipper for custom tree
Luke Palmer wrote: I would just use List. IIRC the derivative of list is: data DList a = DLIst [a] [a] Understood as the elements before the focused one and those after it. Unfortunately I can't remember how that is derived, and my own experiments failed to come up with anything similar. That may indicate that the rest of this message is nonsense. Note that there is a really subtle difference between derivative and zipper which is probably the source of confusion. For lists, both are the same, though. The derivative of the list type with respect to the element type is d List = d (\a - 1 + a * List a) = \a - List a + a * d List a d List a = List a + a * d List a d List a ~ List a * List a The very last isomorphism of types is not trivial and probably the reason why you were stumped. data DTree a = P | D [(a, DTree a)] Can be written algebraically as: DTree a = 1 + List (a * DTree a) DTree a = Mu f. 1 + List (a * f) Differentiating: DDTree a = Mu f. DList (a * f) * a DDTree a = DList (a * DTree a) * a The difference between zipper and derivative shows up here. Namely, your second equation for DDTree a does not follow from the first, it should be DDTree a = DList (a * DDTree a) * a ^^ two Ds To understand this intuitively, DDTree a is the context in which a DTree can appear within itself. The context in which DDTree a can appear within itself is indeed the zipper. But this is different from the derivative with respect to a , which gives the context in which a can appear within DDTree a . To get the zipper, you have to derive the pattern functor with the respect to the variable that will tie the recursion, in this case f . d (DTreeF a) = d (\f - 1 + List (a * f)) = 0 + (d (\g - List g) (a * f)) * d (\f - a * f) = d List (a * f) * a So that is: The (a * DTree a)s that appeared before and after the current list element, together with the a that was paired with the current element. Then, the zipper is a *list* of these things: ContextDTree a = List (DList (a * DTree a) * a) After all, what you describe is only the context of DTree a within a single level, but it might be many levels down in the tree. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finding zipper for custom tree
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
