Re: Proposal: improve the Data.Tree API

Hi all,

-----Original message----- From: João Cristóvão Sent: 2 Mar 2014, 16:47

<snip>

Consider proposal 3.0.b Milan's idea of splitting forest functions to a different submodule. Milan, could you please elaborate on that? I didn't quite get how they would have the same name...

The idea was to provide two modules, Data.Tree and Data.Tree.Forest. The methods for Forest would be in Data.Tree.Forest. To use the modules, the users would write import qualified Data.Tree as Tree import qualified Data.Tree.Forest as Forest and then use the methods as Tree.lookupTree Tree.filter and Forest.filter The disadvantage is that the Forest type still has to be defined in Data.Tree (otherwise we have a module dependency cycle), and that some methods for both Trees and Forests (unfoldTree + unfoldForest, drawTree + drawForest) already exist in Tree. If we provide both version methods in Data.Tree, the question is whether we should always use *Tree and *Forest to disambiguate the calls (filterTree, filterForest), or just use Forest (i.e., filter for Tree, filterForest for Forest). The current API is not consistent (drawTree + drawForest, but levels only, which could be easily defined for Forest too). The current proposal is also not consistent in this regard -- lookupTree and lookupTreeInForest, versus filterPruneTree and filterPruneForest.

<snip>

-- | Size of the (flattened) tree size :: Tree a -> Int size = getSum . F.foldMap (const $ Sum 1)

-- | Maximum depth of tree maxDepth :: Tree a -> Int

-- | Remove all nodes past a certain depth prune :: Int -> Tree a -> Tree a

-- | Take the mirror-image of a tree mirror :: Tree a -> Tree a mirror (Node a ts) = Node a . reverse $ map mirror ts

-- | List of subtrees (including the tree itself), in pre-order. subTrees :: Tree a -> [Tree a]

-- | List of subtrees at each level of the tree. subTreesByLevel :: Tree a -> [[Tree a]]

-- | Label each node of the tree with its full subtree. cojoin :: :: Tree a -> Tree (Tree a) cojoin t@(Node _ ts) = Node t (map cojoin ts)

Should we provide Forest variants of all those methods? We do so for lookup and filter, so I do not see reason why not for those, except for API growth. Cheers, Milan