避免显式传递查找表

Question

在我非常简单的布尔表达玩具程序中,我有以下评估函数:

eval' :: Expr -> M.Map Char Bool -> Bool

eval' (Const c) values = c

eval' (Var v)   values = M.findWithDefault False v values

eval' (Not x)   values = not (eval' x values)

eval' (And a b) values = eval' a values && eval' b values

eval' (Or  a b) values = eval' a values || eval' b values

eval' (Xor a b) values = eval' a values /= eval' b values

我想知道是否有办法values隐含地传递表格？也许在Monads的帮助下？

Answer 1

Monads可以工作,但在我看来使用Applicative更清洁:

eval' :: Expr -> M.Map Char Bool -> Bool
eval' (Const c) = pure c
eval' (Var v)   = M.findWithDefault False v
eval' (Not x)   = not <$> eval' x
eval' (And a b) = (&&) <$> eval' a <*> eval' b 
eval' (Or  a b) = (||) <$> eval' a <*> eval' b
eval' (Xor a b) = (/=) <$> eval' a <*> eval' b

这是使用((->) r)实例,如Readermonad/applicative,但没有newtype包装器.

Answer 2

这正是Reader monad的用途:

Reader monad(也称为Environment monad).表示计算,该计算可以从共享环境读取值,从函数传递值到函数,并在修改的环境中执行子计算.

正如Sjoerd指出的那样,monad在这里提供的功率超出了你的需要,但你仍然可以使用Reader monad来解决这个问题,而无需输入do:

import qualified Data.Map as M

import Control.Applicative ( (<$>), (<*>) )
import Control.Monad.Reader

data Expr = Const Bool
          | Var Char
          | Not Expr
          | And Expr Expr
          | Or Expr Expr
          | Xor Expr Expr

只需将您的环境类型作为Reader类型构造函数的第一个参数,将原始结果类型作为第二个参数.

eval' :: Expr -> Reader (M.Map Char Bool) Bool

而不仅仅是c作为Const案例的价值,用return它将其提升为monad:

eval' (Const c) = return c

当您需要环境来查找变量的值时,请使用ask.使用do表示法,您可以Var像这样编写案例:

eval' (Var v)   = do values <- ask
                     return (M.findWithDefault False v values)

不过,我认为使用fmapaka 更好<$>:

eval' (Var v)   = M.findWithDefault False v <$> ask

类似地,一元not可以fmap在递归的结果上踩踏:

eval' (Not x)   = not <$> eval' x

最后,Reader 的Applicative实例使二进制文件变得愉快:

eval' (And a b) = (&&) <$> eval' a <*> eval' b

eval' (Or  a b) = (||) <$> eval' a <*> eval' b

eval' (Xor a b) = (/=) <$> eval' a <*> eval' b

然后,为了让它全部启动,这里有一个帮助器来创建初始环境并运行计算:

eval :: Expr -> [(Char,Bool)] -> Bool
eval exp env = runReader (eval' exp) (M.fromList env)

Answer 3

values在这种情况下，根本不要通过：

eval' :: Expr -> M.Map Char Bool -> Bool
eval' e values = eval'' e

    where
    eval'' (Const c) = c
    eval'' (Var v) = M.findWithDefault False v values
    eval'' (Not x) = not (eval'' x)
    ...