Safe Haskell | None |
---|
An efficient implementation of queryable sets.
Assume you have a family of types such as:
data Entry = Entry Author [Author] Updated Id Content deriving (Show, Eq, Ord, Data, Typeable) newtype Updated = Updated UTCTime deriving (Show, Eq, Ord, Data, Typeable) newtype Id = Id Int64 deriving (Show, Eq, Ord, Data, Typeable) newtype Content = Content String deriving (Show, Eq, Ord, Data, Typeable) newtype Author = Author Email deriving (Show, Eq, Ord, Data, Typeable) type Email = String data Test = Test deriving (Show, Eq, Ord, Data, Typeable)
- Decide what parts of your type you want indexed and make your type
an instance of
Indexable
. UseixFun
andixGen
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
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.
entries = insertList [e1, e2, e3, e4] (empty :: IxEntry) entries1 = foldr delete entries [e1, e3] entries2 = updateIx (Id 4) e5 entries
- Use the query functions below to grab data from it:
entries @= Author "john@doe.com" @< Updated t1
Statement above will find all items in entries updated earlier than
t1
by john@doe.com
.
- 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:
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:
entries @+ [Word "word1", Word "word2"]
And if you want all entries with both:
entries @* [Word "word1", Word "word2"]
- 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:
newtype FirstAuthor = FirstAuthor Email deriving (Show, Eq, Ord) getFirstAuthor (Entry author _ _ _ _) = [FirstAuthor author] type EntryIxs = '[..., FirstAuthor] instance Indexable Entry where empty = mkEmpty ... (ixFun getFirstAuthor)
entries @= (FirstAuthor "john@doe.com") -- guess what this does
- data IxSet ixs a
- class (All Ord ixs, Ord a) => Indexable ixs a where
- noCalcs :: t -> ()
- inferIxSet :: String -> Name -> Name -> [Name] -> Q [Dec]
- ixSet :: MkIxSet ixs ixs a r => Set a -> r
- mkEmpty :: MkIxSet ixs ixs a r => r
- ixFun :: Ord ix => (a -> [ix]) -> Ix ix a
- ixGen :: forall proxy a ix. (Ord ix, Data a, Typeable ix) => proxy ix -> Ix ix a
- type IndexOp = forall k a. (Ord k, Ord a) => k -> a -> Map k (Set a) -> Map k (Set a)
- change :: forall ixs a. Indexable ixs a => SetOp -> IndexOp -> a -> IxSet ixs a -> IxSet ixs a
- insert :: Indexable ixs a => a -> IxSet ixs a -> IxSet ixs a
- insertList :: forall ixs a. Indexable ixs a => [a] -> IxSet ixs a -> IxSet ixs a
- delete :: Indexable ixs a => a -> IxSet ixs a -> IxSet ixs a
- updateIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix) => ix -> a -> IxSet ixs a -> IxSet ixs a
- deleteIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix) => ix -> IxSet ixs a -> IxSet ixs a
- fromSet :: Indexable ixs a => Set a -> IxSet ixs a
- fromList :: Indexable ixs a => [a] -> IxSet ixs a
- toSet :: Ord a => IxSet ixs a -> Set a
- toList :: Ord a => IxSet ixs a -> [a]
- toAscList :: forall proxy ix ixs a. IsIndexOf ix ixs => proxy ix -> IxSet ixs a -> [a]
- toDescList :: forall proxy ix ixs a. IsIndexOf ix ixs => proxy ix -> IxSet ixs a -> [a]
- getOne :: Ord a => IxSet ixs a -> Maybe a
- getOneOr :: Ord a => a -> IxSet ixs a -> a
- size :: Ord a => IxSet ixs a -> Int
- null :: IxSet ixs a -> Bool
- (&&&) :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a
- (|||) :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a
- union :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a
- intersection :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a
- (@=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a
- (@<) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a
- (@>) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a
- (@<=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a
- (@>=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a
- (@><) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a
- (@>=<) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a
- (@><=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a
- (@>=<=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a
- (@+) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> [ix] -> IxSet ixs a
- (@*) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> [ix] -> IxSet ixs a
- getEQ :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a
- getLT :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a
- getGT :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a
- getLTE :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a
- getGTE :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a
- getRange :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> ix -> IxSet ixs a -> IxSet ixs a
- groupBy :: forall ix ixs a. IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])]
- groupAscBy :: forall ix ixs a. IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])]
- groupDescBy :: IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])]
- flatten :: (Typeable a, Data a, Typeable b) => a -> [b]
- flattenWithCalcs :: (Data c, Typeable a, Data a, Typeable b) => (a -> c) -> a -> [b]
- stats :: Indexable ixs a => IxSet ixs a -> (Int, Int, Int, Int)
Set type
Set with associated indexes.
class (All Ord ixs, Ord a) => Indexable ixs a whereSource
Defines objects that can be members of IxSet
.
Function to be used for calcs
in inferIxSet
when you don't
want any calculated values.
inferIxSet :: String -> Name -> Name -> [Name] -> Q [Dec]Source
Template Haskell helper function for automatically building an
Indexable
instance from a data type, e.g.
data Foo = Foo Int String
and
$(inferIxSet "FooDB" ''Foo 'noCalcs [''Int,''String])
will build a type synonym
type FooDB = IxSet Foo
with Int
and String
as indexes.
WARNING: The type specified as the first index must be a type which
appears in all values in the IxSet
or toList
, toSet
and
serialization will not function properly. You will be warned not to do
this with a runtime error. You can always use the element type
itself. For example:
$(inferIxSet "FooDB" ''Foo 'noCalcs [''Foo, ''Int, ''String])
ixSet :: MkIxSet ixs ixs a r => Set a -> rSource
Create an IxSet
using a list of indexes. Useful in the Indexable
empty
method. Use ixFun
and ixGen
as list elements.
instance Indexable Type where empty = ixSet [ ... ixFun getIndex1 ixGen (Proxy :: Proxy Index2Type) ]
Every value in the IxSet
must be reachable by the first index in this
list, or you'll get a runtime error.
ixFun :: Ord ix => (a -> [ix]) -> Ix ix aSource
Create a functional index. Provided function should return a list of indexes where the value should be found.
getIndexes value = [...indexes...]
instance Indexable Type where empty = ixSet [ ixFun getIndexes ]
This is the recommended way to create indexes.
ixGen :: forall proxy a ix. (Ord ix, Data a, Typeable ix) => proxy ix -> Ix ix aSource
Create a generic index. Provided example is used only as type source
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) ]
In production systems consider using ixFun
in place of ixGen
as
the former one is much faster.
Changes to set
change :: forall ixs a. Indexable ixs a => SetOp -> IndexOp -> a -> IxSet ixs a -> IxSet ixs aSource
insertList :: forall ixs a. Indexable ixs a => [a] -> IxSet ixs a -> IxSet ixs aSource
updateIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix) => ix -> a -> IxSet ixs a -> IxSet ixs aSource
Creation
Conversion
toAscList :: forall proxy ix ixs a. IsIndexOf ix ixs => proxy ix -> IxSet ixs a -> [a]Source
Converts an IxSet
to its list of elements.
List will be sorted in ascending order by the index ix
.
The list may contain duplicate entries if a single value produces multiple keys.
toDescList :: forall proxy ix ixs a. IsIndexOf ix ixs => proxy ix -> IxSet ixs a -> [a]Source
Converts an IxSet
to its list of elements.
List will be sorted in descending order by the index ix
.
The list may contain duplicate entries if a single value produces multiple keys.
Size checking
Set operations
(&&&) :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs aSource
An infix intersection
operation.
(|||) :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs aSource
An infix union
operation.
union :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs aSource
Takes the union of the two IxSet
s.
intersection :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs aSource
Takes the intersection of the two IxSet
s.
Indexing
(@=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs aSource
Infix version of getEQ
.
(@<) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs aSource
Infix version of getLT
.
(@>) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs aSource
Infix version of getGT
.
(@<=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs aSource
Infix version of getLTE
.
(@>=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs aSource
Infix version of getGTE
.
(@><) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs aSource
Returns the subset with indexes in the open interval (k,k).
(@>=<) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs aSource
Returns the subset with indexes in [k,k).
(@><=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs aSource
Returns the subset with indexes in (k,k].
(@>=<=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs aSource
Returns the subset with indexes in [k,k].
(@+) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> [ix] -> IxSet ixs aSource
Creates the subset that has an index in the provided list.
(@*) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> [ix] -> IxSet ixs aSource
Creates the subset that matches all the provided indexes.
getEQ :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs aSource
Returns the subset with an index equal to the provided key. The set must be indexed over key type, doing otherwise results in runtime error.
getLT :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs aSource
Returns the subset with an index less than the provided key. The set must be indexed over key type, doing otherwise results in runtime error.
getGT :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs aSource
Returns the subset with an index greater than the provided key. The set must be indexed over key type, doing otherwise results in runtime error.
getLTE :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs aSource
Returns the subset with an index less than or equal to the provided key. The set must be indexed over key type, doing otherwise results in runtime error.
getGTE :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs aSource
Returns the subset with an index greater than or equal to the provided key. The set must be indexed over key type, doing otherwise results in runtime error.
getRange :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> ix -> IxSet ixs a -> IxSet ixs aSource
Returns the subset with an index within the interval provided. The bottom of the interval is closed and the top is open, i. e. [k1;k2). The set must be indexed over key type, doing otherwise results in runtime error.
groupBy :: forall ix ixs a. IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])]Source
Returns lists of elements paired with the indexes determined by type inference.
groupAscBy :: forall ix ixs a. IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])]Source
Returns lists of elements paired with the indexes determined by 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.
groupDescBy :: IsIndexOf ix ixs => IxSet ixs a -> [(ix, [a])]Source
Returns lists of elements paired with the indexes determined by type inference.
The resulting list will be sorted in descending order by ix
.
NOTE: The values in '[a]' are currently sorted in ascending
order. But this may change if someone bothers to add
toDescList
. So do not rely on the sort order of '[a]'.
Index creation helpers
Debugging and optimization
stats :: Indexable ixs a => IxSet ixs a -> (Int, Int, Int, Int)Source
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.