Использование Maybe с State Monad

Я пытаюсь реализовать очередь FIFO в Haskell с помощью операций push / pop / peek, и это то, что я получил до сих пор.

data Queue a = Queue { 
  inbox :: [a], 
  outbox :: [a] 
} deriving (Eq, Show)

push :: a -> Queue a -> Queue a
push e (Queue inb out) = Queue (e:inb) out

pop :: Queue a -> (Maybe a, Queue a)
pop q = 
  case top of
    Nothing   -> (top, emptyQueue)
    Just elem -> (Just elem, poppedQueue)
    where
      (top, q') = peek q
      poppedQueue = Queue (inbox q') (tail $ outbox q')

peek :: Queue a -> (Maybe a, Queue a)
peek q@(Queue [] [])    = (Nothing, emptyQueue)
peek q@(Queue inb [])   = peek $ Queue [] (reverse inb)
peek q@(Queue _ outb)   = (Just $ head outb, q)

emptyQueue = Queue [] []

Таким образом, все вышеперечисленное работает, и я могу нажимать / открывать / просматривать свою очередь. Как видите, я заключил возвращаемый тип в объект «Maybe», чтобы получить значение Nothing, если я открываю пустую очередь или просматриваю пустую очередь, и элемент Just в противном случае.

Так что я также подумал, что могу использовать монаду State для упрощения цепочки операций. Я поступил следующим образом:

type QueueState a = State (Queue a)

pushQueue :: a -> QueueState a ()
pushQueue e = state $ \q -> ((),push e q)

popQueue :: QueueState a (Maybe a)
popQueue = state $ \q -> pop q

Хорошо, похоже, это работает. Я могу сделать:

runState (pushQueue 2 >> pushQueue 3 >> popQueue >> pushQueue 1 >> popQueue) emptyQueue

и вернись (Just 3,Queue {inbox = [1], outbox = []}), чего я и хотел. Но я не могу сделать что-то вроде:

runState (pushQueue 2 >> popQueue >>= pushQueue) emptyQueue

что приводит к:

Occurs check: cannot construct the infinite type: a0 = Maybe a0
Expected type: Maybe a0
               -> StateT (Queue a0) Data.Functor.Identity.Identity ()
  Actual type: Maybe a0 -> QueueState (Maybe a0) ()

Теперь я думаю, что понимаю, почему это так, но я не могу понять, как заставить его делать то, что я хочу. То есть цепочка с использованием >>= из pop должна иметь возможность передавать в push. Я думаю, что мне может понадобиться преобразователь StateT, но я еще не совсем понимаю их, поэтому мне нужна помощь в том, как реализовать эту функциональность. Или мне нужно сделать это совсем по-другому? Спасибо.


person rafalio    schedule 20.11.2013    source источник
comment
Я недостаточно знаком с преобразователями монад, чтобы по-настоящему ответить, но это звучит как задача для преобразователя StateT или MaybeT. Клейсли-стрелы тоже могут пригодиться.   -  person Jeremy List    schedule 20.11.2013


Ответы (1)


Это потому, что компилятор не может построить бесконечный тип ;-).

Более полезно рассмотрим строку:

runState (pushQueue 2 >> popQueue >>= pushQueue) emptyQueue

Какой тип popQueue? QueueState Int (Maybe Int). (думаю m (Maybe Int))

Какой тип >>= pushQueue? QueueState Int Int -> QueueState Int () (думаю m Int -> m ())

Таким образом, проверка типов пытается объединить типы Maybe a и a - единственный способ объединения этих типов - if a, если бесконечный тип Maybe (Maybe (Maybe (Maybe ....

Решение состоит в том, чтобы сделать что-нибудь для обработки случая Nothing. Например, return () или нажмите в зависимости от значения «Может быть».

runState (pushQueue 2 >> popQueue >>= maybe (return ()) pushQueue) emptyQueue
person Thomas M. DuBuisson    schedule 20.11.2013
comment
Спасибо, объяснение проверки происходит имеет смысл. Но действительно ли я бы так поступил? Выглядит "взломано". Я думал, что смысл всего этого >>= в том, чтобы скрыть такие сложности. Нет ли возможности каким-то образом зайти «внутрь» m и использовать правила монад для Maybe, чтобы применить значение m (Maybe a) к функции типа a -> m b, чтобы мой исходный пример просто работал? Просто пытаюсь хорошо выучить монады :) - person rafalio; 20.11.2013
comment
Нет, монадическое связывание не предназначено / не может обеспечить преобразование из произвольных типов в желаемый тип ввода ... независимо от того, насколько тривиален или распространен этот тип. - person Thomas M. DuBuisson; 21.11.2013