structs
Strict GC'd imperative object-oriented programming with cheap pointers.
http://github.com/ekmett/structs/
Version on this page: | 0.1.6@rev:1 |
LTS Haskell 22.39: | 0.1.9@rev:2 |
Stackage Nightly 2024-10-31: | 0.1.9@rev:2 |
Latest on Hackage: | 0.1.9@rev:2 |
structs-0.1.6@sha256:48b495756dc3b8e9382dbff8d865767e1e24f24f4379cf7e6fa374c41609f1ee,1958
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
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?
Contact Information
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
Changes
0.1.6 [2021.04.30]
- Make the test suite compile on recent GHCs.
0.1.5 [2021.02.17]
- The build-type has been changed from
Custom
toSimple
. To achieve this, thedoctests
test suite has been removed in favor of usingcabal-docspec
to run the doctests.
0.1.4 [2020.10.02]
- Allow building with
template-haskell-2.17.0.0
(GHC 9.0).
0.1.3 [2020.01.29]
- Achieve forward compatibility with GHC proposal 229.
0.1.2 [2019.05.02]
- Add a unit test suite.
0.1.1
- Add a library dependency in the
doctests
test suite
0.1
- Add compare-and-swap support for struct slots
- Add
Data.Struct.TH
, which provides Template Haskell support for generating structs - Remove unneeded proxy argument to
struct
- Add a type parameter to
Order
- Revamp
Setup.hs
to usecabal-doctest
. This makes it build withCabal-2.0
, and makes thedoctest
s work withcabal new-build
and sandboxes.
0
- Repository initialized
- Added structures for list labeling, order-maintenance, and link-cut trees.