Clases de equivalencia

José A. Alonso

05-04-2018

Definir la función

clasesEquivalencia :: Ord a =>
Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

λ> let c = fromList [-3..3]
λ> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
λ> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Soluciones

import Data.Set as S

clasesEquivalencia :: Ord a =>
                      Set a -> (a -> a -> Bool) -> Set (Set a)
clasesEquivalencia xs r
    | S.null xs =  empty
    | otherwise =  us `insert` clasesEquivalencia vs r
    where (y,ys)  = deleteFindMin xs
          (us,vs) = partition (r y) xs