Yes, indeed, thats a totally different discussion I do not want to enter: http://www.reddit.com/r/haskell/comments/xo05l/why_isnt_length_part_of_folda... So, I'll 'erase' the length function from the proposal, since: * it's definition is not unanymous * my definition (number of elements) is simple enough to be implemented in several ways Cheers João 2014-02-24 10:48 GMT+00:00 Henning Thielemann < schlepptop@henning-thielemann.de>:

Am 24.02.2014 11:39, schrieb João Cristóvão:

-- | Length of the tree

...

length :: Tree a -> Int

This one could be implemented more generally (maybe additionally) in Data.Foldable. But this would be another proposal.

I was thinking of: length :: Tree a -> Int length = L.length . flatten But to be honest, I don't have strong feelings about this, I'm willing to drop this particular function (length) from the proposal, if there is no consensus. João 2014-02-24 10:50 GMT+00:00 Ivan Lazar Miljenovic :

On 24 February 2014 21:39, João Cristóvão wrote:

...

Hello,

The Data.Tree API seems rather poor. Some research on hackage shows some additional functions being defined in very unrelated packages:

http://hackage.haskell.org/package/debian-3.81/docs/Debian-Apt-Dependencies....

...

http://hackage.haskell.org/package/hledger-lib-0.22.1/docs/Hledger-Utils.htm...

...

I propose the addition of the following functions, that seem rather

...

forward to me:

-- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a)

-- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition findTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)

-- | keep only the elements that match the provided condition filter :: (a -> Bool) -> Tree a -> Tree a

The 'Tree' is appended in the name, to distinguish from the Foldable instances, that return the value, and not a sub-tree.

Additionally, the following two functions might also be useful (even if

straigh the

...

implementation is very simple in the second case): -- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a)

-- | Length of the tree length :: Tree a -> Int

What is the length of a tree? The number of sub-trees of that particular root node? The overall width of the tree? The number of nodes?

...

There are probably more useful functions to add, so suggestions are welcomed.

Previous discussion: https://github.com/haskell/containers/issues/39#issuecomment-35799628

Discussion period: 2 weeks

Cheers, João

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

On 24 February 2014 22:17, Tobias Florek wrote:

hi,

...

But to be honest, I don't have strong feelings about this, I'm willing to drop this particular function (length) from the proposal, if there is no consensus.

then what about the arguably better name `size`?

Huh, I thought we already had that. Some things I missed when I last used Data.Tree: * An Ord instance (achievable via standalone deriving, though this isn't ideal) * A function to take the mirror-image of a tree (name not that important): mirror :: Tree a -> Tree a mirror (Node a ts) = Node a . reverse $ map mirror ts * Functions to take/drop so many levels of the tree (take is relatively easy; drop would result in a Forest).

cheers, tobias florek

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

Hey, So, proposal 2.0, with the received feedback: -- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a) -- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition findTree :: (a -> Bool) -> Tree a -> Maybe (Tree a) -- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a) -- | keep only the elements that match the provided condition filter :: (a -> Bool) -> Tree a -> Tree a -- | 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 Any additions / comments? Thanks, João 2014-02-24 12:55 GMT+00:00 João Cristóvão :

Hi Ivan,

...

...

then what about the arguably better name `size`? Huh, I thought we already had that.

We do? If there is consensus I would then add `size` with the arguably more efficient implementation: size :: Tree a -> Int size = getSum . F.foldMap (const $ Sum 1)

...

* An Ord instance (achievable via standalone deriving, though this isn't ideal)

Agreed.

...

* Functions to take/drop so many levels of the tree (take is relatively easy; drop would result in a Forest).

Similar to treeprune in http://hackage.haskell.org/package/hledger-lib-0.22.1/docs/Hledger-Utils.htm... ?

...

mirror :: Tree a -> Tree a mirror (Node a ts) = Node a . reverse $ map mirror ts

I don't have strong feeling about this one, but if more people see as useful, why not...

João

2014-02-24 11:38 GMT+00:00 Ivan Lazar Miljenovic :

...

On 24 February 2014 22:17, Tobias Florek wrote:

...

hi,

...

But to be honest, I don't have strong feelings about this, I'm willing to drop this particular function (length) from the proposal, if there is no consensus.

then what about the arguably better name `size`?

Huh, I thought we already had that.

Some things I missed when I last used Data.Tree:

* An Ord instance (achievable via standalone deriving, though this isn't ideal)

* A function to take the mirror-image of a tree (name not that important):

mirror :: Tree a -> Tree a mirror (Node a ts) = Node a . reverse $ map mirror ts

* Functions to take/drop so many levels of the tree (take is relatively easy; drop would result in a Forest).

...

cheers, tobias florek

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

You're right, sorry, forgot that one. 2014-02-27 11:43 GMT+00:00 Ivan Lazar Miljenovic :

And an Ord instance.

On 27 February 2014 22:34, João Cristóvão wrote:

...

Hey, So, proposal 2.0, with the received feedback:

-- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a)

-- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition findTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)

-- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a)

-- | keep only the elements that match the provided condition filter :: (a -> Bool) -> Tree a -> Tree a

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

Any additions / comments? Thanks, João

2014-02-24 12:55 GMT+00:00 João Cristóvão :

...

Hi Ivan,

...

...

then what about the arguably better name `size`? Huh, I thought we already had that.

We do? If there is consensus I would then add `size` with the arguably more efficient implementation: size :: Tree a -> Int size = getSum . F.foldMap (const $ Sum 1)

...

* An Ord instance (achievable via standalone deriving, though this isn't ideal)

Agreed.

...

* Functions to take/drop so many levels of the tree (take is relatively easy; drop would result in a Forest).

Similar to treeprune in http://hackage.haskell.org/package/hledger-lib-0.22.1/docs/Hledger-Utils.htm... ?

...

mirror :: Tree a -> Tree a mirror (Node a ts) = Node a . reverse $ map mirror ts

I don't have strong feeling about this one, but if more people see as useful, why not...

João

2014-02-24 11:38 GMT+00:00 Ivan Lazar Miljenovic :

...

On 24 February 2014 22:17, Tobias Florek wrote:

...

hi,

...

But to be honest, I don't have strong feelings about this, I'm willing to drop this particular function (length) from the proposal, if there is no consensus.

then what about the arguably better name `size`?

Huh, I thought we already had that.

Some things I missed when I last used Data.Tree:

* An Ord instance (achievable via standalone deriving, though this isn't ideal)

* A function to take the mirror-image of a tree (name not that important):

mirror :: Tree a -> Tree a mirror (Node a ts) = Node a . reverse $ map mirror ts

* Functions to take/drop so many levels of the tree (take is relatively easy; drop would result in a Forest).

...

cheers, tobias florek

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

Am 27.02.2014 14:08, schrieb Johan Tibell:

General comment: none of the other containers APIs use a function<DataType> suffix. I noticed that Data.Tree does for a bunch of functions. Perhaps we should avoid continuing down that path and instead have functions like 'lookup' and 'lookupInForest'.

Yes please, but I already got lots of resistance for a qualifiable name in Data.Bits.

I'm with Sean here, In Data.Map, for example, the lookup function returns the type Maybe a, not Data.Map k a. And find, in Data.Foldable (for which Tree has an instance) also returns a Maybe a. But the lookupTree/findTree/lookupTreeInForest functions return Maybe (Tree a), thus I added the final 'Tree' in the name. The only function name where that did not apply was filter, since (for example) for lists the filter function also returns the type of the original container, not the inner type. This was the rationale I followed. I'm afraid that renaming findTree to findBy will be confusing, as it seems that you just provide a 'evaluator function', but still return the inner type a (like find), instead of the (actual) Tree a. Cheers, João 2014-02-27 15:27 GMT+00:00 Daniel Trstenjak :

On Thu, Feb 27, 2014 at 03:05:00PM +0100, Henning Thielemann wrote:

...

Yes please, but I already got lots of resistance for a qualifiable name in Data.Bits.

I really think that 'Data.Bits' is a bit special in this regard with all of its functions, which are often used with back ticks and importing all of them explicitely is really a bit annoying.

Otherwise I'm with you :).

Greetings, Daniel _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Hi all,

-----Original message----- From: Johan Tibell Sent: 28 Feb 2014, 14:11

OK. That sounds fine by me. Milan?

I like lookupTree (being the one who suggested that), as it is returning a Tree. But maybe it would be better to have lookupTreeBy instead of findTree -- when you see lookupTree and lookupTreeBy, it is quite obvious how they differ. If I saw lookupTree and findTree, I would have to see the docs to find the difference. I am nevertheless not convinced about lookupTreeInForest -- the name seems too long. Also, many other functions could be applied to Forest -- filterForest, pruneForest, forestSize, ... Just a wild idea -- if we want to export more functions working with Forest a, what if we added Data.Tree.Forest module, and export from there? The functions would then have the same name as the Tree counterparts. Cheers, Milan

On Fri, Feb 28, 2014 at 1:10 PM, João Cristóvão wrote:

...

I'm with Sean here,

In Data.Map, for example, the lookup function returns the type Maybe a, not Data.Map k a. And find, in Data.Foldable (for which Tree has an instance) also returns a Maybe a.

But the lookupTree/findTree/lookupTreeInForest functions return Maybe (Tree a), thus I added the final 'Tree' in the name.

The only function name where that did not apply was filter, since (for example) for lists the filter function also returns the type of the original container, not the inner type.

This was the rationale I followed. I'm afraid that renaming findTree to findBy will be confusing, as it seems that you just provide a 'evaluator function', but still return the inner type a (like find), instead of the (actual) Tree a.

Cheers, João

2014-02-27 15:27 GMT+00:00 Daniel Trstenjak :

On Thu, Feb 27, 2014 at 03:05:00PM +0100, Henning Thielemann wrote:

...

...

Yes please, but I already got lots of resistance for a qualifiable name in Data.Bits.

I really think that 'Data.Bits' is a bit special in this regard with all of its functions, which are often used with back ticks and importing all of them explicitely is really a bit annoying.

Otherwise I'm with you :).

Greetings, Daniel _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Hi Daniel,

-----Original message----- From: Daniel Trstenjak Sent: 28 Feb 2014, 15:22

...

But maybe it would be better to have lookupTreeBy instead of findTree -- when you see lookupTree and lookupTreeBy, it is quite obvious how they differ. If I saw lookupTree and findTree, I would have to see the docs to find the difference.

Why then not going with the shorter 'findTree' and 'findTreeBy'?

we are using mostly lookup in containers. Also lookup would be more consistent with Data.List.lookup (versus Data.List.find). Cheers, Milan

On Thu, Feb 27, 2014 at 3:08 PM, Johan Tibell wrote:

General comment: none of the other containers APIs use a function<DataType> suffix. I noticed that Data.Tree does for a bunch of functions.

Isn't that because there are Tree and Forest variants of functions with different types? For example: unfoldTree :: (b -> (a, [b])) -> b -> Tree a unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a The other container APIs do not have mutually recursive type names like Tree and Forest and, therefore, do not have analogous function variants. Perhaps we should avoid continuing down that path and instead have

functions like 'lookup' and 'lookupInForest'.

To be consistent with the Data.Tree naming pattern of Tree/Forest variants, maybe these functions should be lookupTree/lookupForest or lookupInTree/lookupInForest. Otherwise, your conclusion may be valid for functions that are do not have variants. Regards, Sean

João Cristóvão wrote:

...

So, proposal 2.0, with the received feedback:

-- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a)

-- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition findTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)

-- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a)

Why is filter now missing? That's the one I've needed the most. Note however, that there are two possible implementations of filtering for Trees and Forests. The type signature you provided doesn't match any of them, so I'm not sure exactly what you had in mind. I support adding all four of these: -- | Prune every subtree whose root label does not match. filterPruneTree :: (a -> Bool) -> Tree a -> Maybe (Tree a) filterPruneTree p (Node x ns) | p x = Just . Node x $ filterPruneForest p ns | otherwise = Nothing filterPruneForest :: (a -> Bool) -> Forest a -> Forest a filterPruneForest = mapMaybe . filterPruneTree -- | Remove nodes that do not match, and graft the children of the removed node onto the tree in place of the parent. filterGraftTree :: (a -> Bool) -> Tree a -> Forest a filterGraftTree p (Node x ns) | p x = [Node x $ filterGraftForest p ns] | otherwise = filterGraftForest p ns filterGraftForest :: (a -> Bool) -> Forest a -> Forest a filterGraftForest = concatMap . filterGraftTree Ross Paterson wrote:

These functions are similar, and one can imagine many more along similar lines: get all the subtrees whose roots satisfy a condition, conditions involving the number of children, etc. There's a concern that the interface becomes large and unwieldy, but without covering all uses... perhaps it would be better to provide... compositions of flatten and levels with the cojoin.. but maybe that's too abstract.

I think it's just that people missed the fact that we already have these functions via the Comonad instance. For that reason, I really haven't missed those functions. I'm not sure why you're saying it's abstract - the Comonad instance for Tree is very concrete, and in fact it's one of the fundamental examples of a comonad. Unfortunately, it's going to be tricky to write implementations of these functions in terms of extend and duplicate in the containers library itself, because containers is distributed with GHC whereas the comonad library isn't even in the Haskell Platform yet (it should be). We should either just document these uses in Data.Tree, or (for now) re-implement unexported versions of extend and duplicate inside Data.Tree, and mention in the documentation that these functions are simple applications of them. Thanks, Yitz

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

-----Original message----- From: Henning Thielemann Sent: 14 Mar 2014, 09:39

<snip>

...

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

I find this naming scheme attractive. In order to break module cycles I usually define private modules. E.g.

Data.Tree.Private exports Tree, but the module is hidden Data.Tree.Forest imports Tree, exports Forest, module is exposed Data.Tree imports Tree and Forest, exports Tree, module is exposed

You are right, no dependency cycle here. Nevertheless, we probably have to export both Tree a and Forest a from Data.Tree, as the Tree datatype uses Forest. Forest is actually only type Forest a = [Tree a] so it is not such a big issue :) We should probably reexport Tree a and Forest a from Data.Tree.Forest too, so that users can use only Data.Tree.Forest module without Data.Tree. Cheers, Milan

A relevant change has occurred since this proposal came out: `length` got added to `Foldable`, with semantics that seem to match this `size`. In light of this, I think `size` should probably be dropped, and the `Foldable` instance expanded to give a better `length`. Aside from that, someone just has to put together a pull request for haskell/containers on GitHub. The hardest part of this whole thing would be the module split. I don't personally see the point—trees are made of forests, which are made of trees, so while you *could* use Henning's trick to avoid cycles, you'd likely end up putting much of the code in Data.Tree.Private (to avoid orphan instances) and then end up with everyone exporting both public modules. For now, even with the proposed additions, Data.Tree is quite a small module, so I don't know why we should go to the trouble. On Sun, Dec 28, 2014 at 3:58 PM, Yitzchak Gale wrote:

João Cristóvão wrote in February 2014:

...

The Data.Tree API seems rather poor... I propose the addition of the following functions, that seem rather straigh forward to me... Discussion period: 2 weeks

Umm. A bit more than 2 weeks has passed since last February. Can we add these yet?

There was a strong consensus to enrich Data.Tree in the way proposed by João. There was a bit of discussion about naming - constructive discussion, not bikeshedding at all, really.

When the thread ended, we had João's "version 3.0 b" of his proposal, which is the functions in "version 3.0 a" (repeated below to jog your memory), but re-organized into separate modules for Tree and Forest according to Henning's plan (also repeated below), with all functions appearing in both of the modules as appropriate, and the epithets "Tree" and "Forest" removed from the function names themselves.

Based on the discussion then, I recommend that we add to the haddock comments a note that some of the functions are simple uses of the Comonad instance for Tree, and several more variations can easily be built using the duplicate and extend functions from the comonad library.

Can we please add this to the containers library now?

Thanks, Yitz

Henning's plan for the module organization:

...

Data.Tree.Private exports Tree, but the module is hidden Data.Tree.Forest imports Tree, exports Forest, module is exposed Data.Tree imports Tree and Forest, exports Tree, module is exposed

João's proposal "version 3.0 a":

(Ord instance for Tree)

-- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a)

-- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition lookupTreeBy :: (a -> Bool) -> Tree a -> Maybe (Tree a)

-- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a)

-- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForestBy :: (a -> Bool) -> [Tree a] -> Maybe (Tree a)

-- | 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)

-- | Prune every subtree whose root label does not match. filterPruneTree :: (a -> Bool) -> Tree a -> Maybe (Tree a) filterPruneTree p (Node x ns) | p x = Just . Node x $ filterPruneForest p ns | otherwise = Nothing

filterPruneForest :: (a -> Bool) -> Forest a -> Forest a filterPruneForest = mapMaybe . filterPruneTree

-- | Remove nodes that do not match, and graft the children of the removed node onto the tree in place of the parent. filterGraftTree :: (a -> Bool) -> Tree a -> Forest a filterGraftTree p (Node x ns) | p x = [Node x $ filterGraftForest p ns] | otherwise = filterGraftForest p ns

filterGraftForest :: (a -> Bool) -> Forest a -> Forest a filterGraftForest = concatMap . filterGraftTree _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Oh, I see what you mean now! We could probably put *everything* in the private module and then use the public ones just for names. That seems fine. On Sun, Dec 28, 2014 at 6:04 PM, Yitzchak Gale wrote:

David Feuer wrote:

...

A relevant change has occurred since this proposal came out: `length` got added to `Foldable`, with semantics that seem to match this `size`. In light of this, I think `size` should probably be dropped, and the `Foldable` instance expanded to give a better `length`.

Sounds good.

...

Aside from that, someone just has to put together a pull request for haskell/containers on GitHub.

OK. João was the original owner; let's see if he wants to follow through.

...

The hardest part of this whole thing would be the module split. I don't personally see the point—trees are made of forests, which are made of trees, so while you *could* use Henning's trick to avoid cycles, you'd likely end up putting much of the code in Data.Tree.Private (to avoid orphan instances) and then end up with everyone exporting both public modules. For now, even with the proposed additions, Data.Tree is quite a small module, so I don't know why we should go to the trouble.

As discussed at the time - the consistent naming convention throughout the containers library is to avoid using names of types as parts of function names. Instead, separate modules are used to qualify the same name for functions that do the same thing. The module split was proposed to comply with that convention, and no one expressed any opposition.

However, personally I'm also fine with using João's original names to avoid the module split. What's important to me is getting these long-overdue combinators into the library as soon as possible, without arguing over the names.

Thanks, Yitz

On Wed, 31 Dec 2014, João Cristóvão wrote:

For the record, nevertheless, I was moving along with the separate Tree/Forest modules to avoid further bikeshedding, but to be honest I don't really see a big advantage - if your using one, you most probably will also need to use the other, so why two imports?

What is bad about two imports?

Henning Thielemann wrote:

...

What is bad about two imports?

João Cristóvão wrote:

It is a breaking change from the current Data.Tree API... would imply turning: Data.Tree.unfoldTree -> Data.Tree.unfold Data.Tree.unfoldForest -> Data.Tree.Forest.unfold Thus breaking existing code.

I didn't envision this as being a breaking change, at least not immediately. I think the idea is: 1. Leave everything currently in Data.Tree as it is. 2. For new functions that apply to trees, put them into Data.Tree, and if there are versions of those that apply to forests, put those into Data.Tree.Forest with the same name. 3. For existing functions in Data.Tree that explicitly include "Tree" or "Forest" as part of the function name, provide aliases using the above scheme. Perhaps mark the old versions as deprecated, but don't get rid of them yet. 4. Use Henning's internal module trick to work around circular module dependencies, re-exporting and/or renaming functions in the modules they need to appear in for the API. Also, re-export Forest itself from Data.Tree.Forest, just because if we don't it would look silly. Thanks, Yitz