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?
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
.