Заставить нормальные монадические функции работать с эквивалентным монадным трансформатором - PullRequest
Новая
       21

Заставить нормальные монадические функции работать с эквивалентным монадным трансформатором

5 голосов
/ 08 февраля 2012

Я пытаюсь решить проблему сбалансированных скобок. Я не хочу делать непрерывный ввод-вывод, а хотел бы сделать один вызов getLine и проанализировать полученную строку. Поэтому функция, которая решает проблему, будет иметь дело с двумя различными состояниями: неизрасходованная часть входной строки и стек скобок.

Я хочу настроить некоторые функции для работы со стеком: 

type Stack = String

pop :: Stack -> (Char,Stack)
pop (x:xs) = (x,xs)

push :: Char -> Stack -> ((),Stack)
push a xs = ((),a:xs)

Это все хорошо, если я работаю в монаде штата, однако я работаю в монаде StateT 

balanced :: StateT Stack (State String) Bool

Я знаю, что мне сказали, чтобы в стеке не было дублированных монад. Я делаю это так, потому что мне нравится, как это упрощает определения push и pop.

Две проблемы:

  1. Независимо от того, что я делаю, я не могу найти способ применить push и pop к Стек содержится в StateT.
  2. Понятия не имею, как вызвать это из основной функции

Вот остаток кода 

next :: String -> (Maybe Char,String)
next ""     = (Nothing,[])
next (x:xs) = (Just x,xs)

balanced = do
            c <- lift (state next)
            case c of
              Nothing -> return True
              Just c  -> if elem c open 
                         then (push c) >> balanced
                         else if elem c close 
                              then pop >>= \x ->
                                if eq x c
                                then balanced
                                else return False
                              else balanced
          where open  = "<{(["
                close = "])}>"
                eq '(' ')' = True
                eq '{' '}' = True
                eq '<' '>' = True
                eq '[' ']' = True
                eq  _   _  = False

1 Ответ

7 голосов
/ 08 февраля 2012

Ваша проблема в том, что ваши push и pop являются просто обычной немонадной функцией, которую вы пытаетесь использовать в монадическом do-блоке.Вы используете next правильно, поскольку вы вызываете его с помощью функции state, но, как вы, вероятно, заметили, state работает только для простой монады State, а не StateT.

Мыможет реализовать версию монадного преобразователя state следующим образом: 

stateT :: Monad m => (s -> (a, s)) -> StateT s m a
stateT f = do
    (x, s') <- gets f
    put s'
    return x

, а затем использовать ее в функции balanced с push и pop. 

balanced :: StateT Stack (State String) Bool
balanced = do
            c <- lift (state next)
            case c of
              Nothing -> return True
              Just c  -> if elem c open
                         then (stateT $ push c) >> balanced
                         else if elem c close
                              then stateT pop >>= \x ->
                                if eq x c
                                    then balanced
                                    else return False
                              else balanced
          where open  = "<{(["
                close = "])}>"
                eq '(' ')' = True
                eq '{' '}' = True
                eq '<' '>' = True
                eq '[' ']' = True
                eq  _   _  = False

Функция вызывается так: 

evalState (evalStateT balanced []) s

Где s - начальная строка, а [] - начальный стек.

...