Andrew Coppin:
Anybody happen to know what the time complexity of "transpose" is?
Bas van Dijk:
The worst case time complexity is O(r*c) where 'r' are the number of rows and 'c' are the number of columns.
I believe Bas is correct, though it might be worth elaborating on what he means by "worst case". Because transpose is quite lazy, it need not necessarily result in a quadratic time complexity on every use. For a trivial example, (sum . map head) could be replaced with (sum . head . transpose), without affecting the linear time complexity. In fact, because of its laziness, you can pretty much ignore applications of transpose when working out *asymptotic* complexities, because transpose will never do any more damage than the functions which consume its result. Of course, whether you do ignore it will depend on how much you care about the constant factor.