[Haskell-cafe] Question about zippers on trees

Dominik Schrempf dominik.schrempf at gmail.com
Wed Jul 22 12:02:19 UTC 2020

Thank you for your fast answer.

A direct implementation without using a library is interesting, thank you. I
refrained from doing that, because I thought that Control.Zipper would actually
do this for me. Actually, I was pretty successful with using Control.Zipper to
change node labels, but failed doing more complicated stuff.

Andrew Martin <andrew.thaddeus at gmail.com> writes:

> From containers, Tree is defined as:
>     data Tree a = Node
>       { label :: a
>       , children :: [Tree a]
>       }
> (I've renamed the record labels.) What is a zipper into such a tree? I think
> that the [rosezipper](
> https://hackage.haskell.org/package/rosezipper-0.2/docs/Data-Tree-Zipper.html
> )
> library gives a good definition. I'll specialized it to rose trees:
>     data TreePos a  = Loc
>       { _content   :: Tree a -- ^ The currently selected tree.
>       , _before    :: [Tree a] -- ^ Forest to the left
>       , _after     :: [Tree a] -- ^ Forest to the right
>       , _parents   :: [([Tree a], a, [Tree a])] -- ^ Finger to the selected
> tree
>       }
> I think that does it. I wouldn't recommend using a library for this kind
> though. Just define `TreePos` in your code and then write the functions
> that you happen to need.
> On Wed, Jul 22, 2020 at 7:41 AM Dominik Schrempf <dominik.schrempf at gmail.com>
> wrote:
>> Hello Cafe!
>> I am trying to modify a large 'Data.Tree.Tree'. I managed to modify node
>> labels
>> with specific indices in the form of @[Int]@ as they are defined in, for
>> example, 'Control.Lens.At.Ixed' or 'Lens.Micro.GHC'.
>> However, I also need to
>> 1. modify the node label using information from nearby nodes (e.g., the
>>    children);
>> 2. modify the tree structure itself; for example, I may want to change the
>>    sub-forest.
>> Basically, I need a lens that focuses not on the node label, but on the
>> node
>> itself. I perceived that this is more difficult.
>> I tried to use 'Control.Zipper'. I can use zippers to achieve point 1,
>> albeit in
>> a complicated way: (1) I need to go downwards to focus the specific node;
>> (2) I
>> need to traverse the children to collect data and save the data somewhere
>> (how?
>> in let bindings?); (3) I then go back upwards and change the node label
>> using
>> the collected data. Even so, I do not really manage to change the actual
>> structure of the tree. I also briefly had a look at plates, but do not
>> manage to
>> use them in a proper way, maybe because the depth of my structures may be
>> several hundred levels.
>> Did you encounter similar problems in the past or could you point me to
>> resources discussing these issues?
>> Thank you!
>> Dominik
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.

More information about the Haskell-Cafe mailing list