使用 Struct 库的快速强制指针（静态、拆箱等）

Question

我有兴趣为在 Haskell 中实现命令式语言的项目使用更有效的指针。已经有 library for that: Struct. There is a blog post on it and 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

使用 Struct 库的快速强制指针（静态、拆箱等）

Fast impertive pointers (static, unboxing, etc.) with Struct library

haskell

pointers

imperative-programming

ghc