pointers - 使用 Struct 库的快速命令式指针(静态、拆箱等)

Question

我有兴趣在 Haskell 中实现命令式语言的项目中使用更高效的指针。已经有library for that: Struct 。有一个blog post就在上面 brief documentation .

问题是只有 linkcut trees 的一个相当复杂的示例。对于像我这样不每天使用 Haskell 的人来说，与很少的文档化代码、模板 haskell 等作斗争是相当累人的。

我需要一个更简单的示例来开始，沿着表达这两种数据类型之一的思路:

import Data.IORef

data DLL a = DLL a (Maybe (IORef (DLL a))) (Maybe (IORef (DLL a)))

data DLLINT = DLLINT Int (Maybe (IORef DLLINT)) (Maybe (IORef DLLINT))

对于精通 Haskell/GHC 的人来说，这应该只是几行简单的代码。

如何使用 Struct 库表达上述数据类型之一？

Answer 1

我设法让您的 DLL 类型与 Structs 一起使用，如下所示:

{-# LANGUAGE TemplateHaskell, RoleAnnotations #-}
module DubLiList where

import Control.Monad.Primitive
import Data.Struct.TH
import Data.Struct
import Data.Struct.Internal


makeStruct [d|
  data DLL a s = DLL
    { prev :: !(DLL a s)
    , value :: a
    , next :: !(DLL a s)
    }
  |]

new :: (PrimMonad m) => a -> m (DLL a (PrimState m))
new x = st $ newDLL Nil x Nil

insert :: (PrimMonad m) => a -> DLL a (PrimState m) -> m (DLL a (PrimState m))
insert x this = st $ do
    prev' <- get prev this
    new <- newDLL prev' x this
    set prev this new
    set next prev' new
    return new

delete :: (PrimMonad m) => DLL a (PrimState m) -> m ()
delete this = st $ do
    prev' <- get prev this
    next' <- get next this
    set next prev' next'
    set prev next' prev'

toList :: (PrimMonad m) => DLL a (PrimState m) -> m [a]
toList this = st $ do
    if isNil this then return [] else do
        x <- getField value this
        that <- get next this
        (x:) <$> toList that

这是使用它的示例:

main :: IO ()
main = do
    dll <- new "foo"           -- [foo]
    dll' <- insert "bar" dll   -- [bar, foo]
    insert "baz" dll           -- [bar, baz, foo]

    xs <- toList dll'
    print xs