How to rewrite this haskell function using folds?

Question

I wrote a haskell function to calculate the determinant of a matrix:

determinant :: Matrix -> Int
determinant [] = 0
determinant [[k]] = k
determinant n = sum [((-1) ^ m) * (head n !! m) * determinant (removeColumn (drop 1 n) m) | m <- [0 .. l]]
  where
    l = length (head n) - 1

It uses the helper function 'removeColumn' to extract the columns:

removeColumn :: Matrix -> Int -> Matrix
removeColumn m n = map (\row -> take (n-1) row ++ drop n row) m

I want to try to rewrite the 'determinant' function using folds. I have been brainstorming for a while but I can't think of how to start. Any help would be appreciated.

Answer 1

It's difficult to convert your version without changing it fundamentally, because it uses an irregular recursion scheme. For folds you would want your function to have a basic structure like this for some z and k:

determinant [] = z
determinant (x : xs) = k x (determinant xs)

Your functions recurses on determinant (removeColumn (drop 1 n) m), so it is not obviously compatible.

Instead of starting with your function, I have taken the liberty to write an implementation based on the Leibniz formula from Wikipedia:

import Data.Bifunctor (first, bimap)

-- e.g. insertEverywhere 0 [1,2] == [(0,[0,1,2]),(1,[1,0,2]),(2,[1,2,0])]
-- the tupled integer keeps track of the number of inversions
insertEverywhere :: a -> [a] -> [(Int, [a])]
insertEverywhere x = 
  (\(ys,yss) -> (0,(x:ys)):yss) 
    . foldr 
      (\y (ys1,ys2) -> (y:ys1, (1, y:x:ys1):map (bimap (+ 1) (y:)) ys2))
      ([], [])

permutations :: [a] -> [(Int, [a])]
permutations = 
  foldr 
    (\x xs -> concatMap (\(n, xs) -> map (first (+ n)) (insertEverywhere x xs)) xs) 
    [(0, [])]

determinant :: Num a => [[a]] -> a
determinant = 
  sum 
    . map (\(i,p) -> (-1) ^ i * product (zipWith (!!) p [0..]))
    . perms

I'd say the essential part of this implementation is the use of the permutations as an intermediate structure (tupled with the number of inversions).