# type-level-sets: Type-level sets and finite maps (with value-level counterparts)

**This is a package candidate release!** Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

This package provides type-level sets (no duplicates, sorted to provide a normal form) via `Set`

and type-level finite maps via `Map`

, with value-level counterparts.

Described in the paper "Embedding effect systems in Haskell" by Dominic Orchard and Tomas Petricek http://www.cl.cam.ac.uk/~dao29/publ/haskell14-effects.pdf (Haskell Symposium, 2014). This version now uses Quicksort to normalise the representation.

Here is a brief example for finite maps:

```
import Data.Type.Map
type instance Combine Int Int = Int
instance Combinable Int Int where
combine x y = x + y
foo :: Map '["x" :-> Int, "z" :-> Bool, "w" :-> Int]
foo = Ext (Var :: (Var "x")) 2
$ Ext (Var :: (Var "z")) True
$ Ext (Var :: (Var "w")) 5
$ Empty
bar :: Map '["y" :-> Int, "w" :-> Int]
bar = Ext (Var :: (Var "y")) 3
$ Ext (Var :: (Var "w")) 1
$ Empty
foobar = foo
````union`

bar

The `Map`

type for `foobar`

here shows the normalised form (sorted with no duplicates). The type signatures is commented out as it can be infered. Running the example we get:

> >>> foobar > {w :-> 6, x :-> 2, y :-> 3, z :-> True}

Thus, we see that the values for "w" are added together.

For sets, here is an example:

```
import GHC.TypeLits
import Data.Type.Set
type instance Cmp (Natural n) (Natural m) = CmpNat n m
data Natural (a :: Nat) where
Z :: Natural 0
S :: Natural n -> Natural (n + 1)
foo = asSet $ Ext (S Z) (Ext (S (S (S Z))) (Ext Z Empty))
bar = asSet $ Ext (S (S Z)) (Ext (S Z) (Ext (S Z) Empty))
foobar = foo
````union`

bar

Note the types here are all inferred.

## Properties

Versions | 0.5, 0.6, 0.6.1, 0.7, 0.8.0.0, 0.8.0.0, 0.8.5.0, 0.8.6.0, 0.8.7.0 |
---|---|

Change log | None available |

Dependencies | base (<5), ghc-prim [details] |

License | BSD-3-Clause |

Copyright | 2013-16 University of Cambridge |

Author | Dominic Orchard |

Maintainer | Dominic Orchard |

Category | Type System, Data Structures |

Source repository | head: git clone https://github.com/dorchard/type-level-sets |

Uploaded | Sun Sep 4 20:46:02 UTC 2016 by DominicOrchard |

## Modules

[Index]

*Data*

## Downloads

- type-level-sets-0.8.0.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)

#### Maintainers' corner

For package maintainers and hackage trustees