Я пытаюсь реализовать очередь 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, но я еще не совсем понимаю их, поэтому мне нужна помощь в том, как реализовать эту функциональность. Или мне нужно сделать это совсем по-другому? Спасибо.
StateT
илиMaybeT
. Клейсли-стрелы тоже могут пригодиться. - person Jeremy List   schedule 20.11.2013