[Haskell-cafe] Complexity question

[Miguel Mitrofanov]

>> 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.