Programming Praxis – Matrix Operations

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.

About these ads

Tags: , , , , , , ,

One Response to “Programming Praxis – Matrix Operations”

  1. Ord Says:

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: