Matrix division in Haskell

Question

What is wrong? This code is supposed to do matrix division by finding a times b inverse. I try to understand what its errors are but I fail to see how to link it.

import List
import Ratio

inverse :: [[Rational]] -> [[Rational]]
inverse mat = sweep ([], zipWith (++) mat unit) where
    unit = map (take (length mat)) $ iterate (0 :) (1 : [0,0..])
    sweep (xss, []) = xss
    sweep (xss, yss) = sweep (xss' ++ [ws], filter (any (/= 0)) yss') where
        Just (x : xs) = find ((/= 0) . head) yss
        ws = map (/ x) xs
        [xss', yss'] = map (map f) [xss, yss]
        f (y : ys) = zipWith (d e -> e - d * y) ws ys

How can I link it with

import Data.Array

mmult :: (Ix i, Num a) => Array (i, i) a -> Array (i, i) a -> Array (i, i) a 
mmult x y 
    | x1 /= y0 || x1' /= y0'  = error "range mismatch"
    | otherwise               = array ((x0, y1), (x0', y1')) l where
        ((x0, x1), (x0', x1')) = bounds x
        ((y0, y1), (y0', y1')) = bounds y
        ir = range (x0, x0')
        jr = range (y1, y1')
        kr = range (x1, x1')
        l  = [((i, j), sum [x ! (i, k) * y ! (k, j) | k <- kr

to do matrix division by multiplying a and b's inverse.

Answer 1

There seem to be a couple problems here. First of all, the definition of l in mmult seems to be incomplete. You start a list and start a pair, but never close them. Perhaps you meant:

l = [((i, j), sum [x ! (i, k) * y ! (k, j) | k <- kr]) | i <- ir, j <- jr]

The other problem that is inherent in, as you put it, linking those two modules, is that you are using different types for matricies in the two modules. The first one, where you invert a matrix, treats it as a list of lists. The second one, which multiplies two matricies, uses arrays. To combine the two, you need to be able to convert between the representations. Essentially, you need two operations:

fromListMatrix :: [[Rational]] -> Array (Int, Int) Rational
toListMatrix :: Array (Int, Int) Rational -> [[Rational]]

Once you have these, you can implement matrix division pretty easily.

divideMatrix :: Array (Int, Int) Rational -> Array (Int, Int) Rational -> Array (Int, Int) Rational
divideMatrix a b = mmult a (fromListMatrix (invert (toListMatrix b)))

On the implementation front, let's start with toListMatrix, as it is easier.

toListMatrix mat =

Now, we're going to need the bounds of the array, so

toListMatrix mat = let ((x0, x1), (x0', x1')) = bounds mat in

We will construct it row by row:

toListMatrix mat = let ((x0, x1), (x0', x1')) = bounds mat in
    [row | rowNum <- range (x1, x1')]

Each row is simply the elements of the matrix with a fixed row number:

toListMatrix mat = let ((x0, x1), (x0', x1')) = bounds mat in
    [[mat ! (pos, rowNum) | pos <- range (x0, x0')] | rowNum <- range (x1, x1')]

Moving on to fromlistMatrix:

fromListMatrix mat =

We want to associate each element with a position, and then feed the result to array, so:

fromListMatrix mat = array ((1, 1), (length (head mat), length mat)) indexedElems where
    indexedElems =

First we need to get the row numbers in place, so:

fromListMatrix mat = array (length (head mat), length mat) indexedElems where
    indexedElems = someFunction (zip [1..] mat)

Then we put in the position numbers:

fromListMatrix mat = array (length (head mat), length mat) indexedElems where
    indexedElems = someFunction (map addPositions (zip [1..] mat))
    addPositions (rowNum, elems) = zip [(pos, rowNum) | pos <- [1..]] elems

Now we have a list of rows of the indexed elements. We need to concatenate this into a single list:

fromListMatrix mat = array (length (head mat), length mat) indexedElems where
    indexedElems = concat (map addPositions (zip [1..] mat))
    addPositions (rowNum, elems) = zip [(pos, rowNum) | pos <- [1..]] elems

Finally, we clean up the code by changing map addPositions (zip [1..] mat) into a simpler form with zipWith:

fromListMatrix mat = array (length (head mat), length mat) indexedElems where
    indexedElems = concat (zipWith addPositions [1..] mat)
    addPositions rowNum elems = zip [(pos, rowNum) | pos <- [1..]] elems

You're done!