structs: Strict GC'd imperative object-oriented programming with cheap pointers.

[ bsd3, data, library ] [ Propose Tags ]

This project is an experiment with a small GC'd strict mutable imperative universe with cheap pointers inside of the GHC runtime system.


[Skip to Readme]
Versions [faq] 0, 0.1, 0.1.1, 0.1.2
Change log CHANGELOG.markdown
Dependencies base (>=4.9 && <5), deepseq, ghc-prim, primitive, template-haskell (>=2.11 && <2.16) [details]
License BSD-3-Clause
Copyright Copyright (C) 2015-2017 Edward A. Kmett
Author Edward A. Kmett
Maintainer Edward A. Kmett <ekmett@gmail.com>
Revised Revision 1 made by ryanglscott at Thu May 2 17:15:37 UTC 2019
Category Data
Home page http://github.com/ekmett/structs/
Bug tracker http://github.com/ekmett/structs/issues
Source repo head: git clone git://github.com/ekmett/structs.git
Uploaded by ryanglscott at Thu May 2 17:14:02 UTC 2019
Distributions LTSHaskell:0.1.2, NixOS:0.1.2, Stackage:0.1.2
Downloads 1323 total (80 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-05-02 [all 1 reports]

Modules

[Index] [Quick Jump]

Flags

NameDescriptionDefaultType
test-doctestsEnabledManual

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for structs-0.1.2

[back to package description]

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