h$}z      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~               ,Conflict-directed clause learning utilities.(c) Tom Harding, 2020MITNone&+< i holmesA set of rules. We use this to represent our global list of "no good" configurations. If any cell's provenance ever contains one of the rules in our global set, we know this computation will eventually end in failure.holmes.A set of value identifiers and their settings.holmesThe index of the chosen value# of a parameter in our computation.holmes,The index of a parameter in our computation.holmesGenerate unique rules for a set of possible values for a given parameter. For example, if we assign parameter #1 possible values [1 .. 4]/, this function might generate something like: [ ( -(1, 0) && -(1, 1), 1 ) , ( -(1, 0) && (1, 1), 2 ) , ( (1, 1) && -(1, 1), 3 ) , ( (1, 1) && (1, 1), 4 ) ] holmes List all the (Major, Minor) pairs in a .holmesToggle the boolean switch of a (Major, Minor) pair.holmes Remove a (Major, Minor) pair from a .holmesIf a group implies (A && B) and  (A && -B) then the B/ seems to be irrelevant, so we can refine the  to A). This hopefully means we can eliminate more' branches, and get to an answer faster!holmes Does any  in this  subsume the given ?holmesIf x  y, then the set of switches in x is a strict subset of the switches in y. In other words, the x  will match  everything that y will.holmes Add a new  to a . Attempt to calculate any " of the rule, and generalise the  as far as possible.#Configuration for input parameters.(c) Tom Harding, 2020MIT Safe-Inferred#$holmesThe simplest way of generating an input configuration is to say that a problem has m# variables that will all be one of n2 possible values. For example, a sudoku board is 81 variables of 9 possible values. This class allows us to generate these simple input configurations like a game of countdown: "81 from 1 .. 9, please, Carol!"holmesDifferent parameter types will have different representations for their values. The  type means that I can say 81  [1 .. 9]?, and have the parameter type determine how it will represent 1, for example. It's a little bit of syntactic sugar for the benefit of the user, so they don't need to know as much about how the parameter types work to use the library.holmes Generate m variables who are one of n values. 81  [1 .. 9], 5  [ True, False ] , and so on.holmesAn input configuration.This stores both an  configuration of input parameters, as well as a function that can look for ways to 7 an input. In other words, if the initial value is an Data.JoinSemilattice.Intersect of [1 .. 5], the refinements might be  ( values of every remaining possibility.holmes"For debugging purposes, produce a % of all possible refinements that a  might produce for a given problem. This set could potentially be very large!.Values with differing levels of "definedness".(c) Tom Harding, 2020MIT Safe-Inferred +58:<=)holmes3Defines simple "levels of knowledge" about a value. holmes'Nothing has told me what this value is. holmes+Everyone who has told me this value agrees. holmes2Two sources disagree on what this value should be.  1Solving problems by reducing lists of candidates.(c) Tom Harding, 2020MITNone&+7<>rholmes$A set type with intersection as the  operation.!holmes Create an  from a list of candidates."holmes-Return a list of candidates stored within an .#holmesRun an action only if a single candidate remains.$holmesDelete a candidate from an .%holmes Return an  of all possible candidates except those in the given . The  of all candidates is assumed to be .&holmes Filter an  with a predicate.'holmes Convert a  to an .(holmes Map over an  with a given function.*holmesCreate a singleton .+holmesCount the candidates in an .,holmes Convert an  to a .-holmes Merge two  values with set union..holmes Produce a  with the given initial value, where the > function just tries each remaining candidate as a singleton. !"#$%&'()*+,-. !"#$%&'()*+,-. 4Performant join semilattice-based knowledge-merging.(c) Tom Harding, 2020MITNone5<":holmesJoin semilattice  specialised for propagator network needs. Allows types to implement the notion of "knowledge combination".;holmesMerge the news (right) into the current value (left), returning an instruction on how to update the network.<holmesThe result of merging some news into a cell's current knowledge.=holmes6We've learnt nothing; no updates elsewhere are needed.>holmes-We've learnt something; fire the propagators!?holmes3We've hit a failure state; discard the computation.:;<>=? ,Relationships between values and their sums.(c) Tom Harding, 2020MITNone9P@holmes0A relationship between two values and their sum.Bholmes7A relationship between two values and their difference.Cholmes0A relationship between a value and its negation.@ABCAn interface for the primitive cell operations in a propagator network.(c) Tom Harding, 2020MITNone+1w DholmesThe DSL for network construction primitives. The following interface provides the building blocks upon which the rest of the library is constructed.If you are looking to implement the class yourself, you should note the lack of functionality for ambiguity/searching. This is deliberate: for backtracking search (as opposed to truth maintenance-based approaches), the ability to create computation branches dynamically makes it much harder to establish a reliable mechanism for tracking the effects of these choices.&For example: the approach used in the  implementation is to separate the introduction of ambiguity into one definite, explicit step, and all parameters must be declared ahead of time so that they can be assigned indices. Other implementations should feel free to take other approaches, but these will be implementation-specific.EholmesThe type of cells for this particular implementation. Typically, it's some sort of mutable reference (, , or similar), but the implementation may attach further metadata to the individual cells.Fholmes Mark the current computation as failed. For more advanced implementations that utilise backtracking and branching, this is an indication that we should begin a different branch of the search. Otherwise, the computation should simply fail without a result.GholmesCreate a new cell with the given value. Although this value's type has no constraints, it will be immutable unless it also implements :, which exists to enforce  monotonic updates.HholmesCreate a callback that is fired whenever the value in a given cell is updated. Typically, this callback will involve potential writes to other cells based on the current value of the given cell. If such a write occurs, we say that we have  propagated. information from the first cell to the next.Iholmes y -> z. When we view it as a  relationship4, we see that it's actually a relationship between three values: x, y, and z.*Given a function that takes everything we  currently know about these three values, and returns three "updates" based on what each can learn from the others, we can lift our three-way relationship (which, again, we can intuit as a multi-directional binary function) into a network as a three-way  propagator3. As an illustrative example, we might convert the  function into something like: addR :: (Int, Int, Int) -> (Int, Int, Int) addR ( a, b, c ) = ( c - b, c - a, a + b ) In practice, these values must be : values (unlike ), and so any of them could be , or less-than-well-defined. This function will take the three results as updates, and :8 it into the cell, so they will only make a difference if we've learnt something new.Lholmes;Create a cell with "no information", which we represent as =. When we evaluate propagator computations written with the  abstraction, this function is used to create the result cells at each node of the computation.#It's therefore important that your  value is reasonably efficient to compute, as larger computations may involve producing many of these values as intermediaries. An  of all 2 values, for example, is going to make things run very slowly.MholmesThis function takes two cells, and establishes propagators between them in both directions. These propagators simply copy across any updates that either cell receives, which means that the two cells end up holding exactly the same value at all times.After calling this function, the two cells are entirely indistinguishable, as they will always be equivalent. We can intuit this function as "merging two cells into one".NholmesA standard unary function goes from an input value to an output value. However, in the world of propagators, it is more powerful to rethink this as a  relationship between two values.A good example is the  function. It doesn't matter whether you know the input or the output; it's always possible to figure out the one you're missing. Why, then, should our program only run in one direction? We could rephrase * from 'Int -> Int' to something more like: negateR :: ( Maybe Int, Maybe Int ) -> ( Maybe Int, Maybe Int ) negateR ( x, y ) = ( x  | fmap negate y, y  | fmap negate x ) Now, if we're missing one of the values, we can calculate it using the other! This, and the K function's description above, give us an idea of how functions and relationships differ. The N function simply lifts one of these expressions into a two-way propagator between two cells.The :" constraint means that we can use 1 to represent "knowing nothing" rather than the  in the above example, which makes this function a little more generalised. DHFJGIEKLMN DHFJGIEKLMN.Lift "regular functions" over parameter types.(c) Tom Harding, 2020MITNone -.2OholmesLift a relationship between two values over some type constructor. Typically, this type constructor will be the parameter type.OP-Computing knowledge from multiple parameters.(c) Tom Harding, 2020MITNone-3hQholmes3Lift a relationship between three values over some f (usually a parameter type).QR$Lifting values into parameter types.(c) Tom Harding, 2020MITNone->4Sholmes.Embed a regular value inside a parameter type.STRelationships between values and their (integral) division results.(c) Tom Harding, 2020MITNone96&Uholmes A four-way  relationship between two values, the result of integral division, and the result of the first modulo the second.holmes)Integral multiplication implemented as a V5 relationship in which the remainder is fixed to be 0.holmes/Integal division as a three-value relationship.holmes:Modulo operator implemented as a three-value relationship.UVRelationships between values and their (floating/fractional) product.(c) Tom Harding, 2020MITNone98PWholmesReversible (fractional or floating-point) multiplication as a three-value relationship between two values and their product.holmesA three-way division relationships implemented as a flipped multiplication relationship.holmesA two-way relationship between a value and its reciprocal, implemented with a multiplication relationship in which the third value is fixed to be 1.WX)Refine parameters using their raw values.(c) Tom Harding, 2020MITNone-;NYholmesSome types, such as , contain multiple "candidate values". This function allows us to take each candidate, apply a function, and then union all the results. Perhaps fanOut> would have been a better name for this function, but we use . to lend an intuition when we lift this into Prop via .There's not normally much reverse-flow information here, sadly, as it typically requires us to have a way to generate an "empty candidate" a la . It's quite hard to articulate this in a succinct way, but try implementing the reverse flow for  or , and see what happens.YZ(Relationships between boolean variables.(c) Tom Harding, 2020MITNone+>>[holmesRather than the , , and " functions we know and love, the [ class presents  relationships that are analogous to these. The main difference is that relationships are not one-way. For example, if I tell you that the output of x && y is , you can tell me what the inputs are, even if your computer can't. The implementations of [ should be such that all directions of inference are considered.\holmesAn overloaded  value.]holmesAn overloaded  value.^holmes8A relationship between a boolean value and its opposite._holmesA relationship between two boolean values and their conjunction.`holmesA relationship between two boolean values and their disjunction.[`_^]\Equality relationships.(c) Tom Harding, 2020MITNone>CaholmesEquality between two variables as a relationship between them and their result. The hope here is that, if we learn the output before the inputs, we can often "work backwards" to learn something about them. If we know the result is exactly true(, for example, we can effectively then   the two input cells, as we know that their values will always be the same.The class constraints are a bit ugly here, and it's something I'm hoping I can tidy up down the line. The idea is that, previously, our class was defined as:  class EqR (x :: Type) (b :: Type) | x -> b where eqR :: (x -> x -> b) -> (x -> x -> b) &The problem here was that, if we said  x .== x :: Prop m (Defined Bool)+, we couldn't even infer that the type of x was Defined-wrapped, which made the overloaded literals, for example, largely pointless.To fix it, the class was rewritten to parameterise the wrapper type, which means we can always make this inference. However, the constraints got a bit grizzly when I hacked it together.dholmesA relationship between two variables and the result of a not-equals comparison between them.acbd!:Relationships between values and their comparison results.(c) Tom Harding, 2020MITNone >FaeholmesComparison relationships between two values and their comparison result. See a for more information on the design of this class, and a full apology for the constraints involved.gholmesA relationship between two values and whether the left is less than or equal to the right.hholmes(Comparison between two values and their  result.iholmes(Comparison between two values and their  result.jholmes(Comparison between two values and their  result.egfhij"1Relationships between values and their absolutes.(c) Tom Harding, 2020MITNone9Hkholmes Unlike the  we know, which is a function& from a value to its absolute value, l is a  relationship" between a value and its absolute.1For some types, while we can't truly reverse the * function, we can say that there are two possible( inputs to consider, and so we can push some' information in the reverse direction.lholmesGiven a value and its absolute, try to learn something in either direction.kl&The high-level propagator abstraction.(c) Tom Harding, 2020MITNone '(+-f(mholmesA propagator network with a "focus" on a particular cell. The focus is the cell that typically holds the result we're trying to compute.nholmesLift a cell into a propagator network. Mostly for internal library use.oholmesLower a propagator network's focal point down to a cell. Mostly for internal library use.qholmesLift a regular function into a propagator network. The function is lifted into a relationship with one-way information flow.rholmes values. Sometimes, we might find we get to a first solution faster by randomising the order in which refinements are given. This is similar to the "random restart" strategy in hill-climbing problems.Another nice use for this function is procedural generation: often, your results will look more "natural" if you introduce an element of randomness.holmesGiven an input configuration, and a predicate on those input variables, return all configurations that satisfy the predicate. It should be noted that there's nothing lazy about this; if your problem has a lot of solutions, or your search space is very big, you'll be waiting a long time! D DThe public API for the holmes library.(c) Tom Harding, 2020MITNone +<=r .:;@ABCDOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrsuvwxyz}~Dkl[\]^_`abcdYZWXUVSTOPefgjhi@ACBQR:; .mnopqrsuvwxyz~}&'())*+,#-./0123456789:;<=>?@ABCDEFGHIJK LMNOPQRSTUVWXYZ [  \ ] ^ _ ` a b cdefghijkl mnopqrstuvwxyz{|}~!!!!!!""mkB                            M  !%holmes-0.3.2.0-IZRXzdzxzGIK7susMZefUqData.Input.ConfigData.JoinSemilattice.DefinedData.JoinSemilattice.Intersect Data.HolmesControl.Monad.Cell.ClassData.PropagatorControl.Monad.MoriarTControl.Monad.WatsonControl.Monad.Holmes Data.CDCL singleton Data.JoinSemilattice.Class.MergeData.JoinSemilattice.Class.SumMoriarT Data.STRefSTRef Data.IORefIORefData.JoinSemilattice.Merge<<-Prop Intersect"Data.JoinSemilattice.Class.Mapping"Data.JoinSemilattice.Class.Zipping"Data.JoinSemilattice.Class.Lifting#Data.JoinSemilattice.Class.Integral%Data.JoinSemilattice.Class.Fractional&Data.JoinSemilattice.Class.FlatMapping.>>="Data.JoinSemilattice.Class.BooleanData.JoinSemilattice.Class.EqunifyData.JoinSemilattice.Class.OrdData.JoinSemilattice.Class.AbsDefinedControl.ApplicativeliftA2InputRawfromConfiginitialrefinepermuteUnknownExactlyConflict$fInputDefined$fFractionalDefined$fIntegralDefined $fRealDefined$fMonoidDefined$fSemigroupDefined$fApplicativeDefined $fEnumDefined $fEqDefined $fOrdDefined $fShowDefined$fFunctorDefined$fGenericDefined$fHashableDefined$fBoundedDefined $fNumDefined Intersectable toHashSetlift2fromListtoListdecideddeleteexceptfilterfromSetmappowerSetsizetoSetunionusing$fSemigroupIntersect$fInputIntersect$fFractionalIntersect$fNumIntersect$fMonoidIntersect$fIntersectablecontent $fEqIntersect$fOrdIntersect$fShowIntersect$fFoldableIntersect$fHashableIntersectMergeResult UnchangedChangedFailureSumRaddRsubRnegateR MonadCellCelldiscardfillwatchwithwritebinarymakeunaryMappingmapRZippingzipWithRLiftinglift' IntegralRdivModR FractionalR multiplyR FlatMappingflatMapRBooleanRfalseRtrueRnotRandRorREqREqCeqRneROrdROrdClteRgtRgteRltRAbsRabsRupdownliftover.&&all' allWithIndex'and'any' anyWithIndex'exactlychoosefalsenot'or'true.||.==./=distinct.>.>=.<.<=.+negate'.-.*../..%..*./recip'abs'.$zipWith'$fFractionalProp $fNumProp unMoriarT unsafeReadrunAllrunOnesolve$fMonadCellMoriarT$fPrimMonadMoriarT$fMonadTransMoriarT$fFunctorMoriarT$fApplicativeMoriarT$fAlternativeMoriarT$fMonadMoriarT$fMonadIOMoriarT$fMonadLogicMoriarT$fMonadPlusMoriarT$fMonadReaderRuleMoriarT$fMonadStateGroupMoriarT$fSemigroupMoriarT$fMonoidMoriarTWatsonbackwardforward satisfyingwhenever$fMonadCellWatson$fMonadFailWatson$fFunctorWatson$fApplicativeWatson $fMonadWatsonHolmesshuffle$fMonadCellHolmes$fMonadFailHolmes$fFunctorHolmes$fApplicativeHolmes $fMonadHolmesGroupRuleMinorMajorindex variablesinvertremove refinementsimpliessubsumesresolve toHashMap4unordered-containers-0.2.13.0-E8eURtuGOE2GzyKMKxNkp8Data.HashSet.InternalHashSetbaseGHC.Base<>memptycontainers-0.6.2.1Data.Set.InternalSetGHC.Num+ghc-prim GHC.TypesIntnegate GHC.MaybeMaybeGHC.RealdivModtimesRdivRmodRdivideRrecipR>>= GHC.Classesnot Data.FoldableandorTrueFalseEqC'>>=<OrdIntersectableabsBool&&allany==/=<=-*divmod/recip mtl-2.2.2Control.Monad.Reader.Class MonadReaderControl.Monad.State.Class MonadState%logict-0.7.0.3-FcvfohOp4iB4I8IocnJDkNControl.Monad.Logic.Class MonadLogicControl.Monad.IO.ClassMonadIOGHC.STSTIO