избегать явного прохождения таблицы поиска - PullRequest
Новая
       18

избегать явного прохождения таблицы поиска

7 голосов
/ 21 сентября 2011

В моей очень простой игрушечной программе с логическим выражением у меня есть следующая функция оценки: 

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? Может быть, с помощью монад?

Ответы [ 4 ]

13 голосов
/ 21 сентября 2011

Монады будут работать, но, на мой взгляд, использование 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), например, монады / аппликатива Reader, но без нового типаобертка.

9 голосов
/ 21 сентября 2011

Это именно то, для чего предназначена Монада Reader :

Монада Reader (также называемая монадой Environment). Представляет вычисления, которые могут читать значения из общей среды, проходят значения от функции к функции, и выполнить подвычисления в модифицированная среда.

Как отмечает Sjoerd, монада дает здесь больше энергии, чем вам нужно, но вы все равно можете использовать монаду Reader для этой задачи, даже не набрав 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, чтобы поднять его в монаду: 

eval' (Const c) = return c

Если вам нужна среда для поиска значения переменной, используйте ask. Используя запись do, вы можете написать регистр Var следующим образом: 

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

Я думаю, что лучше использовать fmap a.k.a. <$>: 

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

Аналогично, унарный not может быть fmap ped по результату рекурсии: 

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

Наконец, Applicative экземпляр Reader делает двоичные случаи приятными: 

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)
4 голосов
/ 21 сентября 2011

В этом случае вообще не передавать 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)
    ...
2 голосов
/ 21 сентября 2011

Знаете ли вы расширение неявные параметры ? Это может быть очень полезно.

...