haskell - 这种表达式抽象支持哪些数学运算？

Question

一本著名的 Haskell 书有一个练习(剧透警告)，要求为数学表达式的简化数据类型编写仿函数、应用程序和单子(monad)实例。不，这不是我的类(class)作业。

以下类型检查:

data Expr a = Var a | Val Int | Add (Expr a) (Expr a) deriving Show

instance Functor Expr where
  fmap f (Var x) = Var $ f x
  fmap f (Add e1 e2) = Add (fmap f e1) (fmap f e2)
  fmap _ (Val x) = Val x

instance Applicative Expr where
  pure x = Var x
  (Val x) <*> _ = Val x
  (Var f) <*> e = f <$> e
  (Add f g) <*> e = Add (f <*> e) (g <*> e)

instance Monad Expr where
  return = pure
  (Val x) >>= _ = Val x
  (Var x) >>= f = f x
  (Add e1 e2) >>= f = Add (e1 >>= f) (e2 >>= f)

但是，问题的最后部分要求通过示例解释绑定(bind)在这种情况下的作用。我认为更好的问题是:您可以使用这些抽象进行哪些有用的操作？于是我开始思考这个问题，用下面的表达:

expr :: Expr Char
expr = Add (Add (Var 'x') (Var 'y')) (Add (Var 'x') (Val 1))

仿函数实例允许我用不同的名称替换变量:

λ> (\v -> if v == 'x' then 't' else v) <$> expr
Add (Add (Var 't') (Var 'y')) (Add (Var 't') (Val 1))

但是用它来替换变量的值似乎并没有真正起作用:

λ> (\v -> if v == 'x' then 2 else 3) <$> expr
Add (Add (Var 2) (Var 3)) (Add (Var 2) (Val 1))

然而，单子(monad)来拯救:

λ> expr >>= (\v -> Val (if v == 'x' then 2 else 3))
Add (Add (Val 2) (Val 3)) (Add (Val 2) (Val 1))

在 monad 的帮助下，似乎甚至可以用表达式替换变量，这里 t+2 替换为 x:

λ> expr >>= (\v -> if v == 'x' then Add (Var 't') (Val 2) else pure v)
Add (Add (Add (Var 't') (Val 2)) (Var 'y')) (Add (Add (Var 't') (Val 2)) (Val 1))

但是还有什么？应用程序的有意义的用途是什么？我们还可以用 monad 进行哪些其他有用的操作？

Answer 1

应用实例对应于替换变量，其中替换的 Expr 级结构不依赖于变量。例如，如果您在线性规划问题的上下文中处理此表达式，并希望将每个变量 Var 'x' 替换为两个变量之和，其中一个始终为正，另一个为总是负面的，你可以写:

> import Control.Applicative
> expr <**> Add (Var (:"pos")) (Var (:"neg"))
Add (Add (Add (Var "xpos") (Var "xneg")) 
   (Add (Var "ypos") (Var "yneg"))) 
   (Add (Add (Var "xpos") (Var "xneg")) (Val 1))
>

这里的关键是每个变量都被替换为相同的模板Add (Var "_pos") (Var "_neg")，其中模板中的新变量的名称可以依赖于原始变量名。这就是使此操作具有应用性的原因。

顺便说一句，请注意，用 Val Int 替换每个 Var Char 并不是一个应用操作，除非替换相同值对于每个变量 - Int 的值是 Expr 级结构的一部分，并且不能依赖于变量名称。

因为 monad 实例可以用依赖于变量名称的 Expr 替换变量，所以它可以执行更通用的替换。

最终，Functor 实例允许您更改变量名称，Monad 实例允许您用任意表达式替换变量，而 Applicative 实例提供有限类型的模板替换，对于这个特定的情况来说，这不是很有趣或有用数据结构。

这确实是他们所能做的，尽管您在尝试使用 Functor 实例替换值的失败尝试中提到了一个概括。这些实例可以将类型从 Expr Char 更改为其他 Expr b。例如，如果您将表达式编译为通过内存指针引用变量的字节码，那么突然通过仿函数“重命名”变量会变得更有趣:

type Location = Int
symtab :: [(Char, Int)]
symtab = [('x', 4096), ('y', 4100)]  -- memory addresses

> fmap (fromJust . flip lookup symtab) expr
Add (Add (Var 4096) (Var 4100)) (Add (Var 4096) (Val 1))
>