úΚš’ĀC      !"#$%&'()*+,-./0123456789:;<=>?@AB non-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/C' isFunction f' returns D iff the top level " constructor"  of f is a function arrow. EF>This function is rather fragile, but should be OK. It is only  used by Test.ChasingBottoms.ApproxShow, which should only be used C for debugging purposes anyway. The unit type is not considered to  be a tuple. GHCFGHCFGHnon-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/ Natural numbers. No I9 instance is provided, because the implementation should  be abstract. JK 0 == L(, for other total natural numbers it is D.  0 == M,  (n+1) == N n for a  total natural number n. 2 performs primitive recursion on natural numbers.  is a fold on natural numbers:    g h =  g (O P h . Q) RS$non-portable (preemptive scheduling) experimentalhttp://www.cs.nott.ac.uk/~nad/ TU   n c runs c for at most n seconds (modulo  scheduling issues). 1 If the computation terminates before that, then   v is  returned, where v( is the resulting value. Note that this + value may be equal to bottom, e.g. if c = V  . - If the computation does not terminate, then  is  returned. . If the computation raises an exception, then  e is  returned, where e is the exception. <Note that a user-defined exception is used to terminate the  computation, so if c# catches all exceptions, or blocks  asynchronous exceptions, then   may fail to function  properly.  . takes a delay in microseconds. Note that the E resolution is not necessarily very high (the last time I checked it B was 0.02 seconds when using the standard runtime system settings  for GHC).  ) is a variant which can be used for pure  computations. The definition,      n =   n . W  ensures that   1  usually returns   < something>. (  1 (V ) usually  returns   "; in other words, the computation ? reaches whnf almost immediately, defeating the purpose of the  time-out.)   is the equivalent variant of  :     n =   n . W      non-portable (exceptions) experimentalhttp://www.cs.nott.ac.uk/~nad/7 generates a bottom that is suitable for testing using  .  a returns L if a is distinct from bottom. If  a= equals bottom and results in an exception of a certain kind  (see below), then  a = D. If a never reaches a A weak head normal form and never throws one of these exceptions,  then  a never terminates. The exceptions that yield D correspond to " pure bottoms", / i.e. bottoms that can originate in pure code:  X  YZ  [\  ]^  _`  ab  cd  ef <Assertions 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  g4, but the value infinity makes that case unclear as  well).  s raises an exception (hi)  that is not caught by . Use s to describe the  exception.  timeOutLimit works like  , but if   timeOutLimit is N lim%, then computations taking more than  lim> seconds are also considered to be equal to bottom. Note that C 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   . non-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/The I instance of  makes sure that   n) behaves (more or less) like the derived  version of j", with the following differences:  After n- levels of descent into a term the output is  replaced by "_". 6 All detectable occurences of bottoms are replaced by "_|_". ' Non-bottom functions are displayed as "< function /= _|_>". Precedence level. knon-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/5 is a class for approximation functions as described =in The generic approximation lemma, Graham Hutton and Jeremy AGibbons, 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 I type class. Due to the limitations of the  Data.Generics approach to generic Dprogramming, which is not really aimed at this kind of application, Athe implementation is only guaranteed to perform correctly, with Frespect 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 Epaper. The specification below is correct, though (if we assume that the I instances are well-behaved). In practice the + function can probably be more useful than . It traverses down all% subterms, and it should be possible 4to prove a variant of the approximation lemma which   satisfies.  n x traverses n levels down in x and replaces all $ values at that level with bottoms.  works like , but the traversal and C 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. lmnnon-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/op4 contains methods for testing whether two terms are 4 related according to the semantic domain ordering.  tweak x y returns M if x and y are  incomparable, and N o otherwise, where o :: q ! represents the relation between x and y.  !"x  y and x   y& compute the least upper and greatest  lower bounds, respectively, of x and y in the semantical A domain ordering. Note that the least upper bound may not always  exist. 8 This functionality was implemented just because it was ' possible (and to provide analogues of r and s in the t = class). If anyone finds any use for it, please let me know. ##4 contains methods for testing whether two terms are  semantically equal. $%&'=The behaviour of some of the functions below can be tweaked. () If equal to N n, an  n is performed on A all arguments before doing whatever the function is supposed to  be doing. * If equal to N n', then all computations that take more  than n3 seconds to complete are considered to be equal to  *. This functionality is implemented using  . +No tweak (both fields are M). uvwxyz{| !"#$%&'()*+'()*+#$%& !"  !" !"#$%&$%&'()*()*+non-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/)},@Monad for generating results given previously generated pattern  matches. A , a6 should be implemented almost as other generators for  the type a, with the difference that 7 should be C used wherever the resulting function should be allowed to pattern D match (typically for each constructor emitted). See example above. ~€‚-The type of a 0/ generator. ƒ8This newtype is (currently) necessary if we want to use  .' as an argument to a type constructor. „.%The type of a generator transformer. /0/0 packages up the possible outcomes of a pattern E match in a style suitable for generating functions. A pattern match  is a generator (…%) transformer based on the top-level " constructor, and a sequence (see   @http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html) of  0/.es based on the children of that constructor. 01)A generator transformer, in the style of †. 2.Further pattern matches made possible by this  match. 3<Generator for continuous, not necessarily strict functions. B Functions are generated by first generating pattern matches, and  then generating a result. 44 specialises 3:   4 = 3 5 ‡ˆ5Generic implementation of 0/ construction. ‰Lowering of a ,. 6 Lifting of a …. Š Returns the } in scope. ‹776 makes sure that the pattern matches get to influence  the generated value. See ,. Œ;Extracts some pattern matches to trigger right away. These C triggered pattern matches may result in new pattern matches which + may in turn also be triggered, and so on. Concatenates arguments. ŽComposes arguments.  Partitions a -. The first argument (a positive integer) is C the relative probability with which elements end up in the second ! part compared to the first one. 8 Lifting of ‘. 9 Lifting of ’. : Lifting of “. ; Lifting of ”. < Lifting of •. = Lifting of –. > Lifting of —. ?An implementation of , a which is suitable when a  is flat and has an ˜% instance. Yields bottoms around 10%  of the time. @This , yields finite partial lists. AThis , yields infinite partial lists. BThis ,* yields finite or infinite partial lists. ™,-./0123456789:;<=>?@AB34/012.-,7689:;<=>5?@AB,-./0120123456789:;<=>?@AB non-portable (GHC-specific) experimentalhttp://www.cs.nott.ac.uk/~nad/C  !"#$%&'()*+,-./0123456789:;<=>?@ABš     !"#$%&'()*+,-./011234567889:;<=>?@ABCDEFGHIJKLMNOPQRSTU VLMWSXYSXZS[\S]^S[_`abbS]cSdeSfgShiShiSjkSjkSjSjSjlSjlSjmSjmSjnSjnSjoSjoShpSfqSfqSrstuvwxyLz{S|}S|~S|€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ “Ą‘Ē‘Ģ‘Ī‘Ĩ‘Ķ‘§“ĻĐŠChasingBottoms-1.3.0Test.ChasingBottoms.NatTest.ChasingBottoms.IsBottomTest.ChasingBottoms.TimeOutTest.ChasingBottoms.ApproxShowTest.ChasingBottoms.ApproxTest.ChasingBottoms.SemanticOrd'Test.ChasingBottoms.ContinuousFunctionsTest.ChasingBottoms.IsTypeTest.ChasingBottomsNatisSuccfromSuccnatrecfoldNbottomResult ExceptionNonTerminationValuetimeOut timeOutMicrotimeOut' timeOutMicro'isBottomnonBottomErrorisBottomTimeOut ApproxShowapproxShowsPrec approxShows approxShowPrecApprox approxAllapprox SemanticOrd!>=!<=!semanticCompare\/!/\! semanticJoin semanticMeet SemanticEq==!/=! semanticEqTweak approxDepth timeOutLimitnoTweak MakeResultMakePMGenTransformer PatternMatchapplymorefunction functionTomatchlift' transform arbitrary'choose' elements'oneof' frequency'sized'resize'flat finiteListOfinfiniteListOflistOf isFunctionghc-primGHC.BoolTrueconisTupleisStringisListbase Data.DataDatanat2intFalse Data.MaybeNothingJust Data.TuplecurryGHC.Base$sndstealsteal2DiereturnGHC.IOevaluateGHC.IO.ExceptionArrayException GHC.Exception ErrorCallControl.Exception.Base NoMethodErrorPatternMatchFail RecConError RecSelError RecUpdError DivideByZeroAssertionFailedGHC.Show showsPrec gShowsPrec approxGen approxAllGen approxGen'RelRel' GHC.OrderingOrdering GHC.ClassesmaxminOrdliftAppr semanticEq' semanticLE'allOK=^= childrenOK semanticMeet' semanticJoin'PatternMatchesMRunMRTreeLeafBranchGenTransformer'GenTQuickCheck-2.1.2Test.QuickCheck.GenGenTest.QuickCheck.Arbitrary coarbitrary matchFlat matchTreerungetPMswithPMs getMatchesconcatcompose partition'containers-0.3.0.0 Data.SequenceSeq arbitrarychooseelementsoneof frequencysizedresize Arbitrary makeResult