Skip to content

Instantly share code, notes, and snippets.

@dagit
Created February 17, 2017 18:02
Show Gist options
  • Save dagit/dfd908b0c6a1419f4d7ba7c394feead8 to your computer and use it in GitHub Desktop.
Save dagit/dfd908b0c6a1419f4d7ba7c394feead8 to your computer and use it in GitHub Desktop.
Division-free determinant for Integer matrices
-- This is a direct copy&paste from Bird's Pearls of Functional Algorithm Design
import Data.List (transpose)
trimult xss yss = zipWith (map . dp) xss (submats (transpose yss))
submats :: [[a]] -> [[[a]]]
submats [[x ]] = [[[x ]]]
submats xss = xss : submats (map tail (tail xss))
dp xs ys = sum (zipWith (*) xs ys)
mut xss = zipWith (:) ys (map tail xss)
where ys = map negate (tail (scanr (+) 0 (map head xss)))
det :: [[Integer ]] -> Integer
det ass = head (head bss)
where
bss = foldl (trimult . mut) ass' (replicate (n - 1) ass)
ass' = if odd n then upper ass else map (map negate) (upper ass)
n = length ass
upper = zipWith drop [0..]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment