Redundant information in zipper data type in Data.Tree.Zipper?

Question

In Data.Tree.Zipper the zipper data type for a rose tree is

data TreePos t a  = Loc
  { _content   :: t a        -- ^ The currently selected tree.
  , _before    :: Forest a
  , _after     :: Forest a
  , _parents   :: [(Forest a, a, Forest a)]
  } deriving (Read,Show,Eq)

Now it seems to me that the information in _after and _before is redundant as it should show up in the _parents field as well. (The siblings of a node are the children of its parents.)

Why is this? Out of convenience?

Answer 1

There is no redundant information. The _parents field contain the left and right siblings on the path from the focused tree to the root, but not the direct siblings.

Let's look at a concrete example:

                               1
                               |
                    -----------------------
                    |          |          |
                    2          10         11
                    |                     |
              -------------             -----
              |  |  |  |  |             |   |
              3  4  5  6  9             12  13
                       |
                     -----
                     |   |
                     7   8

This tree can be represented as follows:

t = Node 1 [ Node 2  [ Node 3 []
                     , Node 4 []
                     , Node 5 []
                     , Node 6 [ Node 7 []
                              , Node 8 []
                              ]
                     , Node 9 []
                     ]
           , Node 10 []
           , Node 11 [ Node 12 []
                     , Node 13 []
                     ]
           ]

Now let's descend to the subtree with label 6 (I'm using fromJust here as an exception because I know exactly what tree we're dealing with):

l = fromJust $ do
  node1 <- return (fromTree t)
  node2 <- childAt 0 node1
  node6 <- childAt 3 node2
  return node6

Now let's inspect the resulting location:

Loc
  { _content = F (Node 6 [ Node 7 []
                         , Node 8 []
                         ]
               )
  , _before  = [ Node 5 []
               , Node 4 []
               , Node 3 []
               ]
  , _after   = [ Node 9 []
               ]
  , _parents = [ ( []
                 , 2
                 , [ Node 10 [], 
                     Node 11 [ Node 12 [],
                               Node 13 []
                   ]
                 )
               , ( []
                 , 1
                 , []
                 )
               ]
  }

You can see that:

• _contents contains the selected subtree at label 6 as expected,

• _before contains the direct siblings to the left (in reverse order),

• _after contains the direct siblings to the right,

• _parents is a list containing two entries, because there are two levels above the selected tree, so it describes the path from the selected subtree to the top. The first entry says that we descended through label 2 which has no left siblings and two right siblings. The second entry says that the root has label 1.

Answer 2

Thanks for the very thorough explanation!

The reason I was confused is that if you take the data type for a rose tree

data Rose x = Rose x [Rose x]

and take the derivative

R = x L(R(x))
R' = L(R) + x L' R'
R' = L(R) / (1 - x L')
R' = L(R) / (1 - x L^2)
R' = L(R) * L(x L^2)

this directly translates to the following data type for the zipper

data TreePos t a  = Loc
  { _content   :: t a        -- ^ The currently selected tree.
  , _parents'  :: [(Forest a, a, Forest a)]
  } deriving (Read,Show,Eq)

where in this case, the first element in _parents' holds the information about the siblings of the focused node.
Obviously, both versions should be equivalent. I just carelessly assumed that _parents and _parents' would hold exactly the same information. One small "drawback" to the implementation in Data.Tree.Zipper though: as far as I can see the last element in _parents always contains two empty lists and thus still some redundant information :-)