Relations binaires et fonctions avec Haskell

Quelques tests pour travailler sur les relations binaires avec Haskell:

Haskell
import qualified Data.List as Liste
 
data Relation = Rel {
  source :: [Int],
  graphe :: [(Int,Int)]
  } deriving (Show)
 
 
r1 = Rel {
       source = [1,2,3,4,5],
       graphe = [(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3),(4,4),(5,5)]
     }
 
 
est_reflexive :: Relation -> Bool
est_reflexive    r        = 
  all (==True) [elem (x,x) (graphe r) | x <- (source r)]
 
echange :: (Int,Int) -> (Int,Int)
echange    (x,y)     =  (y,x)
 
est_symetrique :: Relation -> Bool
est_symetrique    r        =
  all (==True) [elem (echange couple) gr | couple <- gr]
  where gr = graphe r
        
classe :: Relation -> Int -> [Int]
classe    r           x   =  
  [y | y <- source r, elem (x,y) (graphe r) ]
  
big_union :: (Eq t) => [[t]] -> [t]
big_union famille = foldl Liste.union [] famille
 
image_d_un_ens :: Relation -> [Int] -> [Int] 
image_d_un_ens    r           ens = 
  big_union (map (classe r) ens)
  
codomaine :: Relation -> [Int]
codomaine r = image_d_un_ens r (source r)
 
image_suivi_de :: Relation -> Relation -> Int -> [(Int,Int)]
image_suivi_de r1 r2 x = 
  [(x,y) | y <- image_d_un_ens r2 (classe r1 x)]
  
suivi_de :: Relation -> Relation -> Relation
suivi_de r1 r2 = Rel {
  source = source r1 , 
  graphe = big_union (map (image_suivi_de r1 r2) (source r1))
  }
  
 
rel_id :: [Int] -> Relation
rel_id ens = Rel {
  source = ens, 
  graphe = [(x,x) | x <- ens]
  }
 
compo_itere :: Relation -> Int -> Relation
compo_itere r 0 = rel_id (source r)
compo_itere r k = suivi_de r (compo_itere r (k - 1))
 
infix #
 
(#) r k = compo_itere r k
 
transposee :: Relation -> Relation
transposee r = Rel {
  source = source r, 
  graphe = [echange couple | couple <- (graphe r) ]
  }
 
 
est_incluse :: Relation -> Relation -> Bool
est_incluse r1 r2 = all (\couple -> elem couple (graphe r1)) (graphe (r2))
 
infix <#
(<#) r1 r2 = est_incluse r1 r2
 
est_transitive :: Relation -> Bool
est_transitive r = (r # 2) <# r
 
est_equivalence r = (est_reflexive r) && (est_symetrique r) && (est_transitive r)
 
quotient :: Relation -> [[Int]]
quotient r = Liste.nub (map (classe r) (source r))
 
est_totale :: Relation -> Bool
est_totale r = all (\x -> length (classe r x) >= 1) (source r)
 
est_fonction :: Relation -> Bool
est_fonction r = all (\x -> length (classe r x) <= 1) (source r)
 
est_surjective :: Relation -> Bool
est_surjective f = ( est_fonction f ) &&
                   ( all (\x -> elem x (codomaine f)) (source f) )
                   
est_injective :: Relation -> Bool 
est_injective r = est_fonction (transposee r)
 
est_bijective :: Relation -> Bool
est_bijective f = (est_injective f) && (est_surjective f)

courtesy of webmatter.de