Created
February 17, 2017 18:02
-
-
Save dagit/dfd908b0c6a1419f4d7ba7c394feead8 to your computer and use it in GitHub Desktop.
Division-free determinant for Integer matrices
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- 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