[Haskell-cafe] Finding zipper for custom tree

Sergey Mironov ierton at gmail.com
Thu Jul 1 15:54:16 EDT 2010

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'

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.

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 '*' ?

Any comments are welcome!

[1] - http://en.wikibooks.org/wiki/Haskell/Zippers
[2] - http://people.cs.uu.nl/andres/Rec/MutualRec.pdf


More information about the Haskell-Cafe mailing list