Recursive Determinant

Question

The following code I devised to compute a determinant:

module MatrixOps where

determinant :: (Num a, Fractional a) => [[a]] -> a
determinant [[x]] = x
determinant mat =
 sum [s*x*(determinant (getRest i mat)) | i <- [0..n-1], let x = (head mat) !! i
                                                             s = (-1)^i]
 where n = length $ head mat

getRest :: (Num a, Fractional a) => Int -> [[a]] -> [[a]]
getRest i mat = removeCols i (tail mat)

removeCols :: (Num a, Fractional a) => Int -> [[a]] -> [[a]]
removeCols _ [] = []
removeCols i (r:rs) = [r !! j | j <- [0..n-1], j /= i] : removeCols i rs
 where n = length r

I have a few general questions about the style of my code and practices:

• Is a very "Haskell" solution? I come from an OOP background and I am still learning functional programming.

• Is there a better way to space this out? I feel like some of the code is not very readable (this may just be because I am new), especially the definition of determinant mat = ...

• Is this code considerably "clean?"

Answer 1

Just a few thoughts:

• Your method (IIUC) is conceptually correct, but has computation complexity O(n!) where n is the dimension of a given matrix. If you need better complexity (polynomial in n), you have to use another solution, such as using PLU decomposition described here.

• Be aware that since Haskell lists are essentially linked lists, getting i-th element using (!!) takes O(i). So your code

  [r !! j | j <- [0..n-1], j /= i] 
  

  has O(n²) complexity. You could express it in O(n) for example using splitAs as

  let (left, right) = splitAt i r
   in left ++ (tail right)
  

  The same applies for i <- [0..n-1], let x = (head mat) !! i. You could do something like

  (i, x) <- zip [0..] (head mat)
  

  instead.