I have added tests that check to a very high depth. This has invalidated all the quadratic solutions.

More info on the required laziness of the solution has been added to the desciption.

tests implicitly assumes that nodes in the same depth should follow recursive graph vert traversal order on their first path

The tests no longer make this assumption, they now compare bag equality at each depth. Thanks for spotting!

I misspoke, what I meant is Nubs Vert as implemented by the sample tests (and actual tests) is linear per element, so it's quadratic.

I'm not sure what you mean by this. Nubs Vert is linear in the sample and actual tests. (nubs (xs :: [[Vert]]) takes O(n) time, where n == length (concat xs))

In what way are the tests deficient?

There doesn't have to be, the type you defined is a full binary tree.

Ok, I think I understand that this is a terminology/convention issue, rather than a strict correctness issue.

My problem is that the definition of a binary tree that I gave is (in my experience) the standard definition, and that adding the qualification of "full" is distracting and confusing. The alternative definition you gave (data Tree = Maybe Tree :*: Maybe Tree) is quite strange to my eyes, and an unconventional definition.

This may be very obvious in Haskell just by looking at the type, but in other languages, even if it were possible to enforce the fullness just from the type/structure, it may not be nearly as obvious.

I think most of the definitions in other languages I have seen are the same as the Haskell one? i.e. the Python, Ocaml, Rust defs that are currently there all seem to also be "full" binary trees. (as long as you don't allow null pointers in some cases, but I mean in that case you could also have the Haskell def include undefined)

I don't really see the harm in mentioning that fact for clarity?

I think I understand your viewpoint now, but I am going to leave the Kata as-is.

The word "full" made me think "oh, this is some other kind of binary tree, a subset of what is indicated by the type". I think, for most people, when they read "binary tree" and see the type, it's clear what is intended. Adding the qualifier confuses things.

You can define your isomorphism between balanced string of parentheses and binary trees with even number of nodes for example.

This would not satisfy the equations!

forall t. parensToTree (treeToParens t) = t

Doesn't hold if you haven't covered all possible inputs for t.

The description was changed due to a user reportedly spending a good amount of time trying to find an isomorphism between valid parens, and any binary tree.

I'll accept that this is possibly a terminology (and maybe language) issue, but it is impossible to represent anything other than a "full" binary tree with the type given.

data Tree = Leaf | Tree :*: Tree

There is no added condition on this type to make it valid (like a "full" condition). This is in contrast to the strings, which are a subset of the String type.

If the type defined in some translation allowed for trees other than the ones defined by the type above, then the translation is incorrect.

On @awesomead comment: quite insightful, however even with an isomorphism, a function can target a subspace and not necessarily the whole space of full binary trees.

This is incorrect. An isomorphism between balanced strings of parentheses and binary trees must hit every tree, and every possible balanced string of parens. This is implied by the meaning of an isomorphism.

Someone changed the description to say "full" binary trees, which is incorrect. I do not know why, so I have changed it back.

If your representation means that a and b are encoded as the same thing, that means you need to change your representation!

It seems that you're representing trees as nested parentheses, where something like (()()) might represent a tree with two subtrees, each represented by (). But that's not necessarily a good representation: don't tie yourself to the notion that the string of parentheses has to look anything like the tree it represents.

I'm not sure how much I can say as a hint without giving away an answer, but maybe this might help. The four simplest strings of parens I can think of are the following:

""
"()"
"()()"
"(())"

Whatever mapping you choose, these will have to map to unique and distinct trees. Why not pick the four simplest possible trees, and see if you can spot a pattern?

I have added some tests which will hopefully enforce laziness and catch solutions like this one.

Actually it is just a typo on my part!

Thanks! This is very helpful.

I'm trying to figure out a way to make solutions like these time out, but possibly the "correct" solution just isn't fast enough.

I'm not sure I understand the issue here.

Mapping "()" to a leaf, and "(()())" to Leaf :*: Leaf can work, but you still have to deal with all strings, including "". That's the puzzle: you need to figure out a representation that handles every possible string.

If we only kept the parensToTree (treeToParens Tree) test case that would only show that treeToParens is a surjection, not a bijection. You need the other test to show it's a bijection.