Memoization of Haskell Function-CodePudding

I wrote a function in Haskell to compute the determinant of a Matrix, it works just fine but is horribly slow so I tried to memoize it just like the Haskell Wiki does with the Fibonacci function.

But somehow my memoized function takes slightly longer than the non-memoized version, even when computing the determinant for the identity matrix, which should benefit very much from memoization.

I also tried using a Map for caching results but found no way to pass the modified Map to the next iteration of the recursive function.

How can I fix this?

-- Non-Memoized version
det :: (Num a, Eq a) => [[a]] -> a
det x
    | fst s == 0 = 0
    | fst s == 1 = head $ head x
    | fst s == 2 = (head (head x) * ((x !! 1) !! 1)) 
                    - ((head x !! 1) * head (x !! 1))
    | F.allEqual x = 0
    | otherwise = sum [((-1) ^ (i   1)) * head (x !! (i - 1)) 
                                        * det (sub x i 1) 
                       | i <- [1..(fst s)]]
    where
        s = shape x

-- Memoized version
mDet :: (Num a, Eq a) => [[a]] -> a
mDet x = sum [((-1) ^ (i   1)) * head (x !! (i - 1)) 
                               * det' (sub x i 1) 
              | i <- [1..(fst $ shape x)]]
    where
        det' y
            | fst s == 0 = 0
            | fst s == 1 = head $ head y
            | fst s == 2 = (head (head y) * ((y !! 1) !! 1)) 
                            - ((head y !! 1) * head (y !! 1))
            | F.allEqual y = 0
            | otherwise = mDet y
            where
                s = shape y

CodePudding user response：

There are much more efficient algorithms to compute the determinant via factorization.

Even with memoization, there are an exponential number of submatrices involved in the naive determinant formula so that's a little pointless.

CodePudding user response：

Just for reference, your function re-written to avoid the !! access becomes

-- Non-Memoized version

det :: (Num a, Eq a) => [[a]] -> a
det []  =  0
det [r] =  head r
det [r,q] =  case [r,q] of 
          [[a,b],[c,d]]  -> a*d - b*c    -- error out on wrong shape
det x | or [ or [a==b | b <- bs]         -- quadratic test
             | (a:bs) <- tails x ]       --    (must be "collinear",
        =  0  -- "any", not "all"!       --          not "==", anyway)
det x   =  sum $ [s * head r * det ([reverse a,b] >>= map tail)
                   | (a,r,b) <- picks3 x
                   | s <- cycle [1,-1]]

picks3 :: [a] -> [([a], a, [a])]
picks3 xs = unfoldr (\case {  (_,[]) -> Nothing ;
                            (a,x:xs) -> Just ((a,x,xs), (x:a,xs)) })
                    ([],xs)

There's nothing to be memoized here that's immediately apparent.