-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Efficient relational queries on Haskell sets.
--
-- Just pick which parts of your data structures you want indexed using
-- an easy to use template-haskell function. Spare yourself the need to
-- write, run, and maintain code that marshalls your data to/from an
-- external relational database just for efficient queries.
-- happstack-ixset relies on generics and TH to spare you the boilerplate
-- normally required for such tasks.
@package happstack-ixset
@version 6.0.1
-- | This module defines typable indices and convenience functions. Should
-- be probably considered private to Happstack.Data.IxSet.
module Happstack.Data.IxSet.Ix
-- | Ix is a Map from some Typeable key to a
-- Set of values for that key. Ix carries type information
-- inside.
data Ix a
Ix :: (Map key (Set a)) -> (a -> [key]) -> Ix a
-- | Convenience function for inserting into Maps of Sets as
-- in the case of an Ix. If they key did not already exist in the
-- Map, then a new Set is added transparently.
insert :: (Ord a, Ord k) => k -> a -> Map k (Set a) -> Map k (Set a)
-- | Convenience function for deleting from Maps of Sets. If
-- the resulting Set is empty, then the entry is removed from the
-- Map.
delete :: (Ord a, Ord k) => k -> a -> Map k (Set a) -> Map k (Set a)
-- | Helper function to insert a list of elements into a set.
insertList :: (Ord a, Ord k) => [(k, a)] -> Map k (Set a) -> Map k (Set a)
-- | Helper function to delete a list of elements from a set.
deleteList :: (Ord a, Ord k) => [(k, a)] -> Map k (Set a) -> Map k (Set a)
-- | Take union of two sets.
union :: (Ord a, Ord k) => Map k (Set a) -> Map k (Set a) -> Map k (Set a)
-- | Take intersection of two sets
intersection :: (Ord a, Ord k) => Map k (Set a) -> Map k (Set a) -> Map k (Set a)
instance [overlap ok] Typeable1 Ix
instance [overlap ok] (Data ctx a, Sat (ctx (Ix a))) => Data ctx (Ix a)
instance [overlap ok] Data a => Data (Ix a)
-- | An efficient implementation of queryable sets.
--
-- Assume you have a type like:
--
--
-- data Entry = Entry Author [Author] Updated Id Content
-- newtype Updated = Updated EpochTime
-- newtype Id = Id Int64
-- newtype Content = Content String
-- newtype Author = Author Email
-- type Email = String
--
--
--
-- - Decide what parts of your type you want indexed and make your type
-- an instance of Indexable. Use ixFun and ixGen to
-- build indexes:
--
--
--
-- instance Indexable Entry where
-- empty = ixSet
-- [ ixGen (Proxy :: Proxy Author) -- out of order
-- , ixGen (Proxy :: Proxy Id)
-- , ixGen (Proxy :: Proxy Updated)
-- , ixGen (Proxy :: Proxy Test) -- bogus index
-- ]
--
--
--
-- - Use insert, delete, updateIx, deleteIx
-- and empty to build up an IxSet collection:
--
--
--
-- entries = foldr insert empty [e1,e2,e3,e4]
-- entries' = foldr delete entries [e1,e3]
-- entries'' = update e4 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:
--
--
-- getWords (Entry _ _ _ _ (Content s)) = map Word $ words s
--
-- instance Indexable Entry where
-- empty = ixSet [ ...
-- 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
--
-- getFirstAuthor (Entry author _ _ _ _) = [FirstAuthor author]
--
-- instance Indexable Entry where
-- ...
-- empty = ixSet [ ...
-- ixFun getFirstAuthor
-- ]
--
-- entries @= (FirstAuthor "john@doe.com") -- guess what this does
--
module Happstack.Data.IxSet
-- | Set with associatex indexes.
data IxSet a
-- | Indexable class defines objects that can be members of
-- IxSet.
class Indexable a
empty :: Indexable a => IxSet a
-- | Function to be used for calcs in inferIxSet when you
-- don't want any calculated values.
noCalcs :: t -> ()
-- | 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 by runtime error. You can always use the element
-- type itself. For example:
--
--
-- $(inferIxSet "FooDB" ''Foo 'noCalcs [''Foo, ''Int, ''String])
--
inferIxSet :: String -> Name -> Name -> [Name] -> Q [Dec]
-- | Create an IxSet using a list of indexes. Useful in
-- Indexable empty method. Use ixFun and
-- ixGen as list elements.
--
--
-- instance Indexable Type where
-- empty = ixSet [ ...
-- ixFun getIndex1
-- ixGen (Proxy :: Proxy Index2Type)
-- ]
--
--
-- First index in the list must contain all objects in set, doing
-- otherwise result in runtime error.
ixSet :: [Ix a] -> IxSet a
-- | Create a functional index. Provided function should return a list of
-- indexes where value should be found.
--
--
-- getIndexes value = [...indexes...]
--
--
--
-- instance Indexable Type where
-- empty = ixSet [ ixFun getIndexes ]
--
--
-- This is the recommended way to create indexes.
ixFun :: (Ord b, Typeable b) => (a -> [b]) -> Ix a
-- | Create a generic index. Provided example is used only as type source
-- so you may use a Proxy. The ixGen uses flatten to
-- traverse value using its Data instance.
--
--
-- 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.
ixGen :: (Data a, Ord b, Typeable b) => Proxy b -> Ix a
type IndexOp = forall k a. (Ord k, Ord a) => k -> a -> Map k (Set a) -> Map k (Set 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.
change :: (Typeable a, Indexable a, Ord a) => IndexOp -> a -> IxSet a -> IxSet a
-- | Inserts an item into the IxSet. If your data happens to have
-- primary key this function might not be what you want. See
-- updateIx.
insert :: (Typeable a, Ord a, Indexable a) => a -> IxSet a -> IxSet a
-- | Removes an item from the IxSet.
delete :: (Typeable a, Ord a, Indexable a) => a -> IxSet a -> IxSet 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.
updateIx :: (Indexable a, Ord a, Typeable a, Typeable k) => k -> a -> IxSet a -> IxSet 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.
deleteIx :: (Indexable a, Ord a, Typeable a, Typeable k) => k -> IxSet a -> IxSet a
-- | Converts a Set to an IxSet.
fromSet :: (Indexable a, Ord a, Typeable a) => Set a -> IxSet a
-- | Converts a list to an IxSet.
fromList :: (Indexable a, Ord a, Typeable a) => [a] -> IxSet a
-- | Converts an IxSet to a Set of its elements.
toSet :: Ord a => IxSet a -> Set a
-- | Converts an IxSet to its list of elements.
toList :: Ord a => IxSet a -> [a]
-- | Converts an IxSet to its list of elements.
--
-- List will be sorted in ascending order by the index k.
--
-- The list may contain duplicate entries if a single value produces
-- multiple keys.
toAscList :: (Indexable a, Typeable a, Typeable k) => Proxy k -> IxSet a -> [a]
-- | Converts an IxSet to its list of elements.
--
-- List will be sorted in descending order by the index k.
--
-- The list may contain duplicate entries if a single value produces
-- multiple keys.
toDescList :: (Indexable a, Typeable a, Typeable k) => Proxy k -> IxSet a -> [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.
getOne :: Ord a => IxSet a -> Maybe a
-- | Like getOne with a user provided default.
getOneOr :: Ord a => a -> IxSet a -> a
-- | Returns the number of unique items in the IxSet.
size :: Ord a => IxSet a -> Int
-- | Return True if the IxSet is empty, False
-- otherwise.
null :: IxSet a -> Bool
-- | An infix intersection operation.
(&&&) :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a
-- | An infix union operation.
(|||) :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a
-- | Takes the union of the two IxSets.
union :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a
-- | Takes the intersection of the two IxSets.
intersection :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a
-- | Infix version of getEQ.
(@=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a
-- | Infix version of getLT.
(@<) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a
-- | Infix version of getGT.
(@>) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a
-- | Infix version of getLTE.
(@<=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a
-- | Infix version of getGTE.
(@>=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a
-- | Returns the subset with indexes in the open interval (k,k).
(@><) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a
-- | Returns the subset with indexes in [k,k).
(@>=<) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a
-- | Returns the subset with indexes in (k,k].
(@><=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a
-- | Returns the subset with indexes in [k,k].
(@>=<=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a
-- | Creates the subset that has an index in the provided list.
(@+) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> [k] -> IxSet a
-- | Creates the subset that matches all the provided indexes.
(@*) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> [k] -> IxSet 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.
getEQ :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet 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.
getLT :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet 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.
getGT :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet 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.
getLTE :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet 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.
getGTE :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet 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.
getRange :: (Indexable a, Typeable k, Ord a, Typeable a) => k -> k -> IxSet a -> IxSet a
-- | Returns lists of elements paired with the indexes determined by type
-- inference.
groupBy :: (Typeable k, Typeable t) => IxSet t -> [(k, [t])]
-- | Returns lists of elements paired with the indexes determined by type
-- inference.
--
-- The resulting list will be sorted in ascending order by k.
-- The values in '[t]' will be sorted in ascending order as well.
groupAscBy :: (Typeable k, Typeable t) => IxSet t -> [(k, [t])]
-- | Returns lists of elements paired with the indexes determined by type
-- inference.
--
-- The resulting list will be sorted in descending order by k.
--
-- NOTE: The values in '[t]' 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 '[t]'.
groupDescBy :: (Typeable k, Typeable t) => IxSet t -> [(k, [t])]
-- | 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].
flatten :: (Typeable a, Data a, Typeable b) => 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].
flattenWithCalcs :: (Data c, Typeable a, Data a, Typeable b) => (a -> c) -> a -> [b]
-- | 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.
stats :: Ord a => IxSet a -> (Int, Int, Int, Int)
instance [overlap ok] Typeable1 IxSet
instance [overlap ok] Data a => Data (IxSet a)
instance [overlap ok] (Indexable a, Typeable a, Ord a) => Monoid (IxSet a)
instance [overlap ok] (Ord a, Read a, Typeable a, Indexable a) => Read (IxSet a)
instance [overlap ok] (Ord a, Show a) => Show (IxSet a)
instance [overlap ok] (Indexable a, Ord a, Data a, Default a) => Default (IxSet a)
instance [overlap ok] (Data ctx a, Sat (ctx (IxSet a)), Sat (ctx [a]), Indexable a, Data a, Ord a) => Data ctx (IxSet a)
instance [overlap ok] (Serialize a, Ord a, Typeable a, Indexable a) => Serialize (IxSet a)
instance [overlap ok] Version (IxSet a)
instance [overlap ok] (Eq a, Ord a, Typeable a) => Ord (IxSet a)
instance [overlap ok] (Eq a, Ord a, Typeable a) => Eq (IxSet a)