Clases de equivalencia

José A. Alonso

05-04-2016

Definir la función

clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]

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

λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3)
[[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]]
λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0)
[[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]]
λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y)
[[-4,4],[-3,3],[-2,2],[-1,1],[0]]

Soluciones

import Data.List (partition)

clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]
clasesEquivalencia [] r = []
clasesEquivalencia ys@(x:xs) r =
    us : clasesEquivalencia vs r
    where (us,vs) = partition (r x) ys