Разверните значение из контекста состояния Monad и объедините два контекста состояния - PullRequest
Новая
       14

Разверните значение из контекста состояния Monad и объедините два контекста состояния

0 голосов
/ 10 декабря 2018

Я пытаюсь написать функцию eval для моего простого анализатора императивного языка, но я сталкиваюсь с некоторыми проблемами, когда пишу ее с использованием Control.Monad и State .

При evalComm с Пусть case Мне нужно развернуть тип ( m Int ), чтобы передать только Int для обновления функции, есть лиспособ сделать это?

Также в evalComm s Seq case мне нужно объединить две функции evalComm для случая, когда рекурсия открывается двумя способами.liftM альтернатива для этого случая? 

type Env = [(Variable,Int)]

initState :: Env
initState = []

newtype State a = State { runState :: Env -> (a, Env) }

instance Monad State where
    return x = State (\s -> (x, s))
    m >>= f = State (\s -> let (v, s') = runState m s in
                           runState (f v) s')

instance Functor State where
    fmap = liftM

instance Applicative State where
    pure   = return
    (<*>)  = ap      

class Monad m => MonadState m where
    lookfor :: Variable -> m Int
    update :: Variable -> Int -> m ()

instance MonadState State where
    lookfor v = State (\s -> (lookfor' v s, s))
                where lookfor' v ((u, j):ss) | v == u = j
                                             | v /= u = lookfor' v ss
    update v i = State (\s -> ((), update' v i s))
                 where update' v i [] = [(v, i)]
                       update' v i ((u, _):ss) | v == u = (v, i):ss
                       update' v i ((u, j):ss) | v /= u = (u, j):(update' v i ss)

eval :: Comm -> Env
eval p = snd (runState (evalComm p) initState)

evalComm :: MonadState m => Comm -> m ()
evalComm c = case c of
                  Skip          -> return ()
                  Let v i       -> update v (evalIntExp i)
                  Seq c1 c2     -> return (liftM2 (:) (evalComm c2) (evalComm c1))

evalIntExp :: MonadState m => IntExp -> m Int
evalIntExp v = case v of
                    Const x             -> return (fromInteger x)
                    Var x               -> lookfor x
                    UMinus x            -> liftM (*(-1)) (evalIntExp x)
                    Plus x y            -> liftM2 (+) (evalIntExp x) (evalIntExp y)
                    Minus x y           -> liftM2 (-) (evalIntExp x) (evalIntExp y)
                    Times x y           -> liftM2 (*) (evalIntExp x) (evalIntExp y)
                    Div x y             -> liftM2 div (evalIntExp x) (evalIntExp y)


evalBoolExp :: MonadState m => BoolExp -> m Bool
evalBoolExp b = case b of
                     BTrue        -> return True
                     BFalse       -> return False
                     Eq x y       -> liftM2 (==) (evalIntExp x) (evalIntExp y)
                     Lt x y       -> liftM2 (<) (evalIntExp x) (evalIntExp y)
                     Gt x y       -> liftM2 (>) (evalIntExp x) (evalIntExp y)
                     And b0 b1    -> liftM2 (&&) (evalBoolExp b0) (evalBoolExp b1)
                     Or b0 b1     -> liftM2 (||) (evalBoolExp b0) (evalBoolExp b1)
                     Not b        -> liftM not (evalBoolExp b)

Обратите внимание, что код для evalComm не работает, и он может быть неправильным.

Вот мое дерево абстрактного синтаксиса: 

type Variable = String

data IntExp = Const Integer
            | Var Variable
            | UMinus IntExp
            | Plus IntExp IntExp
            | Minus IntExp IntExp
            | Times IntExp IntExp
            | Div IntExp IntExp
            | Quest BoolExp IntExp IntExp
 deriving Show

data BoolExp = BTrue
             | BFalse
             | Eq IntExp IntExp
             | Lt IntExp IntExp
             | Gt IntExp IntExp
             | And BoolExp BoolExp
             | Or BoolExp BoolExp
             | Not BoolExp
 deriving Show

data Comm = Skip
          | Let Variable IntExp
          | Seq Comm Comm
          | Cond BoolExp Comm Comm
          | While BoolExp Comm
          | Repeat Comm BoolExp
 deriving Show

Ответы [ 2 ]

0 голосов
/ 10 декабря 2018

Две вещи.

Во-первых, я думаю, что ваша функция обновления неверна, так как вы соответствуете шаблону дважды.Почему бы и нет?

1004

Эта функция обновления создает список пар.Как писал @Hjulle, использование оператора >> сделает: вычислить первый результат, а затем вычислить второй .В этом случае вычисление результата с использованием evalComm в конечном итоге обновляет состояние или возвращает ().Ваш код должен выглядеть примерно так: 

evalComm :: MonadState m => Comm -> m ()
evalComm c = case c of
                  Skip          -> return ()
                  Let v i       -> evalIntExp i >>= \o -> update v o
                  Seq c1 c2     -> evalComm c1 >> evalComm c2

evalIntExp i >>= \o -> update v o означает: вычислить evalIntExp i, принять полученный результат Int и передать его функции update

Эта реализация возвращает: 

let exp1 = Seq (Seq (Let "string1" (Const 1)) (Let "string2" (Const 2))) Skip 

> eval exp1
[("string1",1),("string2",2)]

Но в других примерах происходит сбой.

0 голосов
/ 10 декабря 2018

Дело Let

Как сказали Зигмонд и Вагнер, (>>=) - правильный инструмент для работы.Давайте посмотрим на типы: 

(>>=) :: m a -> (a -> m b) -> m b
update :: Variable -> Int -> m ()
evalIntExp i :: m Int
v :: Variable

Можете ли вы придумать способ объединить их в ожидаемый тип m ()?Помните, что вы можете частично применить функцию, чтобы получить обратно функцию, которая принимает меньше аргументов.

Случай Seq

Давайте снова посмотрим на типы.

У нас есть два значения типа m (), (evalComm c1 и evalComm c2) и мы хотим объединить их в значение типа m ().Мы можем снова использовать >>=, создав функцию, которая игнорирует ее аргумент: 

Seq c1 c2  -> (evalComm c1) >>= (\x -> (evalComm c1))

Однако это такой распространенный сценарий, поэтому для него уже есть встроенная функция: 

(>>) :: m a -> m b -> m b

Seq c1 c2  -> evalComm c1 >> evalComm c1

Давайте посмотрим на ваш предыдущий код 

liftM2 (:) :: m a -> m [a] -> m [a]

У вас нет списков, поэтому это бесполезно. 

liftM2 :: (a -> b -> c) -> m a -> m b -> m c

Это можно использовать, если a = b = c = (),но это излишне сложно по сравнению с использованием >>.Тем не менее, я призываю вас попробовать это в качестве упражнения.Как бы выглядела функция типа () -> () -> ()? 

return :: a -> m a

Это используется, когда у вас есть чистое значение и вам нужно преобразовать его в монадическое значение, поэтому нет необходимости использовать его здесь.Результат будет иметь двойной тип m (m ()), который вам не подходит.

Заключительные слова

Как вы можете видеть, типы могут быть очень полезны при написании программ на языке Haskell.Всякий раз, когда вам интересно, какие вещи можно комбинировать, посмотрите на типы.Вы можете проверить, какой тип выражения имеет, набрав :t <expression> в GHCi.

...