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

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. Other implementations used by the tests are sublinear per element, so they're fine.

BFS does not define a "canonical" order on the order of nodes at any specific depth, but the tests implicitly assumes that nodes in the same depth should follow recursive graph vert traversal order on their first path. (Trying to define this rigorously is kind of complicated, actually.) This also needs to be specified in the description.

Your solution should have linear complexity.

This is impossible: nubs is linear and not constant, so bfs can only be worst-case quadratic at best (though best-case linear is possible). And the tests will pass worst-case quadratic solutions anyway, so it is definitely not "linear complexity".

should work on infinite graphs

There is nothing told about the existence of infinite graphs in the tests. Obviously a search in infinite graphs is _|_, so clearly it is testing the laziness of something, but there is no way to know what this "something" is.

In what way are the tests deficient?

Yeah. This kata needs better documentation and better tests should be written. The mathematical theory behind this particular bijection is much more complex than should be expected of a 5 kyu.

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.

There is no added condition on this type to make it valid (like a "full" condition).

There doesn't have to be, the type you defined is a full binary tree. The definition of a regular binary tree would likely look more like:

data Tree = Maybe Tree :*: Maybe Tree

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. And since this kata is specifically about full binary trees, I don't really see the harm in mentioning that fact for clarity?

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.

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. After learning that the isomorphism is not between any binary tree, but only binary trees where every branch has exactly two children (or zero, making them leaves) ie. "full", they were able to solve. We therefore added it as clarification.

As far as I am aware, there exists no isomorphism between the set of valid parenthesis, and all binary trees. And even if there were, non-full trees are never tested in any language. Doing so would make this a considerably harder kata.