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

[Ian Lynagh]

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