CODEWITHSUNDEEP
haskellmatrixfunctional-programming
Jeremy Knees
Jeremy Knees

Reputation: 662

Update Matrix Haskell

I will represent matrices in a project by a list of lists [[a]]

Upvotes: 1

Views: 1142

Answers (3)

Landei
Landei

Reputation: 54574

How about using your own data type wrapping a Map (Int,Int) a? Changing an element is trivial, and especially for sparse matrices you save a lot of memory.

Upvotes: 5

leftaroundabout
leftaroundabout

Reputation: 120711

Of course, list-based solutions are never as fast as optimised tight arrays because of the necessary indirections, with all its cache-locality problems. However, that's only a constant overhead factor (possibly quite big though, something in the order of 100).

However, interestingly, the nested-list approach to matrices is not quite as bad as it may seem: lists remain the data structure that's most naturally dealt with in a traditional purely-functional manner. As said by millimoose, you cannot just change an element in-place in a pure way, you have to make a copy of the whole thing with one element changed*. For n ✕ n tight-array matrices, this is O (n2) – hardly acceptable for larger n.

While random access in a list of length m is already O (m) and thus much worse than for arrays, it doesn't get any worse for more complex operations. You can "modify" a list in O (m), you can access an n ✕ n nested list in O (n), and you can modify it in O (n)! So if you want to do nondestructive updates on large matrices, [[a]] is actually faster than Array a i.

Oh, how this works – well, something like

type Matrix a = [[a]]
updateMatrixAt :: (Int,Int) -> (a->a) -> Matrix a -> Matrix a
updateMatrixAt(i,j) f mat
 | (upperRows, thisRow : lowerRows ) <- splitAt i mat
 , (leftCells, thisCell: rightCells) <- splitAt j thisRow
         =                  upperRows
          ++ (leftCells ++ (f thisCell): rightCells)
                          : lowerRows
 | otherwise = error "Tried to index matrix outside range"

will do the trick.

*There have been attempts to avoid this, but I'm afraid this has proven a dead end. If you want really high performance, you should use destructive updates in the ST monad, there's nothing wrong with it though it may not be quite as nice.

Upvotes: 9

millimoose
millimoose

Reputation: 39950

How do I change the element on place with index (i,j)?

Generally speaking, you can't. You have to create a new matrix with the one element changed. (Using Array instead of a list would make this slightly easier with the // operator.) It seems like you could use MArray to do in-place changes, but then pretty much all your code would have to use IO.

Upvotes: 0

Related Questions