Definir la función
clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]] |
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]] |
λ> 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 |
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
Solución en Maxima
clasesEquivalencia (xs,r) :=
equiv_classes (setify (xs),r)$ |
clasesEquivalencia (xs,r) :=
equiv_classes (setify (xs),r)$
La evaluación de los ejemplos es
(%i6) xs : makelist (k,k,1,10)$
(%i7) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,3) = 0)));
(%o7) {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}}
(%i8) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,5) = 0)));
(%o8) {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}
(%i9) clasesEquivalencia (makelist(k,k,-4,4), lambda ([x,y], is (abs (x) = abs (y))));
(%o9) {{- 4, 4}, {- 3, 3}, {- 2, 2}, {- 1, 1}, {0}} |
(%i6) xs : makelist (k,k,1,10)$
(%i7) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,3) = 0)));
(%o7) {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}}
(%i8) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,5) = 0)));
(%o8) {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}
(%i9) clasesEquivalencia (makelist(k,k,-4,4), lambda ([x,y], is (abs (x) = abs (y))));
(%o9) {{- 4, 4}, {- 3, 3}, {- 2, 2}, {- 1, 1}, {0}}