Skip to content

Instantly share code, notes, and snippets.

@franklindyer
Created December 31, 2025 22:35
Show Gist options
  • Select an option

  • Save franklindyer/b3c0ede8f5887b92ace4f59c0327972d to your computer and use it in GitHub Desktop.

Select an option

Save franklindyer/b3c0ede8f5887b92ace4f59c0327972d to your computer and use it in GitHub Desktop.
Central groupoid functions in Haskell
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