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