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