Fwd: [Haskell-cafe] Data.Tree.Zipper in the standard libraries

Ian Lynagh igloo at earth.li
Wed Jun 4 17:36:40 EDT 2008


On Wed, Jun 04, 2008 at 11:11:58PM +0200, apfelmus wrote:
> Ian Lynagh wrote:
> >
> >Also, it's actually the derivative of Forest, not Tree, right? Which is
> >why toTree can lose information, here the b and c trees:
> >    Data.Tree.Zipper> toTree (Loc (Node 'a' []) [Node 'b' []] [Node 'c' 
> >    []] [])
> >    Node {rootLabel = 'a', subForest = []}
> >This feels a little scary to me.

I should expand on that: I wonder if toTree should return
    Maybe (Tree a)
which returns Nothing if either sibling is non-empty.

> Yes. A zipper for a tree would have to carry the value  a  around.

It would actually simplify the datastructure; rather than

    data TreeLoc a  = Loc
      { tree    :: Tree a       -- ^ The currently selected tree.
      , lefts   :: Forest a     -- ^ Siblings on the left, closest first.
      , rights  :: Forest a     -- ^ Siblings on the right, closest first.
      , parents :: [(Forest a, a, Forest a)]
          -- ^ The contexts of the parents for this location.
      } deriving (Read,Show,Eq)

we could have just

    data TreeLoc a  = Loc
      { tree    :: Tree a       -- ^ The currently selected tree.
      , parents :: [(Forest a, a, Forest a)]
          -- ^ The contexts of the parents for this location.
      } deriving (Read,Show,Eq)

where the Forests are now children of the parent nodes, rather than
their siblings. The cost is that you now can't represent forests nicely.


Thanks
Ian



More information about the Libraries mailing list