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.

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.

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.

Personally, I love Haskell (as a hobby / pet language) for the ability to express myself very naturally and mathematically (or functionally, if you will), compared to the more imperative way of implementing the functions at a "lower level", so to speak. To design algorithms and leave the implementation to the compiler, perhaps? Sure, this won't win any awards in a fight against say, highly-optimized C or assembly-code that is specifically crafted against this particular problem- but the higher abstraction levels allow excellent readability for potential future lookenspeepers who might make minute changes to complete a task somewhat similar yet different in details. And who knows - maybe in the near future we might have even smarter compilers which could optimize the implementation to have less recomputations? We already have the magic of laziness today :)

yeah, probably. I, at least, didn't feel like writing a boring-but-efficient low-level recursive solution :p