2

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

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

但它不起作用。有可能做这样的事情吗？提前致谢

4

3 回答 3

7

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

您的函数的 case 语句eval尝试匹配 value 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)

其中 anOp用它包装了实际功能。您将无法做一些好的事情，例如打印出表达式并知道它对应的函数。

于 2013-02-08T18:50:19.890 回答
4

翻阅评论：

data Op a b c where
    Add :: Op Int Int Int
    Sub :: Op Int Int Int
    Less :: Op Int Int Bool

interpretOp :: Op a b c -> a -> b -> c
interpretOp Add = (+)
interpretOp Sub = (-)
interpretOp Less = (<)

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

eval :: Expression a -> a
eval (Const x) = x
eval (Op op a b) = interpretOp op (eval a) (eval b)
于 2013-02-08T20:51:15.067 回答
0

重复luqui的回答：

{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, GADTs #-}
class OpLike op a b where
    type Result op a b
    interpret :: op -> a -> b -> Result op a b

data Expression a where
    Const :: a -> Expression a
    Op :: OpLike op a b => op -> Expression a -> Expression b -> Expression (Result op a b)

eval :: Expression a -> a
eval (Const x) = x
eval (Op op a b) = interpret op (eval a) (eval b)

现在，您可以在程序中的任何位置添加运算符，而无需更改诸如 luqui 的Op数据类型之类的内容。这是一个非常人为的例子：

data Add = Add
add x y = Op Add x y

instance OpLike Add Int Int where
    type Result Add Int Int = Int
    interpret Add x y = x + y

instance OpLike Add Int Bool where
    type Result Add Int Bool = String
    interpret Add x y = if y then reverse (show x) else show x    

example = (Const (3::Int) `add` Const (10::Int)) `add` (Const True)

example有类型Expression String并且eval适用于"31":-)

于 2013-02-09T16:52:40.047 回答