如何为以下数据类型定义monad实例？

Question

这是我必须使用的代码：

infixl 9 :@: -- This is newly defined symbol used in the application of expressions

data Expr
  =  Lit Integer      -- a literal
  |  Var String       -- a variable
  |  Bin Expr Op Expr -- binary operator
  |  Abs String Expr  -- a lambda expression
  |  Expr :@: Expr    -- an application
  deriving Show

data Op = Plus | Mult
  deriving Show

data Value = IntVal Integer | FunVal Env String Expr
  deriving Show

type Env = [(String,Value)]

applyIntOp :: Op -> Value -> Value -> Value
applyIntOp op (IntVal v1) (IntVal v2) = 
   case op of 
      Plus -> IntVal (v1 + v2)
      Mult -> IntVal (v1 * v2)

eval :: Expr -> Env -> Value
eval (Lit i)        env = IntVal i
eval (Var v)        env = fromJust (lookup v env)
eval (Bin e1 op e2) env = applyIntOp op (eval e1 env) (eval e2 env)
eval (Abs v b)      env = FunVal env v b
eval (ef :@: ea)    env = let FunVal env var body = eval ef env
                              arg                 = eval ea env
                           in eval body ((var,arg):env) 

目标是使评估函数能够使用变量（变量字符串），其中变量取自环境（Env）。但是，当我尝试使用这些类型中的任何一种来定义monad时，我不能，因为它们的类型不正确（*代替*-> *）。

所以，我将如何定义此Monad，以便可以使用它正确地评估任何表达式。

instance Monad ? where
  return = ..
  >>=    = .. 

例如（3 +（x * 4）（apply）（x = 1 + 2））：

eval (Bin (Lit 3) Plus ((Abs "x" (Bin (Var "x") Mult (Lit 4))) :@: Bin (Lit 1) Plus (Lit 2))) []

此返回15

Answer 1

作为旁注，您的eval (ef :@: ae)大小写是错误的，因为在评估env和ef时使用了错误的ea副本。您需要这个：

eval (ef :@: ea)    env = let FunVal env' var body = eval ef env
                              arg                  = eval ea env
                           in eval body ((var,arg):env')

无论如何，我们首先讨论为评估函数（例如eval）“使用monad”的常用方法。

您的eval函数具有签名：

eval :: Expr -> Env -> Value

即使它的[[primary目的是获取Expr并确定其Value（即，它基本上是一个函数Expr -> Value），但您仍需要携带一些额外的信息，即[ C0]，它描述了变量绑定。即使您仅在处理Env和Var构造函数时访问这些绑定，并且仅在处理Sub构造函数时修改这些绑定，但是对于所有无关紧要的情况，您仍然需要传递:@:，特别是像这样的情况：

Env

甚至没有
touch

eval (Bin e1 op e2) env = applyIntOp op (eval e1 env) (eval e2 env) ，但需要将其传递给每个递归env调用。[为了避免这种情况，人们通常所做的是介绍一个单子背景进行评估。

not确实涉及为eval或Expr或Env编写monad实例。相反，它涉及更改Value的签名以获取eval并返回Expr，但是在“ monadic上下文”中可以使Value可用于检查和修改：

Env

实际上有一个现成的monad，所以您不必自己编写：
evalM :: Expr -> MyMonad Value

[此后，编写不关心import Control.Monad.Reader
type MyMonad = Reader Env
的案例会稍微容易一些：
Env

以及
do

在乎

evalM (Lit i) = pure $ IntVal i
evalM (Bin e1 op e2) = applyIntOp op <*> eval e1 <*> eval e2

的情况看上去也不错：Env

诚然，在此示例中引入evalM (Var v) = asks (fromJust . lookup v)
evalM (Abs v b) = FunVal <$> ask <*> pure v <*> pure b
evalM (ef :@: ea) = join $ apply <$> evalM ef <*> evalM ea
  where apply (FunVal env var body) va =
          local (const ((var,va):env)) $ evalM body
并没有多大帮助，但是如果您决定扩展语言以支持可变值，错误处理和IO副作用，您将开始看到此方法的更多优点。
同样，这是使用monad进行评估的
通常方法，但我不确定这是否是您要的内容。
一种[[unusual使用monad进行评估的方法将是为monadic动作是某种“替代”的MyMonad类型编写monad实例。很难想象这将如何工作。最明显的出发点是考虑在不更改整体结构的情况下通常使用monad递归替换结构元素的方式。例如，可以将list monad视为将列表的每个元素替换为新列表，但是与其返回列表列表，不如将列表全部串联在一起，以赋予其与原点相同的类型。对于叶子处具有值的树，通常有一个monad可以用关联的树替换每片叶子，但是该结构不是平坦的，而是舍弃了结构，因此它只是与原始树类型相同的树。
从这个起点，很容易想象一个替换单子替换那些以叶子为变量引用的表达式：
Expr

单子动作可以用

data ExprM a
  =  LitM Integer
  |  VarM a
  |  BinM (ExprM a) Op (ExprM a)
  deriving (Show, Functor)

（树）替换每个VarM a（叶）：

ExprM a

请注意，没有

instance Applicative ExprM where
  pure = VarM
  (<*>) = ap
instance Monad ExprM where
  VarM x >>= f = f x
  LitM n >>= f = LitM n
  BinM e1 op e2 >>= f = BinM (e1 >>= f) op (e2 >>= f)

构造函数，因为它已被monadic绑定替换。如果要用AppM替换表达式LitM 1中的VarM "x"值，则可以这样操作：

BinM (VarM "x") Plus (VarM "x")

给出：

body1 = BinM (VarM "x") Plus (VarM "x")

context1 "x" = LitM 1
context1 _ = error "variable not found"

example1 = body1 >>= context1

问题是，还不清楚如何重新添加

> example1
BinM (LitM 1) Plus (LitM 1)

构造函数。它实际上不能具有形式：

Abs

因为唯一明智的monad实例将必须对

参数名称

执行替换，但这没有任何意义。它也容易被变量捕获。

[如果... | Abs a (ExprM a) | ... 有一些巧妙的表示，可以让您坚持采用单子替换方案，那么我看不到。