ixset-typed 0.1.3 → 0.1.4
raw patch · 3 files changed
+89/−77 lines, 3 files
Files
- ixset-typed.cabal +15/−8
- src/Data/IxSet/Typed.hs +72/−67
- src/Data/IxSet/Typed/Ix.hs +2/−2
ixset-typed.cabal view
@@ -1,16 +1,23 @@ name: ixset-typed-version: 0.1.3+version: 0.1.4 synopsis: Efficient relational queries on Haskell sets. description:- Create and query sets that are indexed by multiple indices.+ This Haskell package provides a data structure of sets that are indexed+ by potentially multiple indices. .- This is a variant of the ixset package that tracks the index- information via the type system. It should be safer to use than- ixset, but also requires more GHC extensions.+ Sets can be created, modified, and queried in various ways. .- The two packages are currently relatively compatible. Switching- from one to the other requires a little bit of manual work, but- not very much.+ The package is a variant of the <https://hackage.haskell.org/package/ixset ixset>+ package. The ixset package makes use+ of run-time type information to find a suitable index on a query, resulting+ in possible run-time errors when no suitable index exists. In ixset-typed,+ the types of all indices available or tracked in the type system.+ Thus, ixset-typed should be safer to use than ixset, but in turn requires+ more GHC extensions.+ .+ At the moment, the two packages are relatively compatible. As a consequence+ of the more precise types, a few manual tweaks are necessary when switching+ from one to the other, but the interface is mostly the same. license: BSD3 author: Andres Löh, Happstack team, HAppS LLC maintainer: Andres Löh <andres@well-typed.com>
src/Data/IxSet/Typed.hs view
@@ -28,78 +28,78 @@ 1. Decide what parts of your type you want indexed and make your type an instance of 'Indexable'. Use 'ixFun' and 'ixGen' to build indexes: -> type EntryIxs = '[Author, Id, Updated, Test]-> type IxEntry = IxSet EntryIxs Entry->-> instance Indexable EntryIxs Entry where-> empty = mkEmpty-> (ixGen (Proxy :: Proxy Author)) -- out of order-> (ixGen (Proxy :: Proxy Id))-> (ixGen (Proxy :: Proxy Updated))-> (ixGen (Proxy :: Proxy Test)) -- bogus index+ > type EntryIxs = '[Author, Id, Updated, Test]+ > type IxEntry = IxSet EntryIxs Entry+ >+ > instance Indexable EntryIxs Entry where+ > empty = mkEmpty+ > (ixGen (Proxy :: Proxy Author)) -- out of order+ > (ixGen (Proxy :: Proxy Id))+ > (ixGen (Proxy :: Proxy Updated))+ > (ixGen (Proxy :: Proxy Test)) -- bogus index -The use of 'ixGen' requires the 'Data' and 'Typeable' instances above.-You can build indexes manually using 'ixFun'. You can also use the-Template Haskell function 'inferIxSet' to generate an 'Indexable'-instance automatically.+ The use of 'ixGen' requires the 'Data' and 'Typeable' instances above.+ You can build indexes manually using 'ixFun'. You can also use the+ Template Haskell function 'inferIxSet' to generate an 'Indexable'+ instance automatically. -3. Use 'insert', 'insertList', 'delete', 'updateIx', 'deleteIx'+2. Use 'insert', 'insertList', 'delete', 'updateIx', 'deleteIx' and 'empty' to build up an 'IxSet' collection: -> entries = insertList [e1, e2, e3, e4] (empty :: IxEntry)-> entries1 = foldr delete entries [e1, e3]-> entries2 = updateIx (Id 4) e5 entries+ > entries = insertList [e1, e2, e3, e4] (empty :: IxEntry)+ > entries1 = foldr delete entries [e1, e3]+ > entries2 = updateIx (Id 4) e5 entries -4. Use the query functions below to grab data from it:+3. Use the query functions below to grab data from it: -> entries @= Author "john@doe.com" @< Updated t1+ > entries @= Author "john@doe.com" @< Updated t1 -Statement above will find all items in entries updated earlier than-@t1@ by @john\@doe.com@.+ Statement above will find all items in entries updated earlier than+ @t1@ by @john\@doe.com@. -5. Text index+4. Text index -If you want to do add a text index create a calculated index. Then if you want-all entries with either @word1@ or @word2@, you change the instance-to:+ If you want to do add a text index create a calculated index. Then if you want+ all entries with either @word1@ or @word2@, you change the instance+ to: -> newtype Word = Word String-> deriving (Show, Eq, Ord)->-> getWords (Entry _ _ _ _ (Content s)) = map Word $ words s->-> type EntryIxs = '[..., Word]-> instance Indexable EntryIxs Entry where-> empty = mkEmpty-> ...-> (ixFun getWords)+ > newtype Word = Word String+ > deriving (Show, Eq, Ord)+ >+ > getWords (Entry _ _ _ _ (Content s)) = map Word $ words s+ >+ > type EntryIxs = '[..., Word]+ > instance Indexable EntryIxs Entry where+ > empty = mkEmpty+ > ...+ > (ixFun getWords) -Now you can do this query to find entries with any of the words:+ Now you can do this query to find entries with any of the words: -> entries @+ [Word "word1", Word "word2"]+ > entries @+ [Word "word1", Word "word2"] -And if you want all entries with both:+ And if you want all entries with both: -> entries @* [Word "word1", Word "word2"]+ > entries @* [Word "word1", Word "word2"] -6. Find only the first author+5. Find only the first author -If an @Entry@ has multiple authors and you want to be able to query on-the first author only, define a @FirstAuthor@ datatype and create an-index with this type. Now you can do:+ If an @Entry@ has multiple authors and you want to be able to query on+ the first author only, define a @FirstAuthor@ datatype and create an+ index with this type. Now you can do: -> newtype FirstAuthor = FirstAuthor Email-> deriving (Show, Eq, Ord)->-> getFirstAuthor (Entry author _ _ _ _) = [FirstAuthor author]->-> type EntryIxs = '[..., FirstAuthor]-> instance Indexable EntryIxs Entry where-> empty = mkEmpty-> ...-> (ixFun getFirstAuthor)+ > newtype FirstAuthor = FirstAuthor Email+ > deriving (Show, Eq, Ord)+ >+ > getFirstAuthor (Entry author _ _ _ _) = [FirstAuthor author]+ >+ > type EntryIxs = '[..., FirstAuthor]+ > instance Indexable EntryIxs Entry where+ > empty = mkEmpty+ > ...+ > (ixFun getFirstAuthor) -> entries @= (FirstAuthor "john@doe.com") -- guess what this does+ > entries @= (FirstAuthor "john@doe.com") -- guess what this does -} @@ -346,8 +346,8 @@ -- so you may use a 'Proxy'. This uses flatten to traverse values using -- their 'Data' instances. ----- > instance Indexable Type where--- > empty = ixSet [ ixGen (Proxy :: Proxy Type) ]+-- > instance Indexable '[IndexType] Type where+-- > empty = mkEmpty (ixGen (Proxy :: Proxy Type)) -- -- In production systems consider using 'ixFun' in place of 'ixGen' as -- the former one is much faster.@@ -413,7 +413,7 @@ -- | Defines objects that can be members of 'IxSet'. class (All Ord ixs, Ord a) => Indexable ixs a where -- | Defines what an empty 'IxSet' for this particular type should look- -- like. It should have all necessary indexes. Use the 'ixSet'+ -- like. It should have all necessary indexes. Use the 'mkEmpty' -- function to create the set and fill it in with 'ixFun' and 'ixGen'. empty :: IxSet ixs a @@ -540,7 +540,6 @@ ii m dkey = opI dkey x m index' :: Map ix (Set a) index' = List.foldl' ii index ds--- TODO: the "first index check" is implemented, but I don't like it insertList :: forall ixs a. (Indexable ixs a) => [a] -> IxSet ixs a -> IxSet ixs a@@ -613,7 +612,7 @@ -- | Will replace the item with the given index of type 'ix'. -- Only works if there is at most one item with that index in the 'IxSet'. -- Will not change 'IxSet' if you have more than one item with given index.-updateIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix)+updateIx :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> a -> IxSet ixs a -> IxSet ixs a updateIx i new ixset = insert new $ maybe ixset (flip delete ixset) $@@ -622,7 +621,7 @@ -- | Will delete the item with the given index of type 'ix'. -- Only works if there is at most one item with that index in the 'IxSet'. -- Will not change 'IxSet' if you have more than one item with given index.-deleteIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix)+deleteIx :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a deleteIx i ixset = maybe ixset (flip delete ixset) $ getOne $ ixset @= i@@ -819,7 +818,7 @@ -- type inference. -- -- The resulting list will be sorted in ascending order by 'ix'.--- The values in '[a]' will be sorted in ascending order as well.+-- The values in @[a]@ will be sorted in ascending order as well. groupAscBy :: forall ix ixs a. IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])] groupAscBy (IxSet _ indexes) = f (access indexes) where@@ -831,9 +830,10 @@ -- -- The resulting list will be sorted in descending order by 'ix'. ----- NOTE: The values in '[a]' are currently sorted in ascending+-- NOTE: The values in @[a]@ are currently sorted in ascending -- order. But this may change if someone bothers to add--- 'Set.toDescList'. So do not rely on the sort order of '[a]'.+-- 'Set.toDescList'. So do not rely on the sort order of the+-- resulting list. groupDescBy :: IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])] groupDescBy (IxSet _ indexes) = f (access indexes) where@@ -899,10 +899,15 @@ mappend = union -- | Statistics about 'IxSet'. This function returns quadruple--- consisting of 1. total number of elements in the set 2. number of--- declared indexes 3. number of keys in all indexes 4. number of--- values in all keys in all indexes. This can aid you in debugging--- and optimisation.+-- consisting of+--+-- 1. total number of elements in the set+-- 2. number of declared indexes+-- 3. number of keys in all indexes+-- 4. number of values in all keys in all indexes.+--+-- This can aid you in debugging and optimisation.+-- stats :: (Indexable ixs a) => IxSet ixs a -> (Int,Int,Int,Int) stats (IxSet a ixs) = (no_elements,no_indexes,no_keys,no_values) where
src/Data/IxSet/Typed/Ix.hs view
@@ -31,8 +31,8 @@ -- the core datatypes --- | 'Ix' is a 'Map' from some 'Typeable' key to a 'Set' of values for--- that key. 'Ix' carries type information inside.+-- | 'Ix' is a 'Map' from some key (of type 'ix') to a 'Set' of+-- values (of type 'a') for that key. data Ix (ix :: *) (a :: *) where Ix :: Map ix (Set a) -> (a -> [ix]) -> Ix ix a