结构库中的快速有趣的指针（静态，拆箱等）

我有兴趣为在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库表达上述其中一种数据类型？

来源

2017-04-25 mrsteve

完全正交的问题，而是：你显然已经加入一个陌生的技术（哈斯克尔）到您的项目。通过添加另一个项目，你确定要在项目开始之前杀死该项目吗？我强烈建议你从简单开始。确保无聊的旧“慢”引用实际上是一个问题，然后再尝试跳出深度。（我希望这个警告不会阻止人们试图写出一个好的答案，尽管如此。） –

@DanielWagner这是一个研究项目，没有提到这一点。 Haskell并不陌生，我只是比较熟悉我的博士学位课程中的依赖类型编程。此外，代码是可选的，所以会有一个“非常快”的编译方法，可能会使用这个库，但有另外两种编译代码的方法。与其他编程语言（如Java或脚本语言）相比，这是基准测试的有趣之处。 – mrsteve

这篇博客文章使得图书馆听起来像是ekmett的研讨会，探索他的复杂想法，而不是真正精心打磨的一套供其他人使用的工具。据我所知，他已经标记为“稳定性：实验性”，并且建议您另外建议您将LinkCut的实施标记为“内部”，而不是公开使用的。现在，我知道你不想使用它，但坦率地说，甚至可以理解它可能相当先进。我亲自离开这个图书馆。 – amalloy

我设法让你的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

来源

2017-04-26 03:22:27 Cactus

我开始了一个赏金来答复你的答案（尽快可能会给你） – mrsteve

结构库中的快速有趣的指针（静态，拆箱等）

回答

相关问题