Created
December 31, 2025 22:35
-
-
Save franklindyer/b3c0ede8f5887b92ace4f59c0327972d to your computer and use it in GitHub Desktop.
Central groupoid functions in Haskell
This file contains hidden or 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
| import Control.Monad | |
| import Data.Function | |
| import Data.List | |
| import Data.Maybe | |
| import System.IO | |
| import System.IO.Unsafe | |
| -- Type of central groupoids | |
| type CG = [([Int], [Int])] | |
| --- UTILITY FUNCTIONS --- | |
| -- Count occurrences of each element in a list | |
| counts :: Eq a => [a] -> [(a, Int)] | |
| counts xs = map (\x -> (x, length $ filter (== x) xs)) (nub xs) | |
| -- Group actions of order up to 4 | |
| data GrpAxn4 | |
| = GrpTriv | |
| | GrpZ2Swap1 | |
| | GrpZ2Swap2 | |
| | GrpZ3 | |
| | GrpVTrans | |
| | GrpVIntrans | |
| | GrpZ4 | |
| | GrpS3 | |
| | GrpD4 | |
| | GrpA4 | |
| | GrpS4 | |
| deriving (Eq, Show) | |
| -- Execute a permutation given a list of images of each point | |
| doPerm :: [(Int, Int)] -> Int -> Int | |
| doPerm sigma i = fromJust $ lookup i sigma | |
| -- Get the number of fixpoints of a permutation | |
| permNumFixPts :: [(Int, Int)] -> Int | |
| permNumFixPts sigma = length $ filter (uncurry (==)) sigma | |
| -- Compose the list representations of 2 permutations | |
| composePerms :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)] | |
| composePerms s1 s2 = map (\(x, y) -> (x, doPerm s2 y)) s1 | |
| -- Given a group of permutations of order up to 4, classify it | |
| classifyGrpAxn4 :: [[(Int, Int)]] -> GrpAxn4 | |
| classifyGrpAxn4 sigma | |
| | length sigma == 1 = GrpTriv | |
| | length sigma == 2 = | |
| if (sort (map permNumFixPts sigma) == [0,4]) | |
| then GrpZ2Swap2 | |
| else GrpZ2Swap1 | |
| | length sigma == 3 = GrpZ3 | |
| | length sigma == 4 = | |
| if (sort (map permNumFixPts sigma) == [0,2,2,4]) | |
| then GrpVIntrans | |
| else if (all (\s -> map snd (composePerms s s) == [1,2,3,4]) sigma) | |
| then GrpVTrans | |
| else GrpZ4 | |
| | length sigma == 6 = GrpS3 | |
| | length sigma == 8 = GrpD4 | |
| | length sigma == 12 = GrpA4 | |
| | length sigma == 24 = GrpS4 | |
| -- Close a list under a given binary operation | |
| closure2 :: Ord a => (a -> a -> a) -> [a] -> [a] | |
| closure2 op ls = sort $ f [] ls | |
| where | |
| iter s = foldl | |
| (\s0 (x, y) -> if elem (op x y) s0 then s0 else (op x y):s0) | |
| s | |
| [(x, y) | x <- s, y <- s] | |
| f cls cls' = if cls' == cls then cls else f cls' (iter cls') | |
| -- Given the images of an isomorphism on a few values, | |
| -- deduce its values at all other values generated by those | |
| deduceIsoFromGenerators :: (Ord a, Ord b) => (a -> a -> a) -> (b -> b -> b) -> [(a, b)] -> [(a, b)] | |
| deduceIsoFromGenerators op1 op2 vals = f [] vals | |
| where | |
| iter s = foldl | |
| (\s0 ((a1, b1), (a2, b2)) -> if elem (op1 a1 a2) (map fst s0) then s0 else (op1 a1 a2, op2 b1 b2):s0) | |
| s | |
| [(x, y) | x <- s, y <- s] | |
| f cls cls' = if cls' == cls then cls else f cls' (iter cls') | |
| --- CENTRAL GROUPOIDS --- | |
| -- Get cardinality of a central groupoid | |
| cgSize :: CG -> Int | |
| cgSize cg = sum $ map (length . snd) cg | |
| -- Get central groupoid operation | |
| cgMul :: CG -> Int -> Int -> Int | |
| cgMul cg x y = (filter (`elem` s1) s2) !! 0 | |
| where | |
| s1 = fst ((filter (\t -> elem x (snd t)) cg) !! 0) | |
| s2 = concat [snd t | t <- cg, elem y (fst t)] | |
| -- Get dual of a central groupoid (reverse order of operation) | |
| cgDual :: CG -> CG | |
| cgDual cg = [(pt, map fst $ filter (\(i, s) -> sort s == sort pt) cgsets) | pt <- parts] | |
| where | |
| n = cgSize cg | |
| cgsets = [(i, concat (map snd $ filter (\(s, _) -> elem i s) cg)) | i <- [1..n]] | |
| parts = nub (map snd cgsets) | |
| cgPi1 :: CG -> Int -> Int | |
| cgPi1 cg x = (x `op` x) `op` x | |
| where | |
| op = cgMul cg | |
| cgPi2 :: CG -> Int -> Int | |
| cgPi2 cg x = x `op` (x `op` x) | |
| where | |
| op = cgMul cg | |
| cgPoint :: CG -> Int -> (Int, Int) | |
| cgPoint cg x = (cgPi1 cg x, cgPi2 cg x) | |
| cgCoords :: CG -> [(Int, Int)] | |
| cgCoords cg = map (cgPoint cg) [1..n] | |
| where | |
| n = cgSize cg | |
| cgDeviations :: CG -> [((Int, Int), (Int, Int), (Int, Int))] | |
| cgDeviations cg = filter (\(xc, yc, zc) -> zc /= (snd xc, fst yc)) prods | |
| where | |
| n = cgSize cg | |
| coords = zip [1..n] (cgCoords cg) | |
| prods = [(xc, yc, cgPoint cg (cgMul cg x y)) | (x, xc) <- coords, (y, yc) <- coords] | |
| -- Get idempotent elements of a central groupoid | |
| cgIdemps :: CG -> [Int] | |
| cgIdemps cg = filter (\x -> x == cgMul cg x x) [1..(cgSize cg)] | |
| -- Get elements of a central groupoid that are a product of idempotents | |
| cgIdempProds :: CG -> [Int] | |
| cgIdempProds cg = sort $ nub [cgMul cg x y | x <- idemps, y <- idemps] | |
| where | |
| idemps = cgIdemps cg | |
| -- Get elements of a central groupoid that are not a product of idempotents | |
| cgNonIdempProds :: CG -> [Int] | |
| cgNonIdempProds cg = filter (not . (`elem` idp)) [1..n] | |
| where | |
| n = cgSize cg | |
| idp = cgIdempProds cg | |
| -- Ensure that a (supposed) central groupoid obeys the equational law | |
| verifyCG :: CG -> Bool | |
| verifyCG cg = and [y == op (op x y) (op y z) | x <- [1..n], y <- [1..n], z <- [1..n]] | |
| where | |
| n = length $ concatMap snd cg | |
| op = cgMul cg | |
| cgDeduplicate :: CG -> CG | |
| cgDeduplicate cg = sortBy (compare `on` (minimum . snd)) [(lSet, sort $ concat $ map snd $ filter (\(lSet', rSet) -> sort lSet' == lSet) cg) | lSet <- lSets ] | |
| where | |
| lSets = filter (/= []) $ nub $ map (sort . fst) $ filter (\pr -> snd pr /= []) cg | |
| -- Check that a mapping is an isomorphism of central groupoids | |
| cgIsIso :: CG -> CG -> (Int -> Int) -> Bool | |
| cgIsIso cg1 cg2 f = and [op2 (f x) (f y) == f (op1 x y) | x <- [1..n], y <- [1..n]] | |
| where | |
| n = cgSize cg1 | |
| op1 = cgMul cg1 | |
| op2 = cgMul cg2 | |
| cgFindIdempPerms :: CG -> CG -> [[(Int, Int)]] | |
| cgFindIdempPerms cg1 cg2 = filter mappingGivesIso closedSets | |
| where | |
| idemps1 = cgIdemps cg1 | |
| idemps2 = cgIdemps cg2 | |
| startingSets = map (zip idemps1) (permutations idemps2) | |
| closedSets = map (deduceIsoFromGenerators (cgMul cg1) (cgMul cg2)) startingSets | |
| mappingGivesIso ss = cgIsIso cg1 cg2 (\x -> fromJust (lookup x ss)) | |
| -- Get automorphisms of a central groupoid in permutation list representation | |
| cgFindAutos :: CG -> [[(Int, Int)]] | |
| cgFindAutos cg = cgFindIdempPerms cg cg | |
| -- Get automorphisms of a central groupoid restricted to idempotent elements | |
| cgFindIdempAutos :: CG -> [[(Int, Int)]] | |
| cgFindIdempAutos cg = map (\sigma -> [(idempInd i, idempInd j) | (i, j) <- sigma, elem i idemps]) autos | |
| where | |
| autos = cgFindAutos cg | |
| idemps = cgIdemps cg | |
| idempInd = fromJust . (\i -> lookup i (zip idemps [1..])) | |
| -- Check isomorphism of 2 central groupoids | |
| cgIso :: CG -> CG -> Bool | |
| cgIso cg1 cg2 = length (cgFindIdempPerms cg1 cg2) > 0 | |
| -- Calculate number of elements of a central groupoid that are not a product of idempotents | |
| cgDeficiency :: CG -> Int | |
| cgDeficiency cg = cgSize cg - length (nub $ cgIdempProds cg) | |
| -- Get the sizes of the sub-central-groupoids generated by each element of a central groupoid | |
| cgOrders :: CG -> [Int] | |
| cgOrders cg = map (length . closure2 (cgMul cg) . singleton) [1..n] | |
| where | |
| n = cgSize cg | |
| cgOrderCounts :: CG -> [Int] | |
| cgOrderCounts cg = [length (filter (== (k^2)) orders) | k <- [1..sqn]] | |
| where | |
| n = cgSize cg | |
| sqn = length $ cgIdemps cg | |
| orders = cgOrders cg | |
| -- Get the system of "local coordinates" induced by a central groupoid element | |
| cgLocalGrid :: CG -> Int -> ([[Int]], [[Int]]) | |
| cgLocalGrid cg alpha = (rows, cols) | |
| where | |
| n = cgSize cg | |
| op = cgMul cg | |
| lc = sort $ nub $ map (alpha `op`) [1..n] | |
| rc = sort $ nub $ map (`op` alpha) [1..n] | |
| rows = sortBy (compare `on` minimum) [sort [op i j | j <- rc] | i <- lc] | |
| cols = sortBy (compare `on` minimum) [sort [op i j | i <- lc] | j <- rc] | |
| -- Get the number of incompatible systems of local coordinates in a central groupoid | |
| cgLocalGridCounts :: CG -> [Int] | |
| cgLocalGridCounts cg = sort $ [length $ filter (== grid) localGrids | grid <- distLocalGrids] | |
| where | |
| n = cgSize cg | |
| localGrids = map (cgLocalGrid cg) [1..n] | |
| distLocalGrids = nub localGrids | |
| cgNumLocalGrids :: CG -> Int | |
| cgNumLocalGrids cg = length $ nub $ map (cgLocalGrid cg) [1..(cgSize cg)] | |
| cgLSwapCands :: CG -> [(Int, Int)] | |
| cgLSwapCands cg | |
| = [(i, j) | i <- [1..n], j <- [1..n], i /= j && all (\ls -> elem i ls == elem j ls) (map fst cg)] | |
| where | |
| n = cgSize cg | |
| cgRSwapCands :: CG -> (Int, Int) -> [(Int, Int)] | |
| cgRSwapCands cg (alpha, beta) | |
| = [(i, j) | i <- lsA, j <- lsB, length (filter (\ls -> elem i ls && elem j ls) (map snd cg)) > 0 && (not $ elem i [alpha, beta]) && (not $ elem j [alpha, beta])] | |
| where | |
| n = cgSize cg | |
| lsA = fst ((filter (\r -> elem alpha (snd r)) cg) !! 0) | |
| lsB = fst ((filter (\r -> elem beta (snd r)) cg) !! 0) | |
| cgAllSwapCands :: CG -> [(Int, Int, Int, Int)] | |
| cgAllSwapCands cg = [(a, b, c, d) | (a, b) <- cgLSwapCands cg, (c, d) <- cgRSwapCands cg (a, b) ] | |
| cgDoSwap :: CG -> (Int, Int, Int, Int) -> CG | |
| cgDoSwap cg (alpha, beta, gamma, delta) | |
| = cgDeduplicate (newRows ++ map (\(ls1, ls2) -> (ls1, filter (\j -> not $ elem j [alpha, beta]) ls2)) cg) | |
| where | |
| swapper j = if j == gamma then delta else if j == delta then gamma else j | |
| lsA = fst ((filter (\r -> elem alpha (snd r)) cg) !! 0) | |
| lsB = fst ((filter (\r -> elem beta (snd r)) cg) !! 0) | |
| newRows = [(map swapper lsA, [alpha]), (map swapper lsB, [beta])] | |
| cgAddIfNotIso :: CG -> [CG] -> [CG] | |
| cgAddIfNotIso cg cgs = if (any (cgIso cg) cgs) then cgs else cgs ++ [cg] | |
| data CGInfo = CGInfo { | |
| cg :: CG, | |
| numLSets :: Int, | |
| rSetLens :: [Int], | |
| deficiency :: Int, | |
| orderCounts :: [Int], | |
| localGridCounts :: [Int], | |
| selfDual :: Bool, | |
| autoGrp :: GrpAxn4 | |
| } deriving (Eq) | |
| instance Show CGInfo where | |
| show cgi | |
| = "{\"table\": " ++ show (map (\r -> [fst r, snd r]) (cg cgi)) | |
| ++ ", \"numLSets\": " ++ show (numLSets cgi) | |
| ++ ", \"rSetLens\": " ++ show (rSetLens cgi) | |
| ++ ", \"deficiency\": " ++ show (deficiency cgi) | |
| ++ ", \"orderCounts\": " ++ show (orderCounts cgi) | |
| ++ ", \"localGridCounts\": " ++ show (localGridCounts cgi) | |
| ++ ", \"selfDual\": " ++ (if selfDual cgi then "true" else "false") | |
| ++ ", \"autoGrp\": " ++ show (show $ autoGrp cgi) | |
| ++ "}" | |
| cgInfo :: CG -> CGInfo | |
| cgInfo cg = CGInfo { | |
| cg = cg, | |
| numLSets = length cg, | |
| rSetLens = sort $ map (length . snd) cg, | |
| deficiency = cgDeficiency cg, | |
| orderCounts = cgOrderCounts cg, | |
| localGridCounts = cgLocalGridCounts cg, | |
| selfDual = cgIso cg (cgDual cg), | |
| autoGrp = classifyGrpAxn4 (cgFindIdempAutos cg) | |
| } | |
| cgQuickIso :: CGInfo -> CGInfo -> Bool | |
| cgQuickIso cgi1 cgi2 | |
| = rSetLens cgi1 == rSetLens cgi2 | |
| && numLSets cgi1 == numLSets cgi2 | |
| && deficiency cgi1 == deficiency cgi2 | |
| && orderCounts cgi1 == orderCounts cgi2 | |
| && localGridCounts cgi1 == localGridCounts cgi2 | |
| && selfDual cgi1 == selfDual cgi2 | |
| && autoGrp cgi1 == autoGrp cgi2 | |
| && cgIso (cg cgi1) (cg cgi2) | |
| cgCrawler :: Int -> [CG] -> IO [CGInfo] | |
| cgCrawler m cgs = do | |
| hPutStr outF "[" | |
| sequence (fmap (hPutStr outF . (++ ",") . show . cgInfo) cgs) | |
| res <- (fmap snd $ rec (0, map cgInfo cgs)) | |
| hPutStr outF "]" | |
| hClose outF | |
| return res | |
| where | |
| outF = unsafePerformIO $ openFile ("crawled" ++ show (cgSize (cgs !! 0)) ++ ".json") WriteMode | |
| cgAdder :: [CGInfo] -> CGInfo -> IO [CGInfo] | |
| cgAdder cgis cgi = if (any (cgQuickIso cgi) cgis) then return cgis else (hPutStr outF (show cgi ++ ",")) >> return (cgis ++ [cgi]) | |
| -- cgAdder cgis cgi = if (any (cgQuickIso cgi) cgis) then return cgis else return (cgis ++ [cgi]) | |
| rec :: (Int, [CGInfo]) -> IO (Int, [CGInfo]) | |
| rec (l, cgis) = | |
| if l >= (min (length cgis) m) | |
| then return (l, cgis) | |
| else do | |
| let cgi = cgis !! l | |
| cgis' <- foldM cgAdder cgis (map (cgInfo . cgDoSwap (cg cgi)) (cgAllSwapCands (cg cgi))) | |
| putStrLn ("DONE WITH ITERATION: " ++ show l ++ ", LENGTH " ++ show (length cgis')) | |
| rec (l+1, cgis') | |
| -- Get natural central groupoid of a given order | |
| cgNat :: Int -> CG | |
| cgNat n = [([((r-1)*n+1)..(r*n)], map (\i -> (mod (n*i) n2)+r) [0..(n-1)]) | r <- [1..n] ] | |
| where | |
| n2 = n ^ 2 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment