structs
This package explores strict mutable data structures in Haskell.
In particular, pointer-based data structures are effectively 'half price' due to the encoding used.
However, the result is that if you use the slot
and field
system wrong, you can and will SEGFAULT
.
This means the Internal
modules are very much internal.
Some documentation is available at
[http://ekmett.github.io/structs/Data-Struct.html](http://ekmett.github.io/structs/Data-Struct.html)
Examples
Non-recursive data types
We use the template haskell helper makeStruct
to automatically convert
a Haskell data
definition to a Struct
.
As an example, we create a type that mimics a tuple of integers.
makeStruct [d|
data TupleInts a s = TupleInts
{ tupleLeft, tupleRight :: a
}
|]
This declaration uses makeStruct
, which will generate a bunch of
helper functions for us to use.
Notice the extra type parameter s
in TupleInts a s
. This is used to
carry around state information by structs
, and so is mandatory.
-- Create a new tuple of ints.
mkTupleInts :: PrimMonad m => Int -> Int -> m (TupleInts a (PrimState m))
mkTupleInts a b = st newTupleInts a b
newTupleInts
is a function that was auto-generated by makeStructs
, whose
parameters are all the fields, which returns a TupleInts
within a
PrimMonad
context. Notice the use of PrimState m
for the state
type parameter of TupleInts
, which is used to carry the state around.
-- set the left element of the tuple
setTupleLeft :: PrimMonad m => TupleInts a (PrimState m) -> a -> m ()
setTupleLeft tup val = setField tupleLeft tup val
-- get the left element of the tuple
getTupleLeft :: PrimMonad m => TupleInts a (PrimState m) -> m a
getTupleLeft tup = getField tupleLeft tup
The Template Haskell generates tupleLeft, tupleRight :: Field (TupleInts a) a
, which
can be used to get and set fields with getField, setField
. The type signature
indicates that tupleLeft, tupleRight
extract an a
from a TupleInts a
.
Recursive data types
We identify recursive members of a struct with Slot
s. These are like
makeStruct [d|
data LinkedList a s = LinkedList
{ val :: a,
next :: !(LinkedList a s) }
|]
for this definition, makeStruct
auto-generates
next :: Slot (LinkedList a s) (LinkedList a s)
.
Similar to the case of Field
, the type tells us that next
extracts
a LinkedList a s
from a LinkedList a s
-- Make an empty linked list
mkEmptyLinkedList :: LinkedList a s
mkEmptyLinkedList = Nil
Nil
is a special value which can be assigned to any Struct
.
-- Make a linked list node with a value
mkLinkedListNode :: PrimMonad m => a -> m (LinkedList a (PrimState m))
mkLinkedListNode a = newLinkedList a Nil
Once again, newLinkedList
is auto-generated by makeStruct
which we
use to initialize the linked list.
-- Append a node to a linked list.
appendLinkedList :: PrimMonad m =>
LinkedList x (PrimState m)
-> x
-> m (LinkedList x (PrimState m))
appendLinkedList xs x = do
isend <- isNil <$> (get next xs)
if isend
then do
nodex <- mkLinkedListNode x
set next xs nodex
return xs
else do
xs' <- get next xs
appendLinkedList xs' x
makeStruct [d|
data LinkedList a s = LinkedList
{ val :: a,
next :: !(LinkedList a s) }
|]
-- Make an empty linked list
mkEmptyLinkedList :: LinkedList a s
mkEmptyLinkedList = Nil
-- Make a linked list node with a value
mkLinkedListNode :: PrimMonad m => a -> m (LinkedList a (PrimState m))
mkLinkedListNode a = newLinkedList a Nil
-- Append a node to a linked list.
appendLinkedList :: PrimMonad m =>
LinkedList x (PrimState m)
-> x
-> m (LinkedList x (PrimState m))
appendLinkedList xs x = do
isend <- isNil <$> (get next xs)
if isend
then do
nodex <- mkLinkedListNode x
set next xs nodex
return xs
else do
xs' <- get next xs
appendLinkedList xs' x
The rest is straightforward uses of get
, set
, getField
, and setField
to
manipulate the linked list as usual.
FAQ
- Why can fields not be strict? (compiler error)
- How do I free memory once
alloc
d?
Contributions and bug reports are welcome!
Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.
-Edward Kmett