Haskell でスタックを書く

Ptr, malloc の勉強のため Haskell でスタックを書いてみた。いろいろ間違っている可能性あり。

  1. スタックは mallocBytes で確保する。
  2. 確保した領域へのポインタは(グローバル変数の替わりに)状態モナドで管理する。
-- Stack
import Control.Monad.State
import Foreign.Ptr
import Foreign.Marshal.Alloc
import Foreign.Storable

stackSize :: Int
stackSize = 12
intSize :: Int
intSize = sizeOf (undefined :: Int)

push :: Int -> StateT (Ptr Int, Int) IO ()
push x = do
  (stack, sp) <- get
  if (sp >= stackSize) then
    error "Stack overflow"
  else
   do
     lift $ poke (stack `plusPtr` (sp * intSize) :: Ptr Int) x
     put (stack, sp + 1)
     return ()
      
pop :: StateT (Ptr Int, Int) IO Int
pop = do
  (stack, sp) <- get
  if (sp > 0) then
    do
      x <- lift $ peek (stack `plusPtr` ((sp - 1) * intSize) :: Ptr Int)
      put (stack, sp - 1)
      return x
    else error "Stack undeflow"

initStack :: IO (Ptr Int, Int)
initStack = do
  p <- mallocBytes (stackSize * intSize)
  return (p, 0)

-- 実行方法 
-- initStack >>= evalStateT test0

test0 = do
  push 9
  pop
  
test1 = do
  push 3
  push 99
  x <- pop
  lift $ putStrLn $ "x: " ++ show x
  y <- pop
  lift $ putStrLn $ "y: " ++ show y

test2 = do
  push 8
  push 9
  pop
  pop  
  push 11
  push 13  
  pop
  pop

参考

以下のリンクに必要な情報は全てある。