Utilisation de classes de type Haskell pour appliquer la commutativité

11

Je veux définir une classe de type pour les objets géométriques qui peuvent être intersectés ensemble:

class Intersect a b c | a b -> c where
  intersect :: a -> b -> c
-- Language extensions: -XMultiParamTypeClasses, -XFunctionalDependencies

L'idée est d'avoir une fonction d'intersection à usage général qui peut gérer des objets de différents types. On pourrait imaginer des exemples tels que

instance Intersect Line Plane (Maybe Point) where
  ...
instance Intersect Plane Plane (Maybe Line) where
  ...

Mais je veux aussi déclarer que l'intersection est commutative:

instance (Intersect a b c) => Intersect b a c where
  intersect x y = intersect y x
-- Language extensions: -XUndecidableInstances

Le problème est que chaque fois que j'évalue intersect x ysans d'abord définir une instance de la forme Intersect a b c, où aest le type de xet best le type de y, le programme entre dans une boucle infinie , probablement causée par une déclaration d'instance récursive sur la commutativité. Idéalement, je veux que quelque chose comme intersect Egg Baconne parvienne pas à la vérification de type car aucune instance de ce type n'a été définie, pas me piéger dans une boucle infinie. Comment puis-je implémenter cela?

haskell type-systems typeclass Herng Yi
la source
Cela ressemble à quelque chose que vous pourriez essayer de faire en utilisant des familles de types. Vous pourriez obtenir une meilleure réponse en cas de débordement de pile.
Benjamin Hodgson
2
Voici un article de blog sur une monade qui applique la commutativité, cela peut peut-être aider: gelisam.blogspot.ca/2013/07/the-commutative-monad.html
Daniel Díaz Carrete

Réponses:

2

Tout d'abord, vous pouvez utiliser le package commutatif , auquel cas vous modifierez la signature de type de intersectce qui suit, mais sinon le reste de votre code "fonctionnera" simplement:

instersect :: Commutative a b -> c

Cependant, vous pouvez également utiliser QuickCheck avec hspec afin d'exécuter un test de propriété sur toutes les instances de votre classe de type pour vous assurer qu'il fait effectivement la navette. Cela peut réduire les frais généraux - vous devriez faire un point de repère car je ne sais pas du haut de ma tête. Par exemple:

import Test.Hspec

main :: IO ()
main = hspec $ do
    describe "intersect" $ do
        parallel $ it "should commute" $ do
            property $ \x y -> intersect x y == intersect (y :: Point) (x :: Line)

la source