Data.IxSet.Typed

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)

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

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.

1. 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

1. Use the query functions below to grab data from it:

 entries @= Author "[e-mail]" @< Updated t1

Statement above will find all items in entries updated earlier than t1 by [e-mail].

1. 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"]

1. 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 "[e-mail]")  -- guess what this does

Set type

data IxSet ixs a

Set with associated indexes.

Instances

Indexable ixs a => Eq (IxSet ixs a)

Indexable ixs a => Ord (IxSet ixs a)

(Indexable ixs a, Read a) => Read (IxSet ixs a)

(Indexable ixs a, Show a) => Show (IxSet ixs a)

Indexable ixs a => Monoid (IxSet ixs a)

(Indexable ixs a, SafeCopy a) => SafeCopy (IxSet ixs a)

class (All Ord ixs, Ord a) => Indexable ixs a where

Defines objects that can be members of IxSet.

Methods

empty :: IxSet ixs a

Defines what an empty IxSet for this particular type should look like. It should have all necessary indexes. Use the ixSet function to create the set and fill it in with ixFun and ixGen.

noCalcs :: t -> ()

Function to be used for calcs in inferIxSet when you don't want any calculated values.

inferIxSet :: String -> Name -> Name -> [Name] -> Q [Dec]

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 -> r

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.

mkEmpty :: MkIxSet ixs ixs a r => r

ixFun :: Ord ix => (a -> [ix]) -> Ix ix a

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 a

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

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

Higher order operator for modifying IxSets. Use this when your final function should have the form a -> IxSet a -> IxSet a, e.g. insert or delete.

insert :: Indexable ixs a => a -> IxSet ixs a -> IxSet ixs a

Inserts an item into the IxSet. If your data happens to have a primary key this function might not be what you want. See updateIx.

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

Removes an item from the IxSet.

updateIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix) => ix -> a -> IxSet ixs a -> IxSet ixs a

Will replace the item with index k. Only works if there is at most one item with that index in the IxSet. Will not change IxSet if you have more then 1 item with given index.

deleteIx :: (Indexable ixs a, IsIndexOf ix ixs, Ord ix) => ix -> IxSet ixs a -> IxSet ixs a

Will delete the item with index k. Only works if there is at most one item with that index in the IxSet. Will not change IxSet if you have more then 1 item with given index.

Creation

fromSet :: Indexable ixs a => Set a -> IxSet ixs a

Converts a Set to an IxSet.

fromList :: Indexable ixs a => [a] -> IxSet ixs a

Converts a list to an IxSet.

Conversion

toSet :: Ord a => IxSet ixs a -> Set a

Converts an IxSet to a Set of its elements.

toList :: Ord a => IxSet ixs a -> [a]

Converts an IxSet to its list of elements.

toAscList :: forall proxy ix ixs a. IsIndexOf ix ixs => proxy ix -> IxSet ixs a -> [a]

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]

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.

getOne :: Ord a => IxSet ixs a -> Maybe a

If the IxSet is a singleton it will return the one item stored in it. If IxSet is empty or has many elements this function returns Nothing.

getOneOr :: Ord a => a -> IxSet ixs a -> a

Like getOne with a user-provided default.

Size checking

size :: Ord a => IxSet ixs a -> Int

Returns the number of unique items in the IxSet.

null :: IxSet ixs a -> Bool

Return True if the IxSet is empty, False otherwise.

Set operations

(&&&) :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a

An infix intersection operation.

(|||) :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a

An infix union operation.

union :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a

Takes the union of the two IxSets.

intersection :: Indexable ixs a => IxSet ixs a -> IxSet ixs a -> IxSet ixs a

Takes the intersection of the two IxSets.

Indexing

(@=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a

Infix version of getEQ.

(@<) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a

Infix version of getLT.

(@>) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a

Infix version of getGT.

(@<=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a

Infix version of getLTE.

(@>=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> ix -> IxSet ixs a

Infix version of getGTE.

(@><) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a

Returns the subset with indexes in the open interval (k,k).

(@>=<) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a

Returns the subset with indexes in [k,k).

(@><=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a

Returns the subset with indexes in (k,k].

(@>=<=) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> (ix, ix) -> IxSet ixs a

Returns the subset with indexes in [k,k].

(@+) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> [ix] -> IxSet ixs a

Creates the subset that has an index in the provided list.

(@*) :: (Indexable ixs a, IsIndexOf ix ixs) => IxSet ixs a -> [ix] -> IxSet ixs a

Creates the subset that matches all the provided indexes.

getEQ :: (Indexable ixs a, IsIndexOf ix ixs) => ix -> IxSet ixs a -> IxSet ixs a

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 a

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 a

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 a

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 a

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 a

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])]

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])]

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])]

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

flatten :: (Typeable a, Data a, Typeable b) => a -> [b]

Generically traverses the argument to find all occurences of values of type b and returns them as a list.

This function properly handles String as String not as [Char].

flattenWithCalcs :: (Data c, Typeable a, Data a, Typeable b) => (a -> c) -> a -> [b]

Generically traverses the argument and calculated values to find all occurences of values of type b and returns them as a list. Equivalent to:

 flatten (x,calcs x)

This function properly handles String as String not as [Char].

Debugging and optimization

stats :: Indexable ixs a => IxSet ixs a -> (Int, Int, Int, Int)

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.