0

プッシュ/ポップ/ピーク操作を使用して Haskell に FIFO キューを実装しようとしていますが、これがこれまでに得たものです。

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) ()

これで理由は理解できたと思いますが、自分のやりたいことを実現する方法がわかりません。つまり、 from を使用>>=したチェーンは、popにフィードできる必要がありpushます。StateT トランスフォーマーを使用する必要があるかもしれないと考えていますが、まだよく理解していないため、その機能を実装する方法について助けを求めています。それとも、まったく別の方法でこれを行う必要がありますか? ありがとう。

4

1 に答える 1

2

これは、コンパイラが無限型を構築できないためです;-)。

さらに役立つのは、次の行を検討することです。

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統一する唯一の方法はa、 の無限型の場合ですMaybe (Maybe (Maybe (Maybe ...。

解決策は、ケースを処理するために何かNothingをすることです。たとえばreturn ()、Maybe に応じてプッシュしたりします。

runState (pushQueue 2 >> popQueue >>= maybe (return ()) pushQueue) emptyQueue
于 2013-11-20T02:18:15.087 に答える