ならしコストによるQueue

30分プログラム、その425。HaskellでQueueを作ってみた。関数型言語でキューといえばamortizedなキューだと思ったので、そちらで。

ところで、ボクが最初に読んだ本(コンピュータプログラミングの概念・技法・モデル (IT Architects' Archiveクラシックモダン・コンピューティング))ではamortizedの訳が「減価償却的」だったんだけど、どうも"ならしコスト"とか訳すのが一般的っぽい。

使い方

*Main> let q = insert 1 $ insert 2 $ empty
*Main> let (a,q') = remove q
*Main> a
2
*Main> let (b,_) = remove q'
*Main> b
1
*Main> 

ソースコード

import Control.Monad.State

type Queue a = ([a],[a])

empty   :: Queue a
isEmpty :: Queue a -> Bool
insert  :: a -> Queue a -> Queue a
remove  :: Queue a -> (a,Queue a)

empty = ([],[])

isEmpty ([],[]) = True
isEmpty _       = False

balance ([],q) = (reverse q,[])
balance q      = q

insert y (xs,ys) = balance (xs,y:ys)

remove (x:xs,ys) = (x,balance (xs,ys))
remove _         = error "empty queue"


getOne :: State (Queue Int) Int
getOne = do q <- get
            (x,q') <- return $ remove q
            put q'
            return x
          
test = runState (do a <- getOne
                    b <- getOne
                    c <- getOne
                    return (a,b,c)) $
       insert 1 $ insert 2 $ insert 3 empty

参考

• 過去の30分プログラム