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.

...

Because transpose is quite lazy, it need not necessarily result in a quadratic time complexity on every use.

On the other hand, my program needs the entire transposed list, so... ;-)

May be, you should consider some other data structures, for example (borrowed from fido7.ru.math):

data Matrix a = M a [a] [a] (Matrix a) | MEmpty

Here M x ys zs m is a matrix with x in it's upper left corner, ys as it's first row (without x), zs as it's first column (also without x) and m as a remaining submatrix. For example, 1 2 3 4 5 6 is represented as M 1 [2,3] [4] (M 5 [6] [] MEmpty) It takes linear time to transpose these matrices:

transpose (M x ys zs m) = M x zs ys $ transpose m

It's also relatively easy to add these matrices (do it yourself, please), multiply a matrix by a column:

MEmpty `mColMult` ts = map (const 0) ts M x ys zs m `mColMult` (t:ts) = (x*t + sum (zipWith (*) ys ts)) : zipWith (+) (map (* t) zs) (m `mColMult` ts)

and multiply matrices:

M x ys zs m `mMult` M x' ys' zs' m' = M (x * x' + sum (zipWith (*) ys zs')) (zipWith (+) (map (x *) ys') (transpose m' `mColMult` ys)) (zipWith (+) (map (* x') zs) (m `mColMult` zs)) $ (m `mMult` m') `mAdd` (zs `multColRow` ys') where [] `multColRow` _ = mEmpty _ `multColRow` [] = mEmpty (z:zs) `multColRow` (y:ys) = M (z * y) (map (z *) ys) (map (* y) zs) (zs `multColRow` ys)

Hope this helps.