úÎbXåž      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š › œ (c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableSafe ,-;=>?FTH"A specialized proxy for arguments.(Position: the right-hand side of a type.'Position: the left-hand side of a type.•Get or modify a type within a larger type. This is entirely a type-level operation, there is nothing corresponding to a value access or update.!Inhabitant of the argument proxy.(c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone%7>?AdZ 2A class for extracing "the" underlying value.  , should ideally be a coercion from some newtype wrap of a back to a.2For this common use case, in the module where newtype New a = New a is defined, an instance of The) can be created with an empty definition: -newtype New a = New a instance The (New a) a =A view pattern for discarding the wrapper around a value. f (The x) = expression x is equivalent to &f x = let x' = the x in expression x'     (c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNoneF]B The Proof^ monad is used as a domain-specific language for constructing proofs. A value of type Proof p' represents a proof of the proposition p._For example, this function constructions a proof of "P or Q" from the assumption "P and Q": }and2or :: (p && q) -> Proof (p || q) and2or pq = do p <- and_elimL pq -- or: "p <- fst <$> and_elim pq" or_introL p If the body of the proof does not match the proposition you claim to be proving, the compiler will raise a type error. Here, we accidentally try to use  or_introR instead of  or_introL: Xand2or :: (p && q) -> Proof (p || q) and2or pq = do p <- and_elimL pq or_introR presulting in the error ÿ " Couldn't match type p  with q  p  is a rigid type variable bound by the type signature for: and2or :: forall p q. (p && q) -> Proof (p || q) q  is a rigid type variable bound by the type signature for: and2or :: forall p q. (p && q) -> Proof (p || q) Expected type: Proof (p || q) Actual type: Proof (p || p) *This operator is just a specialization of (>>=)¢, but can be used to create nicely delineated chains of derivations within a larger proof. The first statement in the chain should produce a formula; (|$)@ then pipes this formula into the following derivation rule. Vand2or :: (p && q) -> Proof (p || q) and2or pq = and_elimL pq |$ or_introLþThis operator is used to create nicely delineated chains of derivations within a larger proof. If X and Y are two deduction rules, each with a single premise and a single conclusion, and the premise of Y matches the conclusion of X, then X |. Y; represents the composition of the two deduction rules. Mand2or :: (p && q) -> Proof (p || q) and2or = and_elimL |. or_introLThe (|/)_ operator is used to feed the remainder of the proof in as a premise of the first argument.A common use-case is with the Or-elimination rules or_elimL and or_elimRM, when one case is trivial. For example, suppose we wanted to prove that !R && (P or (Q and (Q implies P))) implies P: ÿ…my_proof :: r && (p || (q && (q --> p))) -> Proof p my_proof = do and_elimR -- Forget the irrelevant r. |. or_elimL given -- The first case of the || is immediate; |/ and_elim -- The rest of the proof handles the second case, |. uncurry impl_elim -- by unpacking the && and feeding the q into -- the implication (q --> p).  The rising /d is meant to suggest the bottom half of the proof getting plugged in to the Or-elimination line.The (|\)t operator is used to take the subproof so far and feed it into a rule that is expecting a subproof as a premise.A common use-case is with the Not-introduction rule  not_intro8, which has a type that fits the second argument of (|\)c. By way of example, here is a proof that "P implies Q" along with "Not Q" implies "Not P". ÿmmy_proof :: (p --> q) -> (Not p --> r) -> Not q -> Proof r my_proof impl1 impl2 q' = do modus_ponens impl1 -- This line, composed with the next, |. contradicts' q' -- form a proof of FALSE from p. |\ not_intro -- Closing the subproof above, conclude not-p. |. modus_ponens impl2 -- Now apply the second implication to conclude r.  The falling \c is meant to suggest the upper half of the proof being closed off by the Not-introduction line.Take a proof of pF and feed it in as the first premise of an argument that expects a p and a q.given3 creates a proof of P, given P as an assumption.given is just a specialization of pure / return.sorryÍ can be used to provide a "proof" of any proposition, by simply assering it as true. This is useful for stubbing out portions of a proof as you work on it, but subverts the entire proof system.#_Completed proofs should never use sorry!_axiom, like sorry4, provides a "proof" of any proposition. Unlike sorryC, which is used to indicate that a proof is still in progress, axioml is meant to be used by library authors to assert axioms about how their library works. For example: •data Reverse xs = Reverse Defn data Length xs = Length Defn rev_length_lemma :: Proof (Length (Reverse xs) == Length xs) rev_length_lemma = axiom   ž79 9 8(c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone +;<=>?QSTVmuThe  Defining P& constraint holds in any module where P has been defined as a newtype wrapper of Defn. It holds only' in that module, if the constructor of P is not exported.LLibrary authors can introduce new names in a controlled way by creating newtype wrappers of Defn. The constructor of the newtyped should *not* be exported, so that the library can retain control of how the name is introduced. 8newtype Bob = Bob Defn bob :: Int ~~ Bob bob = defn 42 An infix alias for .A value of type  a ~~ name; has the same runtime representation as a value of type a$, with a phantom "name" attached.ZIntroduce a name for the argument, and pass the named argument into the given function.Same as , but names two values at once.Same as !, but names three values at once. In the module where the name f is defined, attach the name f to a value.  Ÿ (c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone -;<=>?FQSTV‚U "An infix alias for #.#The Equals± relation is used to express equality between two entities. Given an equality, you are then able to substitute one side of the equality for the other, anywhere you please.$&Chain equalities, a la Liquid Haskell.%.Apply a function to both sides of an equality.&ƒGiven a formula and an equality over ones of its arguments, replace the left-hand side of the equality with the right-hand side.' Substitute x' for x under the function f*, on the left-hand side of an equality.( Substitute x' for x under the function f+, on the right-hand side of an equality.)cTest if the two named arguments are equal and, if so, produce a proof of equality for the names.*Reflect an equality between x and y/ into a propositional equality between the types x and y. ÿ+newtype Bob = Bob Defn bob :: Int ~~ Bob bob = defn 42 needsBob :: (Int ~~ Bob) -> Int needsBob x = the x + the x isBob :: (Int ~~ name) -> Maybe (Proof (name == Bob)) isBob = same x bob f :: (Int ~~ name) -> Int f x = case reflectEq <$> isBob x of Nothing -> 17 Just Refl -> needsBob x x +3Convert a propositional equality between the types x and y into a proof of x == y. "#$%&'()*+ #"$%&'()*+#¡"4(c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone7<>?STÄ¢ 0 A function f is  injective if  f x == f y implies x == y . The  Injective f) typeclass provides a single method, *elim_inj :: (f x == f y) -> Proof (x == y).Within the module where F is defined, you can declare F, to be injective with an empty instance: `-- {x} == {y} implies x == y. newtype Singleton x = Singleton Defn instance Injective Singleton 2A binary operation # distributes over % on the right if (x % y)  z == (x  z) % (y # z) for all x, y, and z . The DistributiveR c c') typeclass provides a single method, ;distributiveR :: Proof (c (c' x y) z == c' (c x z) (c y z)).Within the module where F and G are defined, you can declare F to distribute over G$ on the left with an empty instance: -- (x  Intersect y) Union z == (x Union z)  Intersect (y Uniony z) newtype Union x y = Union Defn newtype Intersect x y = Intersect Defn instance DistributiveR Union Intersect 4A binary operation # distributes over % on the left if x  (y % z) == (x  y) % (x # z) for all x, y, and z . The DistributiveL c c') typeclass provides a single method, ;distributiveL :: Proof (c x (c' y z) == c' (c x y) (c x z)).Within the module where F and G are defined, you can declare F to distribute over G$ on the left with an empty instance: -- x Union (y  Intersect z) == (x Union y)  Intersect (x Uniony z) newtype Union x y = Union Defn newtype Intersect x y = Intersect Defn instance DistributiveL Union Intersect 6A binary operation # is associative if x  (y  z) == (x  y)  z for all x, y, and z . The  Associative c) typeclass provides a single method, 1associative :: Proof (c x (c y z) == c (c x y) z).Within the module where F is defined, you can declare F. to be associative with an empty instance: d-- Define an associative binary operation newtype Union x y = Union Defn instance Associative Union 8A binary operation # is commutative if x  y == y  x for all x and y . The  Commutative c) typeclass provides a single method, %commutative :: Proof (c x y == c y x).Within the module where F is defined, you can declare F. to be commutative with an empty instance: c-- Define a commutative binary operation newtype Union x y = Union Defn instance Commutative Union :A binary operation # is idempotent if  x # x == x for all x . The  Idempotent c) typeclass provides a single method,  idempotent :: Proof (c p p == p).Within the module where F is defined, you can declare F- to be idempotent with an empty instance: b-- Define an idempotent binary operation newtype Union x y = Union Defn instance Idempotent Union <A binary relation R is  transitivea if, for all x, y, z, if R(x, y) is true and R(y, z) is true, then R(x, z) is true. The  Transitive r) typeclass provides a single method, -transitive :: r x y -> r y z -> Proof (r x z)/, proving R(x, z) from R(x, y) and R(y, z).Within the module where R! is defined, you can declare R) to be transitive with an empty instance: i-- Define a transitive binary relation newtype CanReach p q = CanReach Defn instance Transitive CanReach >A binary relation R is  symmetricR if, for all x and y, R(x, y) is true if and only if R(y, x) is true. The  Symmetric) typeclass provides a single method, #symmetric :: r x y -> Proof (r y x)8, proving the implication "R(x, y) implies R(y, x)".Within the module where R! is defined, you can declare R( to be symmetric with an empty instance: a-- Define a symmetric binary relation newtype NextTo p q = NextTo Defn instance Symmetric NextTo @A binary relation R is  reflexive) if, for all x, R(x, x) is true. The  Reflexive r) typeclass provides a single method, refl :: Proof (r x x)), proving R(x, x) for an arbitrary x.%Within the module where the relation R! is defined, you can declare R( to be reflexive with an empty instance: j-- Define a reflexive binary relation newtype SameColor p q = SameColor Defn instance Reflexive SameColor B transitive, with the arguments flipped.0123456789:;<=>?@AB@AA>??<==B:;;899677455233011 011233455677899:;;<==>??@AA(c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone ;<=>?FQSTVè—FAn infix alias for G.G Given a type a and a predicate p, the type a ?p represents a refinement type for a. Values of type a ?p should be values of type a that satisfy the predicate p.Values of type a ?p= have the same run-time representation as values of type a; the proposition p2 does not carry a run-time space or time cost.H Given a type a and a proposition p, the type  (a ::: p) represents a value of type a(, with an attached "ghost proof" of p.Values of the type  (a ::: p)L have the same run-time representation as values of the normal type a; the proposition p2 does not carry a run-time space or time cost.IMGiven a value and a proof, attach the proof as a ghost proof on the value.JZGiven a value and a proof, apply a function to the value but leave the proof unchanged.K\Apply an implication to the ghost proof attached to a value, leaving the value unchanged.L+Forget the ghost proof attached to a value.M%Extract the ghost proof from a value.N2For library authors: assert that a property holds.OCExistential introduction for names: given a named value of type a that satisfies a predicate p, coerce to a value of type a ?p.P<Existential elimination for names: given a value of type a ?p8, re-introduce a new name to produce a value of type a ~~ name ::: p name.QÙTake a simple function with one named argument and a named return, plus an implication relating a precondition to a postcondition of the function, and produce a function between refined input and output types. ÿ'newtype NonEmpty xs = NonEmpty Defn newtype Reverse xs = Reverse Defn rev :: ([a] ~~ xs) -> ([a] ~~ Reverse xs) rev xs = defn (reverse (the xs)) rev_nonempty_lemma :: NonEmpty xs -> Proof (NonEmpty (Reverse xs)) rev' :: ([a] ?NonEmpty) -> ([a] ?NonEmpty) rev' = rev ...? rev_nonempty_lemma R[Traverse a collection of refined values, re-introducing names in the body of the action.SSame as R(, but ignores the action's return value.TSame as ¢", with the argument order flipped.USame as £", with the argument order flipped.FGHIJKLMNOPQRSTUHIKJLMGFNOPQRSTUG¤H¥F1H1(c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone+-7;<=>?FQSTVA¸7XšThe inference rules so far have all been valid in constructive logic. Proofs in classical logic are also allowed, but will be constrained by the X typeclass.YAn infix alias for Implies.ZAn infix alias for And.[An infix alias for And.\An infix alias for And.]An infix alias for Or.^An infix alias for Or._An infix alias for Or.`Universal quantification.aExistential quantifiation.bThe implication "p implies q".cThe negation of p.dThe disjunction of p and q.eThe conjunction of p and q.fThe constant "false".gThe constant "true".h5Apply a derivation to the left side of a conjunction.i6Apply a derivation to the right side of a conjunction.j?Apply derivations to the left and right sides of a conjunction.k5Apply a derivation to the left side of a disjunction.l6Apply a derivation to the right side of a disjunction.m?Apply derivations to the left and right sides of a disjunction.n6Apply a derivation to the left side of an implication.o7Apply a derivation to the right side of an implication.p@Apply derivations to the left and right sides of an implication.q(Apply a derivation inside of a negation.rTRUE@ is always true, and can be introduced into a proof at any time.sKThe Law of Noncontradiction: for any proposition P, "P and not-P" is false.tProve "P and Q" from P and Q.¦Prove "P and Q" from Q and P.uProve "P or Q" from P.vProve "P or Q" from Q.wUProve "P implies Q" by demonstrating that, from the assumption P, you can prove Q.xaProve "not P" by demonstrating that, from the assumption P, you can derive a false conclusion.yy is an alias for x|, with a somewhat more suggestive name. Not-introduction corresponds to the proof technique "proof by contrapositive".zProve a contradiction from P and "not P".{{ is zQ with the arguments flipped. It is useful when you want to partially apply z to a negation.|IProve "For all x, P(x)" from a proof of P(*c*) with *c* indeterminate.}MProve "There exists an x such that P(x)" from a specific instance of P(c).~4From the assumption "P and Q", produce a proof of P.4From the assumption "P and Q", produce a proof of Q.€NFrom the assumption "P and Q", produce both a proof of P, and a proof of Q.gIf you have a proof of R from P, and a proof of R from Q, then convert "P or Q" into a proof of R.‚1Eliminate the first alternative in a conjunction.ƒ2Eliminate the second alternative in a conjunction.„AGiven "P imples Q" and P, produce a proof of Q. (modus ponens)… modus_ponens is just  impl_elimd with the arguments flipped. In this form, it is useful for partially applying an implication.†HModus tollens lets you prove "Not P" from "P implies Q" and "Not Q".JModus tollens is not fundamental, and can be derived from other rules: ÿ„ ----- (assumption) p --> q, p --------------------- (modus ponens) q, Not q -------------------------- (contradicts') FALSE ------------------------------------- (not-intro) Not p 9We can encode this proof tree more-or-less directly as a Proof to implement  modus_tollens: Œmodus_tollens :: (p --> q) -> Not q -> Proof (Not p) modus_tollens impl q' = do modus_ponens impl |. contradicts' q' |\ not_intro ‡From a falsity, prove anything.ˆCGiven "For all x, P(x)" and any c, prove the proposition "P(c)".‰~Given a proof of Q from P(c) with c generic, and the statement "There exists an x such that P(x)", produce a proof of Q.Š Discharge a  ClassicalJ constraint, by saying "I am going to allow a classical argument here."{NOTE: The existence of this function means that a proof should only be considered constructive if it does not have a  Classical) constraint, *and* it does not invoke  classically.‹iThe Law of the Excluded Middle: for any proposition P, assert that either P is true, or Not P is true.Œ†Proof by contradiction: this proof technique allows you to prove P by showing that, from "Not P", you can prove a falsehood.WProof by contradiction is not a theorem of constructive logic, so it requires the  Classicali constraint. But note that the similar technique of proof by contrapositive (not-introduction) isE valid in constructive logic! For comparison, the two types are: zcontradiction :: Classical => (Not p -> Proof FALSE) -> p not_intro :: (p -> Proof FALSE) -> Not p The derivation of proof by contradiction from the law of the excluded middle goes like this: first, use the law of the excluded middle to prove  p || Not p#. Then use or-elimination to prove p¾ for each alternative. The first alternative is immediate; for the second alternative, use the provided implication to get a proof of falsehood, from which the desired conclusion is derived. ÿcontradiction impl = do lem -- introduce p || Not p |$ or_elimL given -- dispatch the first, straightforward case |/ impl -- Now we're on the second case. Apply the implication.. |. absurd -- .. and, from falsity, conclude p. fDouble-negation elimination. This is another non-constructive proof technique, so it requires the  Classical constraint.€The derivation of double-negation elimination follows from proof by contradiction, since "Not (Not p)" contradicts "Not p". 5 not_not_elim p'' = contradiction (contradicts' p'') 6XYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹Œ6gfe\[Zd_^]bYc`arstuvwxyz{|}~€‚ƒ„…†‡ˆ‰XŠ‹Œhijklmnopq`§a¨b©cªd«e¬f­g® Y1Z3[3\3]2^2_2b1©1d2«2e3¬3 (c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNone7<>?STUmšA binary relation R is  antisymmetricO if, for all x and y, when R(x, y) is true, then R(y, x) is false. The  Antisymmetric) typeclass provides a single method, -antisymmetric :: r x y -> Proof (Not (r y x))H, proving the implication "R(x, y) implies the negation of R(y, x)".Within the module where R! is defined, you can declare R, to be antisymmetric with an empty instance: v-- Define an antisymmetric binary relation newtype AncestorOf p q = AncestorOf Defn instance Antisymmetric AncestorOf œA binary relation R is  irreflexive* if, for all x, R(x, x) is false. The  Irreflexive r) typeclass provides a single method, irrefl :: Proof (Not (r x x))9, proving the negation of R(x, x) for an arbitrary x.%Within the module where the relation R! is defined, you can declare R* to be irreflexive with an empty instance: ~-- Define an irreflexive binary relation newtype DifferentColor p q = DifferentColor Defn instance Irreflexive DifferentColor š›œœš››š››œ (c) Matt Noonan 2018 BSD-stylematt.noonan@gmail.comportableNoneVÓƒ  "#$%&'()*+0123456789:;<=>?@ABFGHIJKLMNOPQRSTUXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹Œš›œ¯     !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ¡¢ £ ¤ ¥ ¦§#%,¨©ª¨«¬P­®ijklmnop¯"gdp-0.0.0.2-4bXBTmLPhAF9Y97K4bcwqMData.ArgumentsData.The Logic.Proof Theory.NamedTheory.Equality Logic.Classes Data.RefinedLogic.PropositionalLogic.NegClassesGDPArgRHSLHSArgumentGetArgSetArgarg$fArgumentTYPETYPEEitherLHS$fArgumentTYPETYPEEitherRHSThetheProof|$|.|/|\$$givensorryaxiom $fMonadProof$fApplicativeProof$fFunctorProofDefiningDefn~~Namednamename2name3defn $fTheNameda==Equals==.apply substitute substituteL substituteRsame reflectEqpropEq$fArgumentTYPETYPEEqualsRHS$fArgumentTYPETYPEEqualsLHS$fArgumentTYPENatEquals1$fArgumentTYPENatEquals0 Injectiveelim_inj DistributiveR distributiveR DistributiveL distributiveL Associative associative Commutative commutative Idempotent idempotent Transitive transitive Symmetric symmetric Reflexiverefl transitive'$fReflexiveEquals$fSymmetricEquals$fTransitiveEquals? Satisfies:::...$:...>exorciseconjureassertunnamerename...? traverseP traverseP_forPforP_ $fThe:::a$fTheSatisfiesa Classical-->/\∧&&\/∨||ForAllExistsImpliesNotOrAndFALSETRUEand_mapLand_mapRand_mapor_mapLor_mapRor_map impl_mapL impl_mapRimpl_mapnot_maptrue noncontra and_intro or_introL or_introR impl_intro not_introcontrapositive contradicts contradicts' univ_introex_intro and_elimL and_elimRand_elimor_elimor_elimLor_elimR impl_elim modus_ponens modus_tollensabsurd univ_elimex_elim classicallylem contradiction not_not_elim$fDistributiveLAndAnd$fDistributiveRAndAnd$fAssociativeAnd$fSymmetricAnd$fDistributiveLOrOr$fDistributiveLOrAnd$fDistributiveLAndOr$fDistributiveROrOr$fDistributiveROrAnd$fDistributiveRAndOr$fAssociativeOr $fSymmetricOr Antisymmetric antisymmetric IrreflexiveirreflQEDbaseData.Traversabletraverse Data.Foldable traverse_SuchThat and_intro'