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

Question

I am interested in using more efficient pointers for a project implementing an imperative language in Haskell. There is already a library for that: Struct. There is a blog post on it and brief documentation.

The problem is there is only a quite sophisticated example of linkcut trees. For someone like me who doesn't use Haskell on a daily basis, it is quite exhausting to battle little documented code, template haskell, etc.

I would need a simpler example to get started, along the lines of expressing either of those two data types:

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))

This should be just a few simple lines for someone who is fluent in Haskell/GHC.

How do I express one of the data types above with the Struct library?

Haematoxylon

Completely orthogonal to the question, but: you are apparently already adding one unfamiliar technology (Haskell) to your project. Are you sure you want to kill the project before it even gets off the ground by adding another? I strongly recommend you start simple. Make sure that boring old "slow" references are actually a problem before you try to dive off the deep end. (I hope this warning will not discourage folks from trying to write a good answer, though.) – Tranche

@DanielWagner It's for a research project, didn't mention that. And Haskell is not unfamiliar, I'm just more familiar with dependently typed programming in my PhD. Also, the code is optional, so there will be a "very fast" compilation method that might use this library but there are two other ways to compile code. This is interesting for benchmarks comparing to other programming languages such as Java or scripting languages. – Haematoxylon

This blog post makes the library sound like a workshop for ekmett to explore his sophisticated ideas, not really a well-polished set of tools for use by others. He has marked it as such, as far as I can tell, with "Stability : experimental", and advises you additionally that the implementation of LinkCut is not intended for public use by marking it Internal. Now, I know you don't want to use it, but frankly even understanding it is probably pretty advanced. I'd leave this library alone, personally. – Acquiescence

Yes, I understand that it is internal. I am still interested in running benchmarks as a lower barrier what can be achieved with pointers in Haskell. – Haematoxylon

Out of curiosity, what is your use case exactly? Are you writing an interpreter in Haskell for your imperative language? Or are you trying to improve the compilation times of your language? (If so, are you absolutely certain that pointer hops are the bottleneck in your compiler?) – Permatron

Answer 1

I managed to get your DLL type working with Structs as follows:

{-# 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

Here's an example of using it:

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

Galloglass

I started a bounty to honor your answer (will give you as soon as that is possible) – Haematoxylon