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

See all snapshots structs appears in

BSD-3-Clause licensed by Edward A. Kmett
Maintained by Edward A. Kmett
This version can be pinned in stack with:structs-0.1.6@sha256:48b495756dc3b8e9382dbff8d865767e1e24f24f4379cf7e6fa374c41609f1ee,1958

structs

Hackage Build Status

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 Slots. 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

  1. Why can fields not be strict? (compiler error)
  2. How do I free memory once allocd?

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 to Simple. To achieve this, the doctests test suite has been removed in favor of using cabal-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]

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 use cabal-doctest. This makes it build with Cabal-2.0, and makes the doctests work with cabal new-build and sandboxes.

0

  • Repository initialized
  • Added structures for list labeling, order-maintenance, and link-cut trees.