Miguel Mitrofanov miguelimo38 at yandex.ru
Mon Sep 24 13:13:38 EDT 2007

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