úÎ!+™ ¶      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&'+,-7;<=>?AFQSTV]di]C decidable p is the predicate that p is not true. decidable Implicatons p   q can be lifted "through" a  into an f p   f q. decidable Implicatons p  q can be lifted "through" a  into an f p  f q. decidable p is a constraint that p can be disproven. decidableAA typeclass for provable predicates (constructivist tautologies).,A predicate is provable if, given any input a, you can generate a proof of p @@ a<. Essentially, it means that a predicate is "always true".SThis typeclass associates a canonical proof function for every provable predicate.It confers two main advatnages: JThe proof function for every predicate is available via the same name We can write ‚ instances for polymorphic predicate transformers (predicates parameterized on other predicates) easily, by refering to ) instances of the transformed predicates. decidable-The canonical proving function for predicate p. Note that  is ambiguously typed, so you always\ need to call by specifying the predicate you want to prove using TypeApplications syntax:  @MyPredicate  decidable%A typeclass for decidable predicates.-A predicate is decidable if, given any input a$, you can either prove or disprove p @@ a. A ¶ (p @@ a)# is a data type that has a branch p @@ a and · (p @@ a).WThis typeclass associates a canonical decision function for every decidable predicate.It confers two main advatnages: MThe decision function for every predicate is available via the same name We can write ‚ instances for polymorphic predicate transformers (predicates parameterized on other predicates) easily, by refering to ) instances of the transformed predicates.  decidable.The canonical decision function for predicate p. Note that   is ambiguously typed, so you always\ need to call by specifying the predicate you want to prove using TypeApplications syntax:   @MyPredicate  decidableThis is implication  !, but only in a specific context h.  decidable We say that p implies q (p   q ) if, given p  a, we can always prove q @@ a.  decidable!A proving function for predicate p. See  for more information.  decidableLike !, but only in a specific context h. decidableLike implication  , but knowing p @@ a" can only let us decidably prove q  a is true or false. decidable"A decision function for predicate p. See  for more information. decidableA  p a is a value of type p @@ a- --- that is, it is a proof or witness that p is satisfied for a. decidable%Pre-compose a function to a predicate  :: (k ~> j) ->  j -> Predicate k  decidableConvert a tradtional k ~> ¸ predicate into a .  :: (k ~> Bool) -> Predicate k  decidable a+ is a predicate that the input is equal to a. decidableThe always-false predicateCould also be defined as ¹ Void&, but this defintion gives us a free  instance. decidableThe always-true predicate.  ::  k  decidableConvert a normal '->' type constructor into a .  :: (k -> º) ->  k  decidable>A type-level predicate in Haskell. We say that the predicate P ::  k is true/satisfied by input x :: k" if there exists a value of type P @@ xD, and that it false/disproved if such a value cannot exist. (Where » is ¼S, the singleton library's type-level function application for mathcable functions)See  and H for more information on how to use, prove and decide these predicates. The kind k ~> ºò is the kind of "matchable" type-level functions in Haskell. They are type-level functions that are encoded as dummy type constructors ("defunctionalization symbols") that can be decidedly "matched" on for things like typeclass instances.1There are two ways to define your own predicates: XUsing the predicate combinators and predicate transformers in this library and the  singletonsv library, which let you construct pre-made predicates and sometimes create predicates from other predicates.AManually creating a data type that acts as a matchable predicate.\For an example of the latter, we can create the "not p" predicate, which takes a predicate p5 as input and returns the negation of the predicate: {-- First, create the data type with the kind signature you want data Not :: Predicate k -> Predicate k -- Then, write the ¼N instance, to specify the type of the -- witnesses of that predicate instance ¼ (Not p) a = (p » a) -> Void See the source of Data.Type.Predicate and Data.Type.Predicate.Logic` for simple examples of hand-made predicates. For example, we have the always-true predicate : >data Evident :: Predicate k instance Apply Evident a = Sing a #And the "and" predicate combinator: Xdata (&&&) :: Predicate k -> Predicate k -> Predicate k instance Apply (p &&& q) a = (p » a, q » a) [Typically it is recommended to create predicates from the supplied predicate combinators (d can be used for any type constructor to turn it into a predicate, for instance) whenever possible. decidable%The deciding/disproving function for  p.Must be called by applying the  to disprove:  @p  decidableCompose two implications. decidableDecide Not p based on decisions of p. decidableMap over the value inside a ¶.     1 1 11(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone+,-;<=FQSTV]diƒ¾% decidable+Two-way implication, or logical equivalence& decidable& p q is a constraint that p % q is ; that is, you can prove that p is logically equivalent to q.' decidable' p q is a constraint that p ( q is ; that is, you can prove that p implies q.( decidablep ==> q is true if q+ is provably true under the condition that p is true.) decidablep ) q is a predicate that either p and q are true, but not both.* decidablecRight-biased "or". In proofs, prioritize a proof of the right side over a proof of the left side.+ decidablebLeft-biased "or". In proofs, prioritize a proof of the left side over a proof of the right side., decidablep , q is a predicate that either p and q are true.- decidablep - q is a predicate that both p and q are true.. decidableDecide p - q based on decisions of p and q./ decidableDecide p , q based on decisions of p and q.0 decidableDecide p ) q based on decisions of p and q.1 decidableIf q is provable, then so is p ( q.$This can be used as an easy plug-in  instance for p ( q if q is : Hinstance Provable (p ==> MyPred) where prove = proveImplies @MyPred UThis instance isn't provided polymorphically because of overlapping instance issues.2 decidableFrom   a<, you can prove anything. Essentially a lifted version of ½.3 decidable# can be proven from all predicates.4 decidableWe cannot have both p and  p.5 decidable¿If only this worked, but darn overlapping instances. Same for p ==> p ||| q and p &&& q ==> p :( q) ==> instance Provable (p &&& Not p ==> Impossible) where prove = excludedMiddle @p)If p implies q, then not q implies not p.6 decidableReverse direction of 5. Only possible if q is ! on its own, without the help of p%, which makes this much less useful.7 decidable+Logical double negation. Only possible if p is .8 decidableIf p - q is true, then so is p.9 decidableIf p - q is true, then so is q.: decidableIf p is true, then so is p , q.; decidableIf q is true, then so is p , q.> decidablePicks the proof of p‡. Note that this is instance has stronger constraints than is strictly necessary; we should really only have to require that either p or q is true.%&'()*+,-./0123456789:;-.,/+*)0(1'%&23475689:;%1(1,2-3(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&',-.0;<=>?FQSTV]diÇOD decidableDTrivially witness an item in the second field of a type-level tuple.F decidable Witness an item in a type-level ¾U by either indicating that it is the "head", or by providing an index in the "tail".I decidable Witness an item in a type-level ¿ j by proving the ¿ is À.K decidable Witness an item in a type-level Á by proving the Á is Â.M decidable<Witness an item in a type-level list by providing its index.P decidableA P f p is a predicate on a collection as that no a in as satisfies predicate p.Q decidablePredicate that a given  as :: f k0 is not empty, and has at least one item in it.R decidablePredicate that a given  as :: f k! is empty and has no items in it.S decidable_Typeclass for a type-level container that you can quantify or lift type-level predicates over.T decidablec, but providing an b.U decidabled, but providing an b.V decidablee, but providing an b.W decidableAn W f p% is a predicate testing a collection  as :: f a for the fact that all items in as satisfy p=. Represents the "forall" quantifier over a given universe.This is mostly useful for its , , and / instances, which lets you lift predicates on p to predicates on W f p.X decidableA X p as! is a witness that the predicate p a is true for all items a in the type-level collection as.[ decidableAn [ f p% is a predicate testing a collection  as :: f a) for the fact that at least one item in as satisfies p=. Represents the "exists" quantifier over a given universe.This is mostly useful for its  and / instances, which lets you lift predicates on p to predicates on [ f p.\ decidableA \ p as* is a witness that, for at least one item a in the type-level collection as, the predicate p a is true.^ decidable^ f as# is a predicate that a given input a is a member of collection as.b decidableCA witness for membership of a given item in a type-level collectionc decidableLifts a predicate p on an individual a( into a predicate that on a collection as that is true if and only if any item in as# satisfies the original predicate.&That is, it turns a predicate of kind  k ~> Type into a predicate of kind  f k ~> Type.-Essentially tests existential quantification.d decidableLifts a predicate p on an individual a( into a predicate that on a collection as that is true if and only if all items in as# satisfies the original predicate.&That is, it turns a predicate of kind  k ~> Type into a predicate of kind  f k ~> Type.+Essentially tests universal quantification.e decidableIf p a is true for all values a in as# under some (Applicative) context h, then you can create an W p as! under that Applicative context h.Can be useful with Ã. (which is basically unwrapping and wrapping W ), or with ÁU (which can express predicates that are either provably true or not provably false).`In practice, this can be used to iterate and traverse and sequence actions over all "items" in as.f decidableg, but providing an b.g decidableIf p a is true for all values a in as, then we have W p as). Basically witnesses the definition of W.h decidable5Extract the item from the container witnessed by the bÄ decidableSplit a Å as into a proof that all a in as exist.i decidable:Automatically generate a witness for a member, if possiblej decidablek but with access to the index.k decidableA Æ over all items in a collection. T decidablepredicate on value decidablepredicate on collectionU decidablepredicate on value decidablepredicate on collectionV decidablepredicate on value in context decidable"predicate on collection in contextc decidablepredicate on value decidablepredicate on collectiond decidablepredicate on value decidablepredicate on collectione decidablepredicate on value in context decidable"predicate on collection in contextf decidablealways-true predicate on value decidable#always-true predicate on collectiong decidablealways-true predicate on value decidable#always-true predicate on collectionh decidableWitness decidable Collection(DEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijk(b^STUVMNOKLIJFGHDEWXYZ[\]PRQcdegfkjhia`_(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&',-;<=>?FQSTV]diçq ƒ decidable„, but providing an b.„ decidableLifts a predicate p on an individual a( into a predicate that on a collection as that is true if and only if no item in as# satisfies the original predicate.&That is, it turns a predicate of kind  k ~> Type into a predicate of kind  f k ~> Type.… decidable†, but providing an b.† decidableIf there exists an a s.t. p a , and if p implies q, then there must exist an a s.t. q a.‡ decidableˆ, but providing an b.ˆ decidable If for all a we have p a , and if p implies q, then for all a we must also have p a.‰ decidableŠ, but providing an b.Š decidableIf p implies q under some context h, and if there exists some a such that p a, then there must exist some a such that p q under that context h.h might be something like, say, ÁF, to give predicate that is either provably true or unprovably false.-Note that it is not possible to do this with p a -> ¶ (q a). This is if the p a -> ¶ (q a)< implication is false, there it doesn't mean that there is no a such that q a), necessarily. There could have been an a where p does not hold, but q does.‹ decidableŒ, but providing an b.Œ decidableIf p implies q under some context h, and if we have p a for all a, then we must have q a for all a under context h. decidableŒ, but providing an b.Ž decidable If we have p a for all a, and p a can be used to test for q a, then we can test all as for q a. ƒ decidablepredicate on value decidablepredicate on collection„ decidablepredicate on value decidablepredicate on collection… decidable implication‡ decidable implication‰ decidableimplication in contextŠ decidableimplication in context‹ decidableimplication in contextŒ decidableimplication in context decidabledecidable implicationPUTWXYZ[\]cdƒ„…†‡ˆ‰Š‹ŒŽ[\]PcT„ƒ†…Š‰WXYZdUˆ‡Œ‹Ž(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone+,-7;<=FSTV]di z  decidable f$ takes a parmaeterized predicate on k (testing for a v1) and turns it into a parameterized predicate on f k (testing for a v). It "lifts" the domain into f.An  f p as# is a predicate taking an argument a and testing if p a ::  k is satisfied for any item in  as :: f k.A — k v tests if a k can create some v. The resulting — (f k) v tests if any k in f k can create some v. decidableA — (f k) k. Parameterized on an  as :: f k8, returns a predicate that is true if there exists any a :: k in as. Essentially Q.‘ decidableA constraint that a — k v/ s "selectable". It means that for any input x :: k, we can always find a y :: v that satisfies  P x @@ y. We can "select" that y, no matter what.’ decidableA constraint that a — k v0 is "searchable". It means that for any input x :: k/, we can prove or disprove that there exists a y :: v that satisfies P x @@ y. We can "search" for that y,, and prove that it can or cannot be found.“ decidablePre-compose a function to a —. Is essentially Ç (È)T, but unfortunately defunctionalization doesn't work too well with that definition.” decidable Promote a  v to a — k v, ignoring the k input.• decidableFlip the arguments of a —.– decidableDConvert a parameterized predicate into a predicate on the parameter.A – p is a predicate on p :: — k v that tests a k# for the fact that there exists a v where — k v is satisfied.$Intended as the basic interface for —, since it turns a — into a normal , which can have  and  instances.!For some context, an instance of  (– P), where P :: — k v, means that for any input x :: k, we can always find a y :: v such that we have P x  y.5In the language of quantifiers, it means that forall x :: k, there exists a y :: v such that P x  y.For an instance of  (– P), it means that for all x :: k8, we can prove or disprove the fact that there exists a y :: v such that P x  y.— decidable A parameterized predicate. See – for more information.˜ decidable$The deciding/searching function for ’ p.Must be called by applying the —: ˜ @p ™ decidable#The proving/selecting function for ‘ p.Must be called by applying the —: ™ @p ‘’“”•–—˜™ —•”“–‘™’˜(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&',-;<=>?FQSTV]di"¢ decidableA ¢ f p8 is a predicate that some decidable subset of an input as is true.£ decidableA £ f p  as describes a  decidable" subset of type-level collection as.¦ decidable Create a ¢ from a predicate.§ decidableTurn a ¢ into a list (or any É) of satisfied predicates.¨ decidable Restrict a ¢9 to a single (arbitrary) member, or fail if none exists.© decidableConstruct an empty subset.ª decidableConstruct a full subset« decidableTest if a subset is empty.¬ decidable0Combine two subsets based on a decision function­ decidable0Combine two subsets based on a decision function® decidableSubset intersection¯ decidable Subset union° decidableSymmetric subset difference± decidable;Test if a subset is equal to the entire original collection² decidable³, but providing an b.³ decidableMMap a bidirectional implication over a subset described by that implication.FImplication needs to be bidirection, or otherwise we can't produce a  decidable subset as a result.¢£¤¥¦§¨©ª«¬­®¯°±²³¢£¤¥¦®¯°­¬³²§¨±«©ªSafeðÊËÌÍÎÏÐÑÒ      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKKLMNOOPPQRSTUVWXYZ[\\]^__`abcdefghijklmnopqrstuv)wxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œtužŸ ¡¢¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶´µ·¸¹º´»¼¸¹½´¾¿´¾ÀÁÂÃÁÄÅÁÆÇÁÆÈÁÄÉÁÄÊÁËÌÍ´¾ÎÁÏÐÁÄÑÁÄÒÁÄÓÔÕÖ×ØÙÚÛÜ(decidable-0.1.0.0-FimngCvJ4ooFIdhVW2QkXzData.Type.PredicateData.Type.Predicate.LogicData.Type.Universe"Data.Type.Predicate.QuantificationData.Type.Predicate.ParamData.Type.Universe.SubsetPaths_decidableNotTFunctortmapDFunctordmap DisprovableProvableprove Decidabledecide-->#-->Prove-?>#-?>DecideWitgetWitPMapBoolPredEqualTo ImpossibleEvidentTyPred PredicatedisprovecompImpl decideNot mapDecision$fProvablek1.@#@$$$$fProvablek1TyCon$fDecidablek1.@#@$$$$fDecidablek1TyCon$fDecidablekTyCon$fDecidablek1Not$fProvablek1Not<==>EquivImplies==>^^^||^^|||||&&& decideAnddecideOr decideXor proveImplies explosionatomexcludedMiddlecontrapositivecontrapositive'doubleNegation projAndFst projAndSnd injOrLeft injOrRight$fProvablek1&&&$fDecidablek1&&&$fProvablek1|||$fDecidablek1|||$fProvablek1==>$fDecidablek1==>$fProvablek1==>0$fDecidablek1==>0SndNEIndexNEHeadNETailIsRightIsJustIndexIZISNoneNotNullNullUniverse idecideAny idecideAlligenAllAAllWitAll runWitAllAnyWitAnyInElemSym2ElemSym1ElemSym0Elem decideAny decideAllgenAllAigenAllgenAllindexpickElem ifoldMapUni foldMapUni$fDFunctork1fAll$fTFunctork1fAll$fTFunctork1fAny$fProvablefAll$fDecidablefAll$fDecidablefAny$fProvablef==>$fDecidablef==> $fUniverse[]$fUniverseMaybe$fDecidablekTyCon0$fUniverseEither$fDecidablekTyCon1$fUniverseNonEmpty$fDecidablekTyCon2 $fUniverse(,)$fDecidablekTyCon3 $fShowSnd $fShowNEIndex $fShowIsRight $fShowIsJust $fShowIndex idecideNone decideNone ientailAny entailAny ientailAll entailAll ientailAnyF entailAnyF ientailAllF entailAllFidecideEntailAlldecideEntailAllAnyMatchInP Selectable SearchablePPMapConstPPFlipPPFound ParamPredsearchselect$fProvablekFound$fDecidablekFound$fProvablef==>0$fDecidablef==>0$fDecidablefFound$fDecidablefFound0Subset WitSubset runWitSubset makeSubset subsetToList subsetToAny emptySubset fullSubset subsetToNone imergeSubset mergeSubset intersectionunionsymDiff subsetToAll imapSubset mapSubset$fProvablefSubset$fDecidablefSubset'singletons-2.4.1-CPkrVyNL0Sy7pQw5p6j80uData.Singletons.DecideDecisionRefutedghc-prim GHC.TypesBoolData.Singletons.Prelude.Base ConstSym1TypeData.Singletons.Internal@@Applybase Data.VoidabsurdGHC.BaseNonEmpty Data.EitherEitherRightMaybeJustData.Functor.IdentityIdentity splitSingSing Data.FoldablefoldMapflip. Alternativeversion getBinDir getLibDir getDynLibDir getDataDir getLibexecDir getSysconfDirgetDataFileName