如何在Haskell中计算表达式

Question

我了解如何创建和评估简单的数据类型Expr.例如这样:

data Expr = Lit Int | Add Expr Expr | Sub Expr Expr | [...]

eval :: Expr -> Int
eval (Lit x) = x
eval (Add x y) = eval x + eval y
eval (Sub x y) = eval x - eval y

所以这是我的问题:如何将变量添加到此Expr类型,应该针对其指定值进行评估？它应该如下所示:

data Expr = Var Char | Lit Int | Add Expr Expr [...]
type Assignment = Char -> Int

eval :: Expr -> Assignment -> Int

我现在如何为(Var Char)和(Add Expr Expr)执行我的eval功能？我想我已经找到了最简单的,如何为Lit做这件事.

eval (Lit x) _ = x

对于(Var Char),我尝试了很多,但是我无法从作业中获得一个Int ..想想它会像这样工作:

eval (Var x) (varname number) = number

Answer 1

您需要将赋值函数应用于变量名称以获取Int:

eval (Var x) f = f x

这是因为f :: Char -> Int和x:: Char,所以你可以做f x一个Int.令人满意的是,这将适用于变量名称的集合.

例

ass :: Assignment
ass 'a' = 1
ass 'b' = 2

意思是

eval ((Add (Var 'a') (Var 'b')) ass
= eval (Var 'a') ass + eval (Var 'b') ass
= ass 'a'            + ass 'b'
= 1 + 2
= 3

将赋值函数传递给其他调用 eval

你需要继续传递赋值函数,直到得到整数:

eval (Add x y) f = eval x f + eval y f

订单不同？

如果允许更改类型,那么将赋值函数放在第一位且数据放在第二位似乎更合乎逻辑:

eval :: Assignment -> Expr -> Int
eval f (Var x) = f x
eval f (Add x y) = eval f x + eval f y

...但我想你可以把它看作一个带有变量变量的常量表达式(感觉势在必行),而不是一系列表达式中的一组常量值(感觉就像参照透明度).

Answer 2

好吧,如果你把你的环境建模为

type Env = Char -> Int

那么你拥有的就是

eval (Var c) env = env c

但这不是真的"正确".首先,未绑定变量会发生什么？所以也许更准确的类型

type Env = Char -> Maybe Int
emptyEnv = const Nothing

现在我们可以看到变量是否未绑定

eval (Var c) env = maybe handleUnboundCase id (env c)

现在我们可以handleUnboundCase用来做一些事情,比如分配一个默认值,炸毁程序,或让猴子爬出你的耳朵.

最后要问的问题是"变量如何约束？".如果您在Haskell中查找"let"语句,那么我们可以使用称为HOAS(高阶抽象语法)的技巧.

data Exp = ... | Let Exp (Exp -> Exp)

HOAS位是(Exp - > Exp).基本上我们使用Haskell的名称绑定来实现我们的语言.现在评估let我们做的表达式

eval (Let val body) = body val

这让我们躲闪Var并Assignment依靠Haskell来解析变量名.

此样式中的let语句示例可能是

 Let 1 $ \x -> x + x
 -- let x = 1 in x + x

这里最大的缺点是建模可变性是一种巨大的痛苦,但是当依赖于Assignment类型与具体地图时,情况已经是如此.

Answer 3

我建议使用MapfromData.Map代替。你可以实现它像

import Data.Map (Map)
import qualified Data.Map as M  -- A lot of conflicts with Prelude
-- Used to map operations through Maybe
import Control.Monad (liftM2)

data Expr
    = Var Char
    | Lit Int
    | Add Expr Expr
    | Sub Expr Expr
    | Mul Expr Expr
    deriving (Eq, Show, Read)

type Assignment = Map Char Int

eval :: Expr -> Assignment -> Maybe Int
eval (Lit x) _      = Just x
eval (Add x y) vars = liftM2 (+) (eval x vars) (eval y vars)
eval (Sub x y) vars = liftM2 (-) (eval x vars) (eval y vars)
eval (Mul x y) vars = liftM2 (*) (eval x vars) (eval y vars)
eval (Var x)   vars = M.lookup x vars

但这看起来很笨拙，liftM2 op每次添加操作时我们都必须继续使用。让我们和一些帮手清理一下

(|+|), (|-|), (|*|) :: (Monad m, Num a) => m a -> m a -> m a
(|+|) = liftM2 (+)
(|-|) = liftM2 (-)
(|*|) = liftM2 (*)
infixl 6 |+|, |-|
infixl 7 |*|

eval :: Expr -> Assignment -> Maybe Int
eval (Lit x) _      = return x  -- Use generic return instead of explicit Just
eval (Add x y) vars = eval x vars |+| eval y vars
eval (Sub x y) vars = eval x vars |-| eval y vars
eval (Mul x y) vars = eval x vars |*| eval y vars
eval (Var x)   vars = M.lookup x vars

那更好，但我们仍然要四处走动vars，这对我来说很丑陋。相反，我们可以使用ReaderTmtl 包中的monad。该ReaderT单子（和非变压器Reader）是一个非常简单的单子，它暴露了一个功能ask是回报你，当它的运行，所有你能做的就是通过价值“读”这个值，通常用于运行应用程序静态配置。在这种情况下，我们的“配置”是一个Assignment.

这是liftM2运营商真正派上用场的地方

-- This is a long type signature, let's make an alias
type ExprM a = ReaderT Assignment Maybe a

-- Eval still has the same signature
eval :: Expr -> Assignment -> Maybe Int
eval expr vars = runReaderT (evalM expr) vars

-- evalM is essentially our old eval function
evalM :: Expr -> ExprM Int
evalM (Lit x)   = return x
evalM (Add x y) = evalM x |+| evalM y
evalM (Sub x y) = evalM x |-| evalM y
evalM (Mul x y) = evalM x |*| evalM y
evalM (Var x)   = do
    vars <- ask  -- Get the static "configuration" that is our list of vars
    lift $ M.lookup x vars
-- or just
-- evalM (Var x) = ask >>= lift . M.lookup x

我们真正改变的唯一一件事是，每当遇到 a 时，我们都必须做一些额外的工作Var x，并且我们删除了该vars参数。我想，这使得evalM很优雅的，因为我们只访问Assignment时，我们需要它，我们甚至没有约衰竭担心，它完全被照顾的Monad实例Maybe。在整个算法中没有一行错误处理逻辑，但Nothing如果Assignment.

另外，请考虑稍后是否要切换到Doubles 并添加除法，但您还希望返回错误代码，以便确定是否存在除以 0 错误或查找错误。相反Maybe Double，您可以使用Either ErrorCode Doublewhere

data ErrorCode
    = VarUndefinedError
    | DivideByZeroError
    deriving (Eq, Show, Read)

然后你可以把这个模块写成

data Expr
    = Var Char
    | Lit Double
    | Add Expr Expr
    | Sub Expr Expr
    | Mul Expr Expr
    | Div Expr Expr
    deriving (Eq, Show, Read)

type Assignment = Map Char Double

data ErrorCode
    = VarUndefinedError
    | DivideByZeroError
    deriving (Eq, Show, Read)

type ExprM a = ReaderT Assignment (Either ErrorCode) a

eval :: Expr -> Assignment -> Either ErrorCode Double
eval expr vars = runReaderT (evalM expr) vars

throw :: ErrorCode -> ExprM a
throw = lift . Left

evalM :: Expr -> ExprM Double
evalM (Lit x)   = return x
evalM (Add x y) = evalM x |+| evalM y
evalM (Sub x y) = evalM x |-| evalM y
evalM (Mul x y) = evalM x |*| evalM y
evalM (Div x y) = do
    x' <- evalM x
    y' <- evalM y
    if y' == 0
        then throw DivideByZeroError
        else return $ x' / y'
evalM (Var x) = do
    vars <- ask
    maybe (throw VarUndefinedError) return $ M.lookup x vars

现在，我们有明确的错误处理，但它不是坏的，我们已经能够使用maybe，以避免明确地匹配Just和Nothing。

这比解决这个问题真正需要的信息要多得多，我只是想提出一个替代解决方案，它使用 的 monadic 属性Maybe并Either提供简单的错误处理并用于ReaderT清除Assignment到处传递参数的噪音。