结构库中的快速有趣的指针(静态,拆箱等)
问题描述:
我有兴趣为在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))
这应该只是简单的几行的人谁是精通哈斯克尔/ GHC。
如何用Struct库表达上述其中一种数据类型?
答
我设法让你的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
+3
我开始了一个赏金来答复你的答案(尽快可能会给你) – mrsteve
完全正交的问题,而是:你显然已经加入一个陌生的技术(哈斯克尔)到您的项目。通过添加另一个项目,你确定要在项目开始之前杀死该项目吗?我强烈建议你从简单开始。确保无聊的旧“慢”引用实际上是一个问题,然后再尝试跳出深度。 (我希望这个警告不会阻止人们试图写出一个好的答案,尽管如此。) –
@DanielWagner这是一个研究项目,没有提到这一点。 Haskell并不陌生,我只是比较熟悉我的博士学位课程中的依赖类型编程。此外,代码是可选的,所以会有一个“非常快”的编译方法,可能会使用这个库,但有另外两种编译代码的方法。与其他编程语言(如Java或脚本语言)相比,这是基准测试的有趣之处。 – mrsteve
这篇博客文章使得图书馆听起来像是ekmett的研讨会,探索他的复杂想法,而不是真正精心打磨的一套供其他人使用的工具。据我所知,他已经标记为“稳定性:实验性”,并且建议您另外建议您将LinkCut的实施标记为“内部”,而不是公开使用的。现在,我知道你不想使用它,但坦率地说,甚至可以理解它可能相当先进。我亲自离开这个图书馆。 – amalloy