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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
