-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A Haskell implementation of setoid
--   
--   Setoid (<a>https://en.wikipedia.org/wiki/Setoid</a>) is a set equipped
--   with an equivalence relation. Setoid is a useful data structure in
--   cases where equivalence is chosen not to be equality. One can use it
--   to influence the memberships of the elements more strictly, as opposed
--   to sets, and run computations on unions when conflicts between
--   elements are found. You can find more deatails in <a>Data.Setoid</a>
@package setoid
@version 0.1.0.0


module Data.Setoid.Types
newtype Setoid e a
Setoid :: (Map e a) -> Setoid e a
instance GHC.Generics.Generic (Data.Setoid.Types.Setoid e a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord e) => GHC.Classes.Ord (Data.Setoid.Types.Setoid e a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq e) => GHC.Classes.Eq (Data.Setoid.Types.Setoid e a)


module Data.Setoid.Equivalence

-- | Equivalence class. It reduces the data to the part which is then being
--   tested for equality in a Setoid.
class EquivalenceBy e a
eqRel :: EquivalenceBy e a => a -> e


-- | A Haskell implementation of <a>setoid</a> - a set equipped with an
--   equivalence relation. Setoid is a useful data structure when
--   equivalence is chosen not to be equality. This allows to influence the
--   membership of the elements in a setoid. When equality is all one needs
--   - using sets is a better option.
--   
--   Here we have chosen to use a specific variant of equivalence of
--   transforming the elements to comparable intermediaries. Although it
--   does not make every equivalence relation possible, it is a practial
--   choice for a lot of computations.
--   
--   <h2>Usage</h2>
--   
--   When manipulating collections of objects in the real world, we often
--   use lists/arrays. Sometimes we need to represent some properties of
--   the relation between the elements though, and the lists do not provide
--   such possibility. This library not only provides the guarantee that a
--   setoid is correct by construction, but also that the manipulations
--   will not change its structure.
--   
--   We use it to run computations over time series of sampling data,
--   collections of users (who are unique by username or email) - to keep
--   the same structure as the one which would be used in the database with
--   unique indexes.
--   
--   To implement equivalence we chose to use a data class
--   <a>EquivalenceBy</a> which provides a method of mapping an element to
--   an intermediary, which is then used for comparison and ultimately lead
--   to a choice of the members.
--   
--   The type of a setoid is `Setoid e a` where <tt>a</tt> is the member
--   type and e is the type of equivalence intermediary. To chose the
--   members of the setoid we compare the e(quivalences) of the elements
--   with each other.
--   
--   The definition of `EquivalenceBy e a` is
--   
--   <pre>
--   class EquivalenceBy e a where
--     eqRel :: a -&gt; e
--   </pre>
--   
--   To give a simple example of how the library could be used we will
--   combine apples and oranges to a Setoid of fruit names by color. We
--   want one fruit per colour as a result and don't care if its apple or
--   an orange.
--   
--   <pre>
--   import Data.Setoid (Setoid)
--   import qualified Data.Setoid as Setoid
--   
--   data Colour = Red | Green | Blue deriving (Eq,Ord)
--   
--   instance EquivalenceBy Colour (Colour,String) where
--     eqRel = fst
--   
--   apples, organges, fruits :: Setoid Int (Int,String)
--   apples  = Setoid.fromList [(Green,"golden delicious"), (Orange,"honeycrunch")]
--   oranges = Setoid.fromList [(Orange,"seville"), (Red,"blood orange")]
--   
--   fruits = apples <a>union</a> oranges
--   -- &gt; [(Green,"golden delicious"), (Orange,"seville"), (Red,"blood orange")]
--   </pre>
--   
--   One can see the benefit of using a <a>Setoid</a> instead of
--   <a>Data.List</a> because with the latter, we would have to use
--   <a>nubBy</a> every time the data is transformed.
--   
--   When performing a <a>union</a>, our implementation would use
--   <a>max</a> between two equivalent elements to resolve the conflict.
--   Bear in mind, that the elements, though equivalent, might not be
--   equal. In the example above, ordering of <tt> "seville" </tt> is
--   bigger than <tt> "golden delicious" </tt> thus <tt> (<a>Orange</a>,
--   "seville") </tt> is chosen in the result.
--   
--   <h3>Friends of friends and computation on union</h3>
--   
--   For another example, lets get all the users of two different services
--   F and G. We are not interested in the different details, but want the
--   instance of the users to be unique.
--   
--   <pre>
--   type Email = String
--   data User = User {
--     email :: Email,
--     contacts :: Int
--     } deriving (Eq,Show)
--   
--   instance EquivalenceBy Email User where
--   eqRel u = email u
--   
--   usersF, usersG, allUsers :: Setoid Email User
--   usersF &lt;- getUsers F
--   usersG &lt;- getUsers G
--   
--   allUsers = Setoid.unionWith mergeContactDetails usersF usersG
--   
--   mergeContactDetails :: User -&gt; User -&gt; User
--   mergeContactDetails a b = User (email a) (contacts a + contacts b)
--   -- ... --
--   </pre>
--   
--   We assume that here are equivalent elements in both setoids - in this
--   case they have the same email adress. Thus we use <a>unionWith</a> to
--   merge the other details of the contact. Here, we could also do
--   computations and, for example, sum the number of friends/contacts from
--   bothe services.
--   
--   Here is also one of the shortcommings of the library.
--   mergeContactDetails choses the email of the first argument. Sinse in
--   the context of unionWith, the emails of the first and the second users
--   are the same. It is not nice from the perspective of the function
--   itself though.
--   
--   <tt> Setoid.size allUsers </tt> Would give us the amount of all unique
--   users in both services together.
--   
--   <h2>Future Work</h2>
--   
--   <ul>
--   <li>There is an unproven hypothesis about a relation between setoids
--   and Quotient Sets. It seems, that a `Setoid (a,b) (a,b,c)` is
--   equivalent to a `QuotientSet a (Setoid b (a,b,c))`. This means that
--   every QuotientSet can actually be represented as a setoid.</li>
--   <li>Performance is another issue. Current implementation uses the
--   `newtype Setoid x y = Setoid (Map x y)` which may be inefficient.</li>
--   </ul>
module Data.Setoid
data Setoid e a

-- | Equivalence class. It reduces the data to the part which is then being
--   tested for equality in a Setoid.
class EquivalenceBy e a
eqRel :: EquivalenceBy e a => a -> e

-- | Same as <a>equivalence</a>
(=~=) :: (Eq e) => Setoid e a -> Setoid e a -> Bool
infix 4 =~=

-- | Same as <a>difference</a>
(\\) :: (Ord e) => Setoid e a -> Setoid e a -> Setoid e a
infix 5 \\

-- | Same as <a>union</a>
(∪) :: (Ord e, Ord a) => Setoid e a -> Setoid e a -> Setoid e a

-- | An empty Setoid
empty :: Setoid e a

-- | Same as <a>empty</a>
ø :: Setoid e a

-- | A Setoid with a single element
singleton :: (EquivalenceBy e a) => a -> Setoid e a

-- | Combine two Setoids resolving conflicts with <a>max</a> by default.
--   This makes the union operation commutative and associative.
union :: (Ord e, Ord a) => Setoid e a -> Setoid e a -> Setoid e a

-- | Union several Setoids into one. This uses de default union variant
unions :: (Ord e, Ord a) => [Setoid e a] -> Setoid e a

-- | A generalized variant of union which accepts a function that will be
--   used when two equivalent elements are found an the conflict needs to
--   be resolved. Note that the elements are not necessarily equal
unionWith :: (Ord e) => (a -> a -> a) -> Setoid e a -> Setoid e a -> Setoid e a

-- | Difference of two setoids. Return elements of the first setoid not
--   existing in the second setoid.
difference :: (Ord e) => Setoid e a -> Setoid e a -> Setoid e a

-- | Filter a setoid. Return a setoid with elements that statisfy the
--   predicate
filter :: (Ord e) => (a -> Bool) -> Setoid e a -> Setoid e a

-- | Test if Setoid is empty
null :: Setoid e a -> Bool

-- | Get the size of a setoid
size :: Setoid e a -> Int

-- | Test if an element is a member of a setoid
member :: (EquivalenceBy e a, Ord e) => a -> Setoid e a -> Bool

-- | Test if two Setoids are equivalent i.e. if all the elements are
--   equivalent
equivalence :: (Eq e) => Setoid e a -> Setoid e a -> Bool

-- | Map a function over elements of a setoid. It resolves conflict in the
--   result by chosing the maximum one
map :: (EquivalenceBy eb b, Ord eb, Ord b) => (a -> b) -> Setoid ea a -> Setoid eb b

-- | Generalized version of map, allowing to use custom function to resolve
--   a conflict if two equivalent elements are found in the result
mapResolve :: (EquivalenceBy eb b, Ord eb) => (b -> b -> b) -> (a -> b) -> Setoid ea a -> Setoid eb b

-- | Monadic variant of a map
mapM :: (Monad m, EquivalenceBy eb b, Ord eb, Ord b) => (a -> m b) -> Setoid ea a -> m (Setoid eb b)

-- | A default variant of fromList using <a>max</a> to resolve a conflict
--   if two equivalent elements are found. Therefore it depends on Ord
--   instance of the element
fromList :: (EquivalenceBy e a, Ord e, Ord a) => [a] -> Setoid e a

-- | A generalized version of fromList, which will use a supplied funtion
--   if two equivalent elements are found in the input list
fromListWith :: (EquivalenceBy e a, Ord e) => (a -> a -> a) -> [a] -> Setoid e a

-- | Convert setoid into a List
toList :: Setoid e a -> [a]
instance GHC.Show.Show a => GHC.Show.Show (Data.Setoid.Types.Setoid e a)
instance (GHC.Classes.Ord e, GHC.Classes.Ord a) => GHC.Base.Monoid (Data.Setoid.Types.Setoid e a)