Hi, I'm the original author of this Kata (Ruby version). Author of the haskell version didn't understand this Kata properly, and indeed added a DFS version instead of BFS.

I have learned haskell to fix this. I added a BFS solution and a correct buildTree (thanks to @nickie for providing one). Please take a look again.

Thanks,
Karol

Yep, spent an hour on this until I realized that the test was broken. The test is written for pre-order traversal, not level order traversal.

Here's a buildTree that does correctly builds full binary trees out of lists in O(n).

buildTree :: [a] -> Maybe (TreeNode a)
buildTree l = fst $ walk $ split 1 l
  where split _ [] = []
        split n l = h : split (2*n) t
          where (h, t) = splitAt n l
        walk [] = (Nothing, [])
        walk ls@([] : _) = (Nothing, ls)
        walk ((h : t) : ls) = (Just $ TreeNode l r h, t : ls'')
          where (l, ls') = walk ls
                (r, ls'') = walk ls'

Please, whoever introduced the Haskell version of this kata, let's fix this!

Ugh, that's why. I didn't want to bother debugging, but this is frustrating.

@pcapriotti

That should have been totally obvious! Thanks for putting it straight.

For some reason, I wanted to see how totality would break Lambek's Lemma... but that was clearly the wrong tree to be climbing.

Looks fine to me !

The test involving sum was replaced with

  describe "Basic mapping" $ do
    it "should map" $
      shouldBe (toListOf (elements . to succ) [1,2,3]) [2,3,4 :: Int]

There is now to in the solution skeleton, but I can't reset the provided tests, so I can't check if it's in there too :(

Ah, thank you! That is a bug. I forgot to track the public test cases to the behind-the-scenes ones.

It should be fixed now, please let me know if you find any remnants. Thanks!

Not sure if the changes are supposed to be atomic, but the "commit" button does require to, and it's not in the default solution or test cases as far as I can see.

Yep, it's rather frustrating.

Wow, that one bent my mind a lot...
I'm still not sure I have it down completely, but I feel like I've leared a lot about type-level fixed points.

Nice excercise!