模式与GADT匹配

Question

我正在实现一个表达式求解器,但我在模式匹配方面遇到了一些问题.我有以下代码

data Expression a where
                Const   ?  Int ? Expression Int
                Add ?  Expression Int ? Expression Int ? Expression Int
                Sub ?  Expression Int ? Expression Int ? Expression Int


eval ?  Expression a ? a
eval (Const a) = a

eval (Add exp1 exp2) = (val1 + val2)
  where
    val1 = eval exp1
    val2 = eval exp2


eval (Sub exp1 exp2) = (val1 - val2)
  where
    val1 = eval exp1
    val2 = eval exp2

但是因为eval Add和eval Sub非常相似,我可能想要另一个操作,但我做了更通用的实现,但是我遇到了一些问题.我虽然喜欢

data Op = Add | Sub

data Expression a where
                Const   ?  Int ? Expression Int
                Op ?  Expression Int ? Expression Int ? Expression Int

eval (Op exp1 exp2) = case Op of
                           Add ? (val1 + val2)
                           Sub ? (val1 - val2)
                      where
                        val1 = eval exp1
                        val2 = eval exp2 

但它不起作用.可以这样做吗？提前致谢

Answer 1

这不起作用,因为您定义Op为数据构造函数和类型.该类型Op有两个构造函数Add和Sub,但 Expression类型有一个Op构造函数.这段代码令两者混淆.

eval函数的case语句尝试匹配值 Op,但是Op在此上下文中采用两个参数的构造函数,因此您无法对其进行模式匹配.我怀疑你会选择这样的东西

data Op = Add | Sub

data Expression a where
                Const ::  Int -> Expression Int
                Op ::  Op -> Expression Int -> Expression Int -> Expression Int

eval (Const c)         = c
eval (Op op exp1 exp2) = case op of
                           Add -> (val1 + val2)
                           Sub -> (val1 - val2)
                      where
                        val1 = eval exp1
                        val2 = eval exp2

您必须在Op构造函数中包含一个字段,该字段表示要执行的操作.既然你必须匹配该操作,那么坚持使用原始定义可能会更好 Expression.

另一种更简单,更容易扩展的可能性可能如下所示

data Expression a where
    Const ::  Int -> Expression Int
    Op    ::  (a -> b -> c) -> Expression a -> Expression b -> Expression c

eval :: Expression a -> a
eval (Const c)        = c
eval (Op f exp1 exp2) = f (eval exp1) (eval exp2)

其中一个Op与它包装实际功能了.你不可能做出很好的事情,比如打印出表达式并知道它对应的功能.