The type-level-sets package

[Tags:bsd3, library]

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
Dependencies base (<5), ghc-prim [details]
License BSD3
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:57:51 UTC 2016 by DominicOrchard
Distributions NixOS:0.8.0.0
Downloads 821 total (45 in the last 30 days)
Votes
0 []
Status Docs available [build log]
Last success reported on 2016-09-04 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees