Each length is calculated twice, so I can't even tell without testing if caching would help or not. And the complexity is just O(n * log n), the group lengths are not independent of the list length, they are made of the same items.

It has approximate time complexity O(n log n). ( I already thought so. But I checked. ) Your C or assembly solution might have time complexity O(n), but will very, very probably also have O(n log n).

No, length is not cached. But even without, time complexity is something like (O m n log n) with m the length of the longest group. That's approximately a small constant except in extreme cases. Caching length would be a good thing here.

Ah, that's true, and is a nasty edge case for some solutions. It would be nice to add, but tests are now locked because too many people have completed the kata.

That is certainly the primary conceptual hurdle I'm throwing at people attempting the kata. I don't want to give up the ghost immediately, but I would certainly entertain ideas about how to hint in the right direction without removing the opportunity for the person trying to kata to discover the trick on their own.

Alternatively, it might just need to have an elevated rank.

Thanks! Fixed.

There is a typo in the test case.

 describe "append works" $ do
    prop "should work the same as consDumb" $ \l l' -> 

Unfortunately I don't know a way to enforce it without making the types more complex (see bartavelle's suggestion below), but the right answer (which you solution is an instance of) is perhaps the most beautiful way to solve it.

It doesn't fit perfectly with other code kata which have absolute answers. It's more like a nice math exercise where the right answer is whichever one brings you the greatest enlightenment.

How do I know if I did it the inteded way?

While I agree that writing the individual lenses feel a bit abstract, I thought that writing over and set gives an excellent hint on how the machinery works.

A profunctor (not a protofunctor) is something looks like a bifunctor (like (,) or Either), except the first argument is contravariant (if that means something). My intuition for it is that Profunctor p => p a b represents somethings that "consumes" an a and "produces" a b, for example a -> b. With lmap you can "adapt the source" and rmap changes the output, like fmap.

I think a "witness" is just another word for a piece of code that serves as a proof.

But all the lens stuff is crazy category theory stuff, so I suppose you need to learn some of it if you want to grok it.

Bleh. I didn't know lenses before I started, and I still dont know how most of the lensy things I just wrote work. This was frustrating; basically just blindly following types, with no intuition. What is a Protofunctor? What is a "witness"? Some crazy category theory stuff I guess?

Towards the end of it, I was just motivated by sunk cost (and wanting to complain about how annoying it was).

The last Iso problem is untested (so I could have left it blank), and I have no idea what "coerce" was about but it seemed to be happy with it as bottom, so I didn't touch it.

Side note: Either is not traversable in this version of haskell, so I implemented it myself.

The instructions are not clear for someone who has not played bowling before. Specifically, I could not figure out how 2 or 3 balls are chosen in the 10th frame, and had to go spend a half hour looking up rules.

I suggest adding something like this:

If the player gets a strike on the tenth frame, they get two bonus balls, that only count towards the bonus score for that strike, not towards a frame score. Similarly, if they get a spare, they get one such bonus ball.

This was rather frustrating to deal with, and has nothing to do with programming.