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