Memoization of Haskell Function

Question

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

Answer 1

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.

Answer 2

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.