-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Measure container capacity. Use it to safely change container. -- -- This module introduces typeclasses -- -- -- -- No, it's not about playing cards. It's about cardinalities. Wikipedia: -- "/In mathematics, the cardinality of a set is a measure of the number -- of elements of the set. For example, the set A = 2, 4, 6 contains 3 -- elements, and therefore A has a cardinality of 3./" In this package I -- dare to extend the definition a bit to "C. is a measure of the -- number of elements in a container" -- -- Usual containers are (together with their cardinality ranges): -- -- -- -- I extended this to the folowing list: -- -- -- -- Typeclass HasCardUCT together with function -- sContTrans (safe container transform) provides a facility to -- safely change container from one to another keepeng the content. If -- content doesn't fit to target container, Nothing is returned. -- However, when transforming from list [a] to (Maybe -- a) it won't check list length further first 2 elements. The -- complexity and power of this package is that it provides a facility to -- lazily evaluate amount of content in the container. -- -- To interface package functions -- -- 
--   import Data.Cardinality
--
@package Cardinality @version 0.2 module Data.Intersectable data SetsFit set NoIntersection :: SetsFit set Intersection :: set -> SetsFit set FirstInSecond :: SetsFit set SecondInFirst :: SetsFit set EqualSets :: SetsFit set class Intersectable set setFits :: Intersectable set => set -> set -> SetsFit set instance Typeable1 SetsFit instance Show set => Show (SetsFit set) module Data.NeverEmptyList data NeverEmptyList a NEL :: a -> [a] -> NeverEmptyList a -- | 
--   neverEmptyList2List (NEL h t) = h:t
--
nel2List :: NeverEmptyList a -> [a] -- | 
--   list2NeverEmptyList [] = Nothing
--
-- -- 
--   list2NeverEmptyList (h:t) = Just (NEL h t)
--
list2nel :: [a] -> Maybe (NeverEmptyList a) nelSingleton :: a -> NeverEmptyList a module Data.EmptySet data EmptySet a EmptySet :: EmptySet a instance Typeable1 EmptySet instance Eq (EmptySet a) instance Show (EmptySet a) -- | Two main assumptions (and constraints) of this module: -- --
    --
  1. Cardinality can't be negative.
    2. --
  2. For refinableC construction it is always refined -- by growing. F.e., if refinableC (7, ref_f_1) refines -- to refinableC (x, ref_f_2), then x SHOULD -- NEVER be less then 7. On this assumption relies heavily -- functions lazyIsZeroLC, -- lazyCompare2LCs, addLCToLC and also -- almost every refinement routine.
    3. --
module Data.Cardinality.Cardinality -- | Count of elements in container. It's always positive or zero. -- -- It would be best here to use Word32 instead, however, -- with Integer it's easier to catch the error of going down -- below zero (in case of Word32 0-1==4294967295 ). -- -- However it is decided not to allow the direct use of -- PreciseC data constructor, but to wrap it into -- function preciseC, which guards from the attemts to -- conctruct negative cardinality (by throwing an error). type PreciseCardinality = Integer type CurrentNotFinalPreciseCardinality = PreciseCardinality type BoundaryPreciseCardinality = CurrentNotFinalPreciseCardinality type ContinueCounting_DoWe = Bool -- | An example of this is length2 function. type ContinueRefiningCardinalityUntil = CurrentNotFinalPreciseCardinality -> (CurrentNotFinalPreciseCardinality -> ContinueCounting_DoWe) -> LazyCardinality type CardinalityRefinementState = (CurrentNotFinalPreciseCardinality, ContinueRefiningCardinalityUntil) -- | In other words: count of elements in a container, with an opportunity -- not to refine the whole content of the container (and the container's -- structure). -- -- Constructors: -- -- data LazyCardinality -- | LazyCardinality constructor. -- -- F.e., [1..] list has such cardinality. infiniteC :: LazyCardinality -- | LazyCardinality constructor. If given negative value, -- raises error. -- -- F.e., the tuple (5,6) has a precise cardinality 2. preciseC :: PreciseCardinality -> LazyCardinality -- | LazyCardinality constructor. -- -- For lists it happens, that we do not want to count all the elements of -- a container, but want to count them until some lower boundary. For -- example, I do not want to know the length of the list (which involves -- taking each element of it, and counting it in) to reason about whether -- it's content fit into the (,,) data constructor. For this -- case I only need to count till 3rd element and check, if list is -- continued. It's actual especially, when dealing with infinite lists or -- with lists, whose reading may block. -- -- For (refinableC (x0, refine_f)) important rules: -- --
    --
  1. If (refine_f x0 (<= 5)) evaluates to another -- refinableC, then it is not fully refined, but (at least) -- 5 is achieved (the precise cardinality is >= -- 5).
    2. --
  2. If x0 is 10 and (refine_f 10 (<= -- 15)) returned (refinableC (17, refine_f_2)), then it is -- known, that precise cardinality is already >= 10 + 7. In -- sight of refine_f there SHOULD be everything except for -- what's already counted in x0 (which is 10), and in -- sight of refine_f_2 there should be even less by 7 -- elements comparing to refine_f. So if total cardinality was -- 25, then (refine_f_2 17 (<= 30)) MUST return -- preciseC 25, to make 10 + 7 + 8 = 25.
    3. --
  3. The theatment of the first argument of refinement function -- refine_f must be relative. For example, given total count of -- elements = 25 , and x0 = 20 - these 20 elements are -- already counted, and in sight of refine_f there are only 5 -- last elements. Then refine_f 20 (<= 26) will result in -- preciseC 25, but(!) refine_f 10 (<= 16) MUST -- result in preciseC 15.
    4. --
-- -- Recomendations: -- --
    --
  1. If subject has infinite cardinality, it's best to determine it's -- cardinality as infiniteC at early stages and avoid -- using refinableC for it.
    2. --
refinableC :: CardinalityRefinementState -> LazyCardinality -- | Returns Nothing, ONLY if LC is refinableC (0, -- _) (according to 2nd assumption of the module). Returns Just -- True only for preciseC 0. lazyIsZeroLC :: LazyCardinality -> Maybe Bool refinementState :: LazyCardinality -> Maybe CardinalityRefinementState addPCToLC :: PreciseCardinality -> LazyCardinality -> LazyCardinality -- | For case when adding up 2 refinables, if both of them sooner or later -- refines to infiniteC, then one that returns infinity -- earlier is recommended to put as a first term. Infinity + any -- LazyCardinality = infinity. Another recommendation would be to put -- refinable that's easier to compute as a first term. addLCToLC :: LazyCardinality -> LazyCardinality -> LazyCardinality -- | 
--   foldl addLCToLC
--
-- -- See recommendations by addLCToLC. sumLCs :: [LazyCardinality] -> LazyCardinality refineCRS_Till :: CardinalityRefinementState -> BoundaryPreciseCardinality -> LazyCardinality refineCRS_TillOneAbove :: CardinalityRefinementState -> BoundaryPreciseCardinality -> LazyCardinality refineCRS_TillOneBelow :: CardinalityRefinementState -> BoundaryPreciseCardinality -> LazyCardinality crsRefinementStep :: CardinalityRefinementState -> LazyCardinality -- | Don't use it on infinite refinables not measured with -- infiniteC. refineCRS_TillEnd :: CardinalityRefinementState -> LazyCardinality -- | Wrapper around refineCRS_Till. refineTill :: LazyCardinality -> BoundaryPreciseCardinality -> LazyCardinality -- | Wrapper around refineTillOneAbove. refineTillOneAbove :: LazyCardinality -> BoundaryPreciseCardinality -> LazyCardinality -- | Wrapper around refineTillOneBelow. refineTillOneBelow :: LazyCardinality -> BoundaryPreciseCardinality -> LazyCardinality -- | Wrapper around crsRefinementStep. refinementStep :: LazyCardinality -> LazyCardinality -- | Wrapper around refineCRS_TillEnd. refineTillEnd :: LazyCardinality -> LazyCardinality -- | For equalize2Refinements (m, ref_f_1) (n, ref_f_2) finishes -- when m == n. Else refines them. Another termination condition is when -- in result of refinement one of cardinalities becomes final (not -- refinableC). equalize2Refinements :: CardinalityRefinementState -> CardinalityRefinementState -> (LazyCardinality, LazyCardinality) compare2Refinements :: CardinalityRefinementState -> CardinalityRefinementState -> (Ordering, LazyCardinality, LazyCardinality) -- | Used for instance of Ord typeclass. -- -- Together with Ordering returns also probably refined -- cardinalities for reuse. -- -- WARNING!!! When comparing refinableC with -- infiniteC , it results in LT (less -- than)! While comparing infiniteC `almostStrictCompare2LCs` -- infiniteC == EQ. That's the reason for an -- almost- prefix in function name. If there is a probability that -- refinement of refinableC may evaluate to -- infiniteC, and it's important to you, that infinities -- are equal, then before comparing this refinable, use -- refineCRS_TillEnd on it. That's laziness. -- -- Trying to compare 2 refinableCs that are actually -- infinite, but don't use infiniteC will hang the system -- (the same as if you try to determine length of an infinite list). almostStrictCompare2LCs :: LazyCardinality -> LazyCardinality -> (Ordering, LazyCardinality, LazyCardinality) -- | Won't refine refinables. According to 2nd assumption of the module: -- -- 
--   refinableC (m, _) `lazyCompare2LCs` preciseC n
--
-- -- equals to Just GT if m > n , and Nothing -- otherwise. lazyCompare2LCs :: LazyCardinality -> LazyCardinality -> Maybe Ordering -- | Used for Show typeclass instaniation. Here refinableC -- isn't refined. showLazy :: LazyCardinality -> String -- | Here refineCRS_TillEnd is applied to -- refinableC argument. showStrict :: LazyCardinality -> String -- | HasCard = "Has cardinality". In other words, "it's possible -- to measure current count of elements for this container" class HasCard a cardOf :: HasCard a => a -> LazyCardinality -- | HasCardT = "Has cardinality (for container types of kind -- (* -> *))". In other words, "it's possible to measure -- current count of elements for this container (for container types of -- kind (* -> *))" class HasCardT t cardOfT :: HasCardT t => t elem -> LazyCardinality cardOf_Unity :: () -> LazyCardinality cardOf_EmptySet :: EmptySet a -> LazyCardinality cardOf_Identity1 :: Identity a -> LazyCardinality cardOf_Maybe :: Maybe a -> LazyCardinality -- | Refinable starting from 0, uses length2 cardOf_List :: [a] -> LazyCardinality -- | Not refinable, since Map is a strict structure. cardOf_Map :: Map k e -> LazyCardinality -- | Refinable starting from 1. cardOf_NeverEmptyList :: NeverEmptyList k -> LazyCardinality -- | List length of controlable greediness. length2 :: [a] -> ContinueRefiningCardinalityUntil instance Typeable LazyCardinality instance HasCard (a, a, a, a, a, a, a, a, a, a, a, a) instance HasCard (a, a, a, a, a, a, a, a, a, a, a) instance HasCard (a, a, a, a, a, a, a, a, a, a) instance HasCard (a, a, a, a, a, a, a, a, a) instance HasCard (a, a, a, a, a, a, a, a) instance HasCard (a, a, a, a, a, a, a) instance HasCard (a, a, a, a, a, a) instance HasCard (a, a, a, a, a) instance HasCard (a, a, a, a) instance HasCard (a, a, a) instance HasCard (a, a) instance HasCardT ((,) key) instance HasCardT NeverEmptyList instance HasCard (NeverEmptyList a) instance HasCardT (Map k) instance HasCard (Map k e) instance HasCardT [] instance HasCard [a] instance HasCardT Maybe instance HasCard (Maybe a) instance HasCardT Identity instance HasCard (Identity a) instance HasCardT EmptySet instance HasCard (EmptySet a) instance HasCard () instance Show LazyCardinality instance Ord LazyCardinality instance Eq LazyCardinality module Data.Cardinality.CardinalityRange type CardinalityRange_From = LazyCardinality type CardinalityRange_To = LazyCardinality -- | Constructor: cardinalityRange CardinalityRange_From -- CardinalityRange_To data CardinalityRange -- | CardinalityRange data constructor. The range is always -- including it's boundaries. F.e., range CardinalityRange -- (preciseC 1) (preciseC 4) contains cardinalities -- [1,2,3,4]. First cardinality MUST always be less or equal to second -- one. However, we do not fully guard from such type of error - we do -- not refine refinableC, if it participates in the -- constriction. cardinalityRange :: CardinalityRange_From -> CardinalityRange_To -> CardinalityRange cr2Tuple :: CardinalityRange -> (CardinalityRange_From, CardinalityRange_From) lazyVerfyCR :: CardinalityRange_From -> CardinalityRange_To -> Maybe Bool -- | Root prototype for all subsequent "FitsIn" functions. Returns probably -- refined cardinality and range, which is useful for reuse. If returns -- EQ then subject cardinality is between boundaries (including) -- of cardinality range. -- -- Uses almostStrictCompare2LCs function. cFitsInCR_Proto :: LazyCardinality -> CardinalityRange -> (Ordering, LazyCardinality, CardinalityRange) -- | LazyCardinality fits in -- CardinalityRange? cFitsInCR :: LazyCardinality -> CardinalityRange -> Bool -- | Wrapper around cFitsInCR. fitsInCR :: HasCard a => a -> CardinalityRange -> Bool -- | Wrapper around cFitsInCR. fitsInCR_T :: HasCardT c => c a -> CardinalityRange -> Bool -- | Used in Compare2CRsError data FirstOrSecond First :: FirstOrSecond Second :: FirstOrSecond -- | Error, that may occur, when performing compare2CRs data Compare2CRsError LowerBoundaryAfterHigher :: FirstOrSecond -> CardinalityRange -> Compare2CRsError -- | This function is made hard, but fast. It tends to make minimal amount -- of comparisons, reusing refinements. compare2CRs :: CardinalityRange -> CardinalityRange -> (Either Compare2CRsError (SetsFit CardinalityRange), CardinalityRange, CardinalityRange) -- | Wrapper around setFits of typeclass -- Intersectable crFitsInCR :: CardinalityRange -> CardinalityRange -> SetsFit CardinalityRange -- | Same as cr0_Inf. crNoConstraint :: CardinalityRange -- | Only zero elements. cr0 :: CardinalityRange -- | Only one element. cr1 :: CardinalityRange -- | Zero or one element. cr0_1 :: CardinalityRange -- | Any count of elements. cr0_Inf :: CardinalityRange -- | Any nonzero count of elements. cr1_Inf :: CardinalityRange -- | Concrete count of elements. crX :: PreciseCardinality -> CardinalityRange -- | A concrete range. crXY :: PreciseCardinality -> PreciseCardinality -> CardinalityRange instance Show FirstOrSecond instance Show CardinalityRange instance Intersectable CardinalityRange instance Show Compare2CRsError module Data.Cardinality.ContTrans type CardinalityConstraint = CardinalityRange -- | 
--   cFitsInCC = cFitsInCR
--
-- -- Defined to satisfy abbreviation. cFitsInCC :: LazyCardinality -> CardinalityConstraint -> Bool -- | 
--   fitsInCC = fitsInCR
--
-- -- Defined to satisfy abbreviation. fitsInCC :: HasCard a => a -> CardinalityConstraint -> Bool -- | 
--   fitsInCC = fitsInCR_T
--
-- -- Defined to satisfy abbreviation. fitsInCC_T :: HasCardT c => c a -> CardinalityConstraint -> Bool -- | HasCardConstr = "Has cardinality constraint". In other words, -- "there is a capacity constraint for this container". class HasCardConstr a cardinalityConstraintOf :: HasCardConstr a => a -> CardinalityConstraint -- | HasCardConstrT = "Has cardinality constraint (for container -- types of kind (* -> *))". In other words, "there is a -- capacity constraint for this container type of kind (* -> -- *)". class HasCardConstrT c cardinalityConstraintOfT :: HasCardConstrT c => c a -> CardinalityConstraint -- | Wrapper around cFitsInCC. cFitsIn :: HasCardConstr b => LazyCardinality -> b -> Bool -- | Wrapper around cFitsInCC. cFitsInT :: HasCardConstrT c => LazyCardinality -> c b -> Bool -- | Wrapper around cFitsInCC. fitsIn :: (HasCard a, HasCardConstr b) => a -> b -> Bool -- | Wrapper around cFitsInCC. fitsInT :: (HasCardT c, HasCardConstrT d) => c a -> d b -> Bool -- | HasCardUCT = "Has cardinality-unsafe container transform". -- Define transform that may thow an error, if contents of from -- don't fit in to . class HasCardUCT from to uContTrans :: HasCardUCT from to => from -> to -- | HasCardUCT_T = "Has cardinality-unsafe container transform -- (for container types of kind (* -> *))". Same thing as -- HasCardUCT, but for containers of kind (* -> -- *). class HasCardUCT_T from to uContTransT :: HasCardUCT_T from to => from a -> to a type TransformError_FromTypeName = String type TransformError_ToTypeName = String type TransformError_Details = String -- | This error is used by HasCardUCT typeclass instances -- in cases when from container's contents don't fit in -- to container. uContError :: TransformError_FromTypeName -> TransformError_ToTypeName -> TransformError_Details -> a -- | Same as uContError, but for use in -- HasCardUCT_T typeclass instances uContErrorT :: TransformError_FromTypeName -> TransformError_ToTypeName -> TransformError_Details -> a -- | A wrapper around uContTrans. Contrary to it, where -- "u-" prefix stands for "unsafe-", here "s-" prefix stands for "safe-". -- This is aimed to localize and exclude case, when contents of -- from don't fit in to If HasCardUCT -- instaniated correctly, then sContTrans should never -- allow uContError to be called by subject instance. It -- should return Nothing instead. sContTrans :: (HasCard from, HasCardConstr to, HasCardUCT from to) => from -> Maybe to -- | A wrapper around uContTransT. Contrary to it, where -- "u-" prefix stands for "unsafe-", here "s-" prefix stands for "safe-". -- This is aimed to localize and exclude case, when contents of (from -- a) don't fit in (to a) . If HasCardUCT_T -- instaniated correctly, then sContTransT should never -- allow uContErrorT to be called by subject instance. It -- should return Nothing instead. sContTransT :: (HasCardT from, HasCardConstrT to, HasCardUCT_T from to) => from a -> Maybe (to a) -- | Used in ContTransError. type From_LazyCardinality = LazyCardinality -- | Used in ContTransError. type To_CardinalityConstraint = CardinalityConstraint -- | Used in ContTransError. The kind of container. data ContainerOrder -- | For container transformation we might use more informative error -- feedback. The Ordering in the middle is a relation -- between subject From_LazyCardinality and -- To_CardinalityConstraint. It's never EQ (and that's the -- reason for the error). data ContTransError ContTransError :: From_LazyCardinality -> Ordering -> To_CardinalityConstraint -> ContainerOrder -> ContTransError -- | Analogue to sContTrans. Herre, in case of cardinality -- error, a more informative data structure is returned instead of -- Nothing (as was in sContTrans). sContTrans_E :: (HasCard from, HasCardConstr to, HasCardUCT from to) => from -> Either ContTransError to -- | Analogue to sContTransT. Herre, in case of cardinality -- error, a more informative data structure is returned instead of -- Nothing (as was in sContTransT). sContTransT_E :: (HasCardT from, HasCardConstrT to, HasCardUCT_T from to) => from a -> Either ContTransError (to a) instance Show ContTransError instance Eq ContainerOrder instance Ord ContainerOrder instance Show ContainerOrder instance HasCardUCT (a, a, a, a, a, a, a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a, a, a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a, a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a, a) [a] instance HasCardUCT (a, a, a, a) [a] instance HasCardUCT (a, a, a) [a] instance HasCardUCT (a, a) [a] instance HasCardUCT [a] (a, a, a, a, a, a, a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a, a, a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a, a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a, a) instance HasCardUCT [a] (a, a, a, a) instance HasCardUCT [a] (a, a, a) instance HasCardUCT [a] (a, a) instance HasCardUCT (Map k e) (NeverEmptyList (k, e)) instance Ord k => HasCardUCT (NeverEmptyList (k, e)) (Map k e) instance HasCardUCT (Map k e) [(k, e)] instance HasCardUCT_T NeverEmptyList [] instance HasCardUCT (NeverEmptyList a) [a] instance Ord k => HasCardUCT [(k, e)] (Map k e) instance HasCardUCT_T [] NeverEmptyList instance HasCardUCT [a] (NeverEmptyList a) instance HasCardUCT (Map k e) (Maybe (k, e)) instance HasCardUCT_T NeverEmptyList Maybe instance HasCardUCT (NeverEmptyList a) (Maybe a) instance HasCardUCT_T [] Maybe instance HasCardUCT [a] (Maybe a) instance HasCardUCT (Maybe (k, e)) (Map k e) instance HasCardUCT_T Maybe NeverEmptyList instance HasCardUCT (Maybe a) (NeverEmptyList a) instance HasCardUCT_T Maybe [] instance HasCardUCT (Maybe a) [a] instance HasCardUCT (Map k e) () instance HasCardUCT [a] () instance HasCardUCT (Maybe a) () instance HasCardUCT () (Map k e) instance HasCardUCT () [a] instance HasCardUCT () (Maybe a) instance HasCardUCT (Map k e) (Identity (k, e)) instance HasCardUCT_T NeverEmptyList Identity instance HasCardUCT (NeverEmptyList a) (Identity a) instance HasCardUCT_T [] Identity instance HasCardUCT [a] (Identity a) instance HasCardUCT_T Maybe Identity instance HasCardUCT (Maybe a) (Identity a) instance HasCardUCT (Identity (k, e)) (Map k e) instance HasCardUCT_T Identity NeverEmptyList instance HasCardUCT (Identity a) (NeverEmptyList a) instance HasCardUCT_T Identity [] instance HasCardUCT (Identity a) [a] instance HasCardUCT_T Identity Maybe instance HasCardUCT (Identity a) (Maybe a) instance HasCardUCT_T (Map k) ((,) k) instance HasCardUCT (Map k e) (k, e) instance HasCardUCT_T ((,) k) (Map k) instance HasCardUCT (k, e) (Map k e) instance HasCardUCT (Map k e) (EmptySet (k, e)) instance HasCardUCT (EmptySet (k, e)) (Map k e) instance HasCardUCT_T [] EmptySet instance HasCardUCT [a] (EmptySet a) instance HasCardUCT_T EmptySet [] instance HasCardUCT (EmptySet a) [a] instance HasCardUCT_T Maybe EmptySet instance HasCardUCT (Maybe a) (EmptySet a) instance HasCardUCT_T EmptySet Maybe instance HasCardUCT (EmptySet a) (Maybe a) instance HasCardUCT () (EmptySet a) instance HasCardUCT (EmptySet a) () instance HasCardConstr (a, a, a, a, a, a, a, a, a, a, a) instance HasCardConstr (a, a, a, a, a, a, a, a, a, a) instance HasCardConstr (a, a, a, a, a, a, a, a, a) instance HasCardConstr (a, a, a, a, a, a, a, a) instance HasCardConstr (a, a, a, a, a, a, a) instance HasCardConstr (a, a, a, a, a, a) instance HasCardConstr (a, a, a, a, a) instance HasCardConstr (a, a, a, a) instance HasCardConstr (a, a, a) instance HasCardConstr (a, a) instance HasCardConstrT (Map k) instance HasCardConstr (Map k e) instance HasCardConstrT NeverEmptyList instance HasCardConstr (NeverEmptyList a) instance HasCardConstrT [] instance HasCardConstr [a] instance HasCardConstrT Maybe instance HasCardConstr (Maybe a) instance HasCardConstrT Identity instance HasCardConstr (Identity a) instance HasCardConstrT EmptySet instance HasCardConstr (EmptySet a) instance HasCardConstr () module Data.Cardinality