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

2010/7/2 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

_______________________________________________ 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

I am trying to document my parser library. In order to do so I should like to include some example output in my haddock documentation. I fail to see however how to get a block of output into the haddock part. E.g. -- | We can now run the parser @`pa`@ on input \"a\", which succeeds: -- @ Result: \"a\" -- @ does not put the Result ... on a separate line, and if I have several lines of output they are concatenated. How to proceed, Doaitse

On Wednesday 21 July 2010 16:09:37, S. Doaitse Swierstra wrote:

I am trying to document my parser library. In order to do so I should like to include some example output in my haddock documentation. I fail to see however how to get a block of output into the haddock part.

E.g.

-- | We can now run the parser @`pa`@ on input \"a\", which succeeds: -- @ Result: \"a\" -- @

-- | We can now ... -- -- @ -- Result: \"a\" -- @ -- -- In further news, ...

does not put the Result ... on a separate line, and if I have several lines of output they are concatenated.

How to proceed,

Doaitse

On Wednesday 21 July 2010 16:23:48, S. Doaitse Swierstra wrote:

Unfortunately I get for input:

-- | We can now run the parser @`pa`@ on input \"a\", which succeeds: -- @ -- Result: \"a\" -- Second line -- @

the output

You need to separate the @'d paragraph from the rest of the comment by a blank comment line. -- | We can now run the parser @`pa`@ on input \"a\", which succeeds: -- -- @ -- Result: \"a\" -- Second line -- @ ought to work as intended.

We can now run the parser pa on input "a", which succeeds: Result: "a" Second line

Doaitse

On 21 jul 2010, at 16:17, Daniel Fischer wrote:

...

On Wednesday 21 July 2010 16:09:37, S. Doaitse Swierstra wrote:

...

I am trying to document my parser library. In order to do so I should like to include some example output in my haddock documentation. I fail to see however how to get a block of output into the haddock part.

E.g.

-- | We can now run the parser @`pa`@ on input \"a\", which succeeds: -- @ Result: \"a\" -- @

-- | We can now ... -- -- @ -- Result: \"a\" -- @ -- -- In further news, ...

...

does not put the Result ... on a separate line, and if I have several lines of output they are concatenated.

How to proceed,

Doaitse