2
\$\begingroup\$

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?"

\$\endgroup\$
3
\$\begingroup\$

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(n2) 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.

\$\endgroup\$
1
  • \$\begingroup\$ @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]) ...). \$\endgroup\$ – Will Ness May 24 '13 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.