In today’s Programming Praxis exercise our task is to implement four common matrix operations. The provided Scheme solution has 44 lines. Let’s see what we can do to reduce that a bit.

There are many ways to represent matrices. The most common one in Haskell (if not the most efficient if you need random access) is to use a list of lists, which is what we’ll be using here.

For addition, all we need to do is add the corresponding numbers in the two matrices together.

add :: Num a => [[a]] -> [[a]] -> [[a]]
add = zipWith $ zipWith (+)

Scaling (multiplying by a constant) is even simpler: just apply the multiplication to every element.

scale :: Num a => a -> [[a]] -> [[a]]
scale = map . map . (*)

For transposition I could’ve just used the definition from Data.List, but that would be cheating. Instead, I figured I would just use a right fold.

transpose :: [[a]] -> [[a]]
transpose [] = []
transpose xs = foldr (zipWith (:)) (repeat []) xs

Multiplying two matrices requires multiplying rows and columns. Since nested lists don’t have easy access to columns, we can use the transpose function we just defined to fix that.

mult :: Num a => [[a]] -> [[a]] -> [[a]]
mult a b = [map (sum . zipWith (*) r) $ transpose b | r <- a]

And of course we need to test if everything works correctly.

main :: IO ()
main = do let m = [[1..3],[4..6]]
let n = [[1..4], [2..5], [3..6]]
print $ add m [[2..4],[3..5]] == [[3,5,7], [7,9,11]]
print $ scale 2 m == [[2,4,6], [8,10,12]]
print $ mult m n == [[14,20..32], [32,47..77]]
print $ transpose m == [[1,4], [2,5], [3,6]]

Yep. And with a 89% reduction in line count, that’s good enough for me.

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, Haskell, kata, matrices, matrix, praxis, programming

This entry was posted on June 22, 2010 at 1:13 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

July 12, 2013 at 7:22 am |

Scheme doesn’t have to be that long and ugly though. Here’s a Racket version that’s almost as short as the Haskell:

(define add (curry map (curry map +)))

; pretty much the same as the Haskell version, except with explicit instead of implicit currying. As a bonus, since map has variable arity, you can use this to add together any number of matrices

(define (scl s m) (map (curry map (curry * s)) m))

; same ideas as the Haskell one, but much uglier :)

(define transpose (curry apply map list))

; I think this one wins for elegance … again taking advantage of scheme’s support for variable arity in map

(define (mult as bs)

(for/list ([a as])

(for/list ([b (transpose bs)])

(apply + (map * a b)))))

; not as short as Haskell, but I think it is much clearer what this is doing … you can see it de-structuring the matrix into rows and columns then piecing it back together. Granted, you could easily write essentially the same code in Haskell with a nested list comprehension