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.

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

You don't need to go low level or recursive for it though, just save the lengths in a tuple instead of recomputing them.

Admittedly, my solution pulled in Arrows, which is also kinda silly.

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

Wouldn't this have a pretty terrible time complexity? The lengths are not going to be cached, right?