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.

• Will Ness: @mjgpy3 to add the oscillating sign there, (i, sx) <- zip [0..] (zipWith (*) (cycle [1,-1]) $ head mat) can be used. Or (zipWith ($) (cycle [id, negate]) ...).