Symmetric Relation in Haskell

Question

I'm working with relations and I want to find whether a relation is symmetric.

To find that a relation is symmetric, we need to find two tuples such that: [(a,b), (b,a)].

This is what I've got so far:

simmetry:: Eq a => [(a,a)] -> [a]
simmetry [] = []
simmetry (x:xs)
            | (fst x `elem` map snd xs) && (snd x `elem` map fst xs) = fst x : (simmetry xs)
            | otherwise = simmetry xs

What this function does is, it grabs a tuple x and checks that it finds its first element in another tuple as the second position, as well as checking that the second element is in another tuple as the first position.

However I'm missing out on the part where I have to check that the other tuple is the same one for both conditions. With my code, something like this: [(a,b),(b,c),(d,a)] would work.

P.D: simmetry returns [a] for testing purposes.

I'm out of ideas, any tips are highly appreciated!

question from:https://stackoverflow.com/questions/65953083/symmetric-relation-in-haskell

Answer 1

What you want to check is: for every tuple (x,y) in the list, (y,x) should also be present. You can express that quite directly in Haskell:

isSymmetric :: Eq a => [(a,a)] -> Bool
isSymmetric l = all ((x,y) -> (y,x)`elem`l) l

This is actually doing some redundant work because it always also goes over (x,y) itself, which your not really interested in, but it doesn't really matter. However it's a good exercise to design this in a way so it doesn't go over the element itself; for this it's helpful to use an auxiliary function

foci :: [a] -> [(a,[a])]

witht the behaviour

foci [p,q,r] ≡ [(p,[q,r]), (q,[p,r]), (r,[p,q])]

Then you left with an all over the foci of the input list, i.e.

isSymmetric = all _ . foci