Évaluateur polymorphe dans Haskell

Question

Comment puis-je modifier le code suivant afin de ne pas avoir autant d'évaluateurs (qui reflètent actuellement différents types de résultats)? Je veux un seul évaluateur pour ne pas connaître à l'avance le type de résultat. Je veux un évaluateur pour toute la langue. Dois-je ajouter un type de valeur pour Exp pour ce faire? À quoi cela ressemblerait-il? Quel type de valeur et comment éditerais-je les fonctions eval actuelles afin de refléter ce nouveau type polymorphe?

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

data Exp = V Var
    | B Bool
    | MyInt Int
    | And Exp Exp
    | Or Exp Exp
    | Not Exp
    | Mult Exp Exp
    | UnaryNeg Exp
    | LEQ Exp Exp
    | LESST Exp Exp
    | Add Exp Exp 
    | POLYEQ Exp Exp
data Var = VZ |VS Var

eval:: Exp -> Int
eval (MyInt e1)     = e1
eval (UnaryNeg e1)     = - (eval e1)
eval (Mult e1 e2) = eval e1 * eval e2
eval (Add e1 e2) = eval e1 + eval e2

eval0:: Exp -> Bool
eval0 (B e1) = e1
eval0 (Not e1) = not (eval0 e1)
eval0 (And e1 e2) = (eval0 e1) && (eval0 e2)
eval0 (Or e1 e2) = (eval0 e1) || (eval0 e2)
eval0 (LEQ e1 e2) = eval e1 <= eval e2
eval0 (LESST e1 e2) = eval e1 < eval e2

eval1:: Exp -> Bool
eval1 (POLYEQ e1 e2) = eval0 e1 == eval0 e2

Answer 1

La solution standard consiste à annoter le type d'expression avec le type de résultat qu'il représente. Ce sera alors un type de données algébriques généralisées :

{-# LANGUAGE GADTs #-}

data Exp a where
   V :: Var -> Exp a
   B :: Bool -> Exp Bool
   MyInt :: Int -> Exp Int
   And :: Exp Bool -> Exp Bool -> Exp Bool
   POLYEQ :: Exp a -> Exp a -> Exp Bool
   ...

Ensuite, vous n'avez besoin que d'une fonction d'évaluation, dont le résultat sera quel que soit le type représenté par l'expression:

eval :: Exp a -> a
eval (MyInt e1) = e1
eval (B  e1) = e1
...