Proposal: improve the Data.Tree API

[Milan Straka]

Hi all,

> -----Original message-----
> From: João Cristóvão <jmacristovao at gmail.com>
> 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