我想知道它是否正确（似乎正确），如何使其更快以及如何检测堆栈溢出而不携带堆栈大小并检查堆栈大小（我听说过保护页，但是我不知道如何在Haskell中使用它们）。
{-# LANGUAGE RankNTypes #-}
module Main where
import Data.IORef
import Foreign.Ptr
import Foreign.Storable
import Foreign.Marshal.Alloc
import Control.Exception ( bracket )
import System.IO.Unsafe
newtype StackRef s a = StackRef (Ptr a)
data Stack = Stack (Ptr ())
newtype StackMonad s a = StackMonad (Stack -> IO (Stack, a))
instance Monad (StackMonad s) where
return x = ioToStackMonad (return x)
(StackMonad m) >>= f = StackMonad $ \stack -> do
(newStack, x) <- m stack
let (StackMonad g) = f x
g newStack
runStackWithSize :: Int -> (forall s. StackMonad s a) -> a
runStackWithSize stackSize (StackMonad f) = unsafePerformIO $
bracket (mallocBytes stackSize) free $ \theStack -> do
(_, a) <- f (Stack theStack)
return a
-- | 1024 bytes is the usual size for a stack
runStack :: (forall s. StackMonad s a) -> a
runStack = runStackWithSize 1024
newStackRef :: Storable a => a -> StackMonad s (StackRef s a)
newStackRef value = StackMonad $ \(Stack topOfStack) -> do
let ptr = castPtr (alignPtr topOfStack (alignment value))
poke ptr value
return (Stack (plusPtr ptr (sizeOf value)), StackRef ptr)
ioToStackMonad :: IO a -> StackMonad s a
ioToStackMonad action = StackMonad $ \ptr -> do
a <- action
return (ptr, a)
writeStackRef :: Storable a => StackRef s a -> a -> StackMonad s ()
writeStackRef (StackRef p) val = ioToStackMonad (poke p val)
readStackRef :: Storable a => StackRef s a -> StackMonad s a
readStackRef (StackRef p) = ioToStackMonad (peek p)
{- |
The type hackery means that pointers to the old stuff isn't reachable,
therefore it's okay to pop the stack pointer.
-}
stack :: (forall s. (forall b. StackRef t b -> StackRef s b) -> StackMonad s a) -> StackMonad t a
stack f = let (StackMonad s) = f (\(StackRef p) -> StackRef p) in StackMonad $ \old_ptr -> do
(_, state) <- s old_ptr
return (old_ptr, state)
stack_ :: (forall s. (forall b. StackRef t b -> StackRef s b) -> StackMonad s ()) -> StackMonad t ()
stack_ f = let (StackMonad s) = f (\(StackRef p) -> StackRef p) in StackMonad $ \old_ptr -> do
_ <- s old_ptr
return (old_ptr, ())
x :: Int
x = runStack $ do
a <- newStackRef 5
c <- stack $ \lift1 -> do
b <- newStackRef 1
let liftedA = lift1 a
aValue <- readStackRef liftedA
writeStackRef liftedA 6
bValue <- readStackRef b
return (aValue + bValue)
newAValue <- readStackRef a
return (c + newAValue)
main = print x
#1 楼
此代码是完全错误的。它甚至不是堆栈（因为它缺少pop操作，并且不可能以类型安全的方式实现它）。这里是一个示例：
runStack $ do
newStackRef (5:: Int)
newStackRef False
newStackRef 'x'
根据
newStackRef的定义，它只是将Storable的值表示在内存块中并前进指针。有关该值类型的所有信息都会丢失。
要从这样的堆栈中弹出一个值，您需要指定正确的类型，并且
如果类型不正确，编译器（或RTS）将无法发出警告。
到问题的单子部分。从
instance Monad的定义中，很容易看出它与State monad几乎相同（这是在Control.Monad.State.Trans.State.Lazy中定义的方式）
<唯一的区别是它运行在
IO的顶部，具有固定的状态类型。所以实际上是StateT (Ptr ()) IO。甚至不清楚作为
Monad实例的堆栈是什么。 list monad允许不确定的计算（类似prolog的样式），
Maybe monad允许失败的计算。要使计算能够访问和操作堆栈，使用现有的
State monad更容易。堆栈实现作为一种状态。我认为没有理由实施您自己的Stack monad。
评论
您是否尝试过仅将堆栈作为普通列表的实现？让运行时为您工作通常更快。实际上，列表是一个堆栈：它倾向于访问第一个元素。而且，[]是Monad ...，并且可能进行了重大优化，尽管它不如Vector那样快。
性能只是一个方面。关键是内存的半确定性分配（这也很容易调试）。因此，仅使用列表是不正确的。
我不了解Haskell，但是我知道如果我以我熟悉的语言来解决此问题，我将编写测试（无论是单元测试还是集成测试）来确定其是否按预期工作。通过它的步调运行它，并断言您不会溢出，并且堆栈可以正确响应。