!]      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\ $(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)Safe )]ChasingBottoms' isFunction f' returns ^% iff the top level "constructor" of f is a function arrow._ChasingBottomsGThis function is rather fragile, but should be OK. It is only used by Test.ChasingBottoms.ApproxShowk, which should only be used for debugging purposes anyway. The unit type is not considered to be a tuple.]_`a$(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)None2ChasingBottomsNatural numbers.No bF instance is provided, because the implementation should be abstract.ChasingBottoms 0 == c(, for other total natural numbers it is ^.ChasingBottoms 0 == d,  (n+1) == e n for a total natural number n.ChasingBottoms1 performs primitive recursion on natural numbers.ChasingBottoms is a fold on natural numbers:   g h =  g (f g h . h) $(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)None=?X,ChasingBottoms is a class for approximation functions as described in The generic approximation lemma, Graham Hutton and Jeremy Gibbons, Information Processing Letters, 79(4):197-201, Elsevier Science, August 2001,  &http://www.cs.nott.ac.uk/~gmh/bib.html..Instances are provided for all members of the b+ type class. Due to the limitations of the  Data.Generics approach to generic programming, which is not really aimed at this kind of application, the implementation is only guaranteed to perform correctly, with respect to the paper (and modulo any bugs), on non-mutually-recursive sum-of-products datatypes. In particular, nested and mutually recursive types are not handled correctly with respect to the paper. The specification below is correct, though (if we assume that the b instances are well-behaved).In practice the + function can probably be more useful than . It traverses down allY subterms, and it should be possible to prove a variant of the approximation lemma which  satisfies.ChasingBottoms n x traverses n levels down in x5 and replaces all values at that level with bottoms.ChasingBottoms works like , but the traversal and replacement is only performed at subterms of the same monomorphic type as the original term. For polynomial datatypes this is exactly what the version of approx$ described in the paper above does.$(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimental$non-portable (preemptive scheduling)Safe2XBBChasingBottoms n c runs c for at most n% seconds (modulo scheduling issues).0If the computation terminates before that, then  v is returned, where vS is the resulting value. Note that this value may be equal to bottom, e.g. if c = i .,If the computation does not terminate, then  is returned.-If the computation raises an exception, then  e is returned, where e is the exception.PNote that a user-defined exception is used to terminate the computation, so if cB catches all exceptions, or blocks asynchronous exceptions, then  may fail to function properly.ChasingBottoms takes a delay in microseconds. Note that the resolution is not necessarily very high (the last time I checked it was 0.02 seconds when using the standard runtime system settings for GHC).ChasingBottomsG is a variant which can be used for pure computations. The definition,   n =  n . j  ensures that  1  usually returns  <something>. ( 1 (i ) usually returns  l; in other words, the computation reaches whnf almost immediately, defeating the purpose of the time-out.)ChasingBottoms is the equivalent variant of :   n =  n . j $(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (exceptions)NoneX[ChasingBottoms8 generates a bottom that is suitable for testing using .ChasingBottoms a returns c if a is distinct from bottom. If aP equals bottom and results in an exception of a certain kind (see below), then  a = ^. If aX never reaches a weak head normal form and never throws one of these exceptions, then  a never terminates.The exceptions that yield ^M correspond to "pure bottoms", i.e. bottoms that can originate in pure code:klmnopqrAssertions are excluded, because their behaviour depends on compiler flags (not pure, and a failed assertion should really yield an exception and nothing else). The same applies to arithmetic exceptions (machine dependent, except possibly for s;, but the value infinity makes that case unclear as well).ChasingBottoms s raises an exception (t) that is not caught by . Use s to describe the exception. ChasingBottoms  timeOutLimit works like  , but if  timeOutLimit is e lim&, then computations taking more than lim seconds are also considered to be equal to bottom. Note that this is a very crude approximation of what a bottom is. Also note that this "function" may return different answers upon different invocations. Take it for what it is worth. ) is subject to all the same vagaries as .!ChasingBottoms A variant of  that lives in the u monad."ChasingBottoms A variant of   that lives in the u monad. !"! "$(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)None=?SXpL#ChasingBottoms#g contains methods for testing whether two terms are related according to the semantic domain ordering.(ChasingBottoms( tweak x y returns d if x and y are incomparable, and e o otherwise, where o :: v" represents the relation between x and y.,ChasingBottomsx ) y and x * yF compute the least upper and greatest lower bounds, respectively, of x and y in the semantical domain ordering. Note that the least upper bound may not always exist. This functionality was implemented just because it was possible (and to provide analogues of w and x in the y= class). If anyone finds any use for it, please let me know.-ChasingBottoms-H contains methods for testing whether two terms are semantically equal.1ChasingBottoms<The behaviour of some of the functions below can be tweaked.3ChasingBottoms If equal to e n, an  n\ is performed on all arguments before doing whatever the function is supposed to be doing.4ChasingBottoms If equal to e n-, then all computations that take more than n4 seconds to complete are considered to be equal to +. This functionality is implemented using  .5ChasingBottomsNo tweak (both fields are d).#$%&')*(+,-./01243512435-./0#$%&')*(+,$4%4&4'4)5*5.4/4$(c) Nils Anders Danielsson 2005-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)None2MSXf;ChasingBottomsIMonad for generating results given previously generated pattern matches.A ; a@ should be implemented almost as other generators for the type a, with the difference that F should be used wherever the resulting function should be allowed to pattern match (typically for each constructor emitted). See example above.<ChasingBottomsThe type of a > generator.zChasingBottoms9This newtype is (currently) necessary if we want to use =& as an argument to a type constructor.=ChasingBottoms$The type of a generator transformer.>ChasingBottoms> packages up the possible outcomes of a pattern match in a style suitable for generating functions. A pattern match is a generator ({E) transformer based on the top-level constructor, and a sequence of >.es based on the children of that constructor.@ChasingBottoms)A generator transformer, in the style of |.AChasingBottoms5Further pattern matches made possible by this match.BChasingBottomsGenerator for continuous, not necessarily strict functions. Functions are generated by first generating pattern matches, and then generating a result.CChasingBottomsC specialises B:  C = B D DChasingBottomsGeneric implementation of > construction.}ChasingBottomsLowering of a ;.EChasingBottoms Lifting of a {.~ChasingBottoms Returns the  in scope.FChasingBottomsFP makes sure that the pattern matches get to influence the generated value. See ;.ChasingBottomsExtracts some pattern matches to trigger right away. These triggered pattern matches may result in new pattern matches which may in turn also be triggered, and so on.ChasingBottomsConcatenates arguments.ChasingBottomsComposes arguments.ChasingBottoms Partitions a . The first argument (a positive integer) is the relative probability with which elements end up in the second part compared to the first one.GChasingBottoms Lifting of .HChasingBottoms Lifting of .IChasingBottoms Lifting of .JChasingBottoms Lifting of .KChasingBottoms Lifting of .LChasingBottoms Lifting of .MChasingBottoms Lifting of .NChasingBottomsAn implementation of ; a which is suitable when a is flat and has an 2 instance. Yields bottoms around 10% of the time.OChasingBottomsThis ; yields finite partial lists.PChasingBottomsThis ; yields infinite partial lists.QChasingBottomsThis ;) yields finite or infinite partial lists.;<=>?@ABCDEFGHIJKLMNOPQBC>?@A=<;FEGHIJKLMDNOPQ$(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)None=?X}XChasingBottomsThe b instance of W makes sure that X n5 behaves (more or less) like the derived version of !, with the following differences:After n> levels of descent into a term the output is replaced by "_".5All detectable occurences of bottoms are replaced by "_|_".&Non-bottom functions are displayed as "<function /= _|_>".[ChasingBottomsPrecedence level.WXYZ[[WXYZ $(c) Nils Anders Danielsson 2004-2020See the file LICENCE. http://www.cse.chalmers.se/~nad/ experimentalnon-portable (GHC-specific)NoneE !"#$%&')*(+,-./012435;<=>?@ABCDEFGHIJKLMNOPQWXYZ[     !"#$%&'()*+,-./0123456789:;;<=>?@ABCDEFGGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnfgolpqlprlstluvlswluxlyzl{|l}~llllllll{fgfgfffl-ChasingBottoms-1.3.1.9-42wXkZSoQZuJo75scFomovTest.ChasingBottoms.IsBottomTest.ChasingBottoms.NatTest.ChasingBottoms.ApproxTest.ChasingBottoms.TimeOutTest.ChasingBottoms.SemanticOrd'Test.ChasingBottoms.ContinuousFunctionsTest.ChasingBottoms.ApproxShowTest.ChasingBottoms.IsTypeTest.ChasingBottomsbottomNatisSuccfromSuccnatrecfoldN$fCoArbitraryNat$fArbitraryNat $fShowNat $fEnumNat $fIntegralNat $fRealNat$fNumNat$fEqNat$fOrdNatApprox approxAllapprox $fApproxaResultValueNonTermination ExceptiontimeOut timeOutMicrotimeOut' timeOutMicro'$fExceptionDie $fShowResult $fShowDieisBottomnonBottomErrorisBottomTimeOut isBottomIOisBottomTimeOutIO SemanticOrd=!>!semanticCompare\/!/\! semanticJoin semanticMeet SemanticEq==!/=! semanticEqTweak approxDepth timeOutLimitnoTweak $fSemanticEqa$fSemanticOrda $fEqTweak $fOrdTweak $fShowTweak MakeResultMakePMGenTransformer PatternMatchapplymorefunction functionTomatchlift' transform arbitrary'choose' elements'oneof' frequency'sized'resize'flat finiteListOfinfiniteListOflistOf $fShowTree $fDataTree$fFunctorMakeResult$fApplicativeMakeResult$fMonadMakeResult ApproxShowapproxShowsPrec approxShows approxShowPrec $fApproxShowa isFunctionghc-prim GHC.TypesTrueisTupleisStringisListbase Data.DataDataFalse GHC.MaybeNothingJust Data.TuplecurryGHC.Base$sndreturnGHC.IOevaluateGHC.IO.ExceptionArrayException GHC.Exception ErrorCallControl.Exception.Base NoMethodErrorPatternMatchFail RecConError RecSelError RecUpdErrorGHC.Exception.Type DivideByZeroAssertionFailedIOOrdering GHC.ClassesmaxminOrdGenTransformer'%QuickCheck-2.14-C4cnfP1Eum44Xog1qbaOxTest.QuickCheck.GenGenTest.QuickCheck.Arbitrary coarbitraryrungetPMsPatternMatches getMatchesconcatcompose partition'containers-0.6.0.1Data.Sequence.InternalSeq arbitrarychooseelementsoneof frequencysizedresize ArbitraryGHC.Show showsPrec