structs
==========

[![Hackage](https://img.shields.io/hackage/v/structs.svg)](https://hackage.haskell.org/package/structs) [![Build Status](https://github.com/ekmett/structs/workflows/Haskell-CI/badge.svg)](https://github.com/ekmett/structs/actions?query=workflow%3AHaskell-CI)

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.

```hs
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.


```hs
-- 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.


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

```hs
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`.


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