使用Struct库的快速不连续指针(静态,拆箱等)

Question

我有兴趣为在Haskell中实现命令式语言的项目使用更有效的指针.已有一个库:Struct.有一篇博客文章和简要文档.

问题是链接树只有一个非常复杂的例子.对于像我这样每天不使用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