code-conjure 0.3.0 → 0.3.2

raw patch · 42 files changed

+913/−243 lines, 42 filesdep ~expressPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: express

API changes (from Hackage documentation)

Files

• .gitignore +2/−0
• Makefile +5/−1
• bench/longshot.hs +69/−0
• bench/runtime/zero/bench/ill-hit.runtime +1/−1
• bench/runtime/zero/bench/longshot.runtime +1/−0
• bench/runtime/zero/bench/self.runtime +1/−1
• bench/runtime/zero/bench/take-drop.runtime +1/−1
• bench/runtime/zero/eg/arith.runtime +1/−1
• bench/runtime/zero/eg/bools.runtime +1/−1
• bench/runtime/zero/eg/factorial.runtime +1/−1
• bench/runtime/zero/eg/fibonacci.runtime +1/−0
• bench/runtime/zero/eg/ints.runtime +1/−1
• bench/runtime/zero/eg/list.runtime +1/−1
• bench/runtime/zero/eg/spec.runtime +1/−1
• bench/runtime/zero/eg/tapps.runtime +1/−1
• bench/runtime/zero/proto/u-conjure.runtime +1/−1
• bench/runtime/zero/versions +1/−1
• bench/take-drop.hs +1/−1
• changelog.md +19/−0
• code-conjure.cabal +4/−3
• eg/fibonacci.hs +27/−0
• eg/list.hs +15/−0
• mk/depend.mk +47/−0
• src/Conjure/Conjurable.hs +6/−0
• src/Conjure/Constructors.hs +165/−0
• src/Conjure/Engine.hs +111/−9
• src/Conjure/Expr.hs +53/−12
• src/Conjure/Utils.hs +52/−0
• stack.yaml +1/−1
• test/model/bench/ill-hit.out +27/−27
• test/model/bench/longshot.out +37/−0
• test/model/bench/self.out +4/−4
• test/model/bench/take-drop.out +27/−23
• test/model/eg/arith.out +6/−6
• test/model/eg/bools.out +26/−26
• test/model/eg/factorial.out +10/−10
• test/model/eg/fibonacci.out +17/−0
• test/model/eg/ints.out +29/−29
• test/model/eg/list.out +61/−46
• test/model/eg/spec.out +18/−18
• test/model/eg/tapps.out +15/−15
• test/utils.hs +45/−0

@@ -30,11 +30,13 @@ eg/arith eg/bools eg/factorial+eg/fibonacci eg/ints eg/list eg/tapps eg/spec bench/self+bench/longshot bench/ill-hit bench/take-drop proto/u-conjure

@@ -8,12 +8,14 @@ EG = \   eg/arith \   eg/factorial \+  eg/fibonacci \   eg/ints \   eg/bools \   eg/list \   eg/spec \   eg/tapps \   bench/ill-hit \+  bench/longshot \   bench/self \   bench/take-drop \   proto/u-conjure@@ -39,7 +41,9 @@ %.bench: % 	@mkdir -p bench/runtime/$$HOSTNAME/`dirname $<` 	@printf "%-18s " $<-	@/usr/bin/time -f%e ./$< 2>&1 >/dev/null | tee bench/runtime/$$HOSTNAME/$<.runtime+	@/usr/bin/time -f%e ./$< 2>&1 >/dev/null | \+	python3 -c 'print("%.1f" % float(input()))' | \+	tee bench/runtime/$$HOSTNAME/$<.runtime  diff-test: $(patsubst %,%.diff-test,$(EG)) 

@@ -0,0 +1,69 @@+-- longshot.hs: miscellaneous longshots+--+-- Copyright (C) 2021 Rudy Matela+-- Distributed under the 3-Clause BSD licence (see the file LICENSE).+import Conjure++sort' :: [Int] -> [Int]+sort' []       =  []+sort' [x]      =  [x]+sort' [x,y]+  | x <= y     =  [x,y]+  | otherwise  =  [y,x]+sort' [x,y,z]+  | x <= y && y <= z  =  [x,y,z]+  | z <= y && y <= x  =  [z,y,x]++pow :: Int -> Int -> Int+pow 2 0  =  1+pow 2 1  =  2+pow 2 2  =  4+pow 2 3  =  8+pow 3 2  =  9++main :: IO ()+main = do+  -- qsort+  -- qsort xs  =  if null xs                                 -- 3+  --              then []                                    -- 4+  --              else qsort (filter (< head xs) (tail xs))  -- 11+  --                ++ (head xs:[])                          -- 16+  --                ++ qsort (filter (>= head xs) (tail xs)) -- 24+  -- not only this is out of reach performance wise,+  -- but the needed recursive calls will not be enumerated+  conjure "qsort" sort'+    [ val ([] :: [Int])+    , value ":" ((:) :: Int -> [Int] -> [Int])+    , value "head" (head :: [Int] -> Int)+    , value "tail" (tail :: [Int] -> [Int])+    , value "null" (null :: [Int] -> Bool)+    , value "++" ((++) :: [Int] -> [Int] -> [Int])+    , value "<" ((<) :: Int -> Int -> Bool)+    , value ">=" ((>=) :: Int -> Int -> Bool)+    , value "filter" (filter :: (Int -> Bool) -> [Int] -> [Int])+    ]++  -- pow b e  =  if e == 0 then 1 else b * pow b (dec e)+  --             1  2  3 4      5      6 7 8   9  10 11+  -- somehow this takes 30s to run, the two arguments+  -- of the same type introduce the difficulty here.+  conjureWithMaxSize 8 "pow" pow+    [ val (0::Int)+    , val (1::Int)+    , value "+" ((+) :: Int -> Int -> Int)+    , value "*" ((*) :: Int -> Int -> Int)+    , value "dec" (subtract 1 :: Int -> Int)+    , value "==" ((==) :: Int -> Int -> Bool)+    ]++  -- pow b e  =  if e == 0 then 1 else pow b (halve e) * pow b (halve e) * if odd e then b else 1+  --             1  2  3 4      5      6   7  8     9 10 11 12  13   14 15 16 17  18    19     20+  -- out of reach performance wise+  conjureWithMaxSize 8 "pow" pow+    [ val (0::Int)+    , val (1::Int)+    , value "+" ((+) :: Int -> Int -> Int)+    , value "*" ((*) :: Int -> Int -> Int)+    , value "halve" ((`div` 2) :: Int -> Int)+    , value "==" ((==) :: Int -> Int -> Bool)+    ]

@@ -1,1 +1,1 @@-1.64+1.2

@@ -0,0 +1,1 @@+2.7

@@ -1,1 +1,1 @@-0.01+0.0

@@ -1,1 +1,1 @@-6.42+5.7

@@ -1,1 +1,1 @@-0.94+0.9

@@ -1,1 +1,1 @@-6.83+3.1

@@ -1,1 +1,1 @@-5.26+1.4

@@ -0,0 +1,1 @@+2.7

@@ -1,1 +1,1 @@-1.44+1.0

@@ -1,1 +1,1 @@-3.20+0.6

@@ -1,1 +1,1 @@-0.68+0.5

@@ -1,1 +1,1 @@-0.73+0.5

@@ -1,1 +1,1 @@-0.33+0.4

@@ -1,4 +1,4 @@ GHC 8.10.4 leancheck-0.9.6-express-0.1.10+express-0.1.12 speculate-0.4.6

@@ -32,7 +32,7 @@    -- take n xs = if n==0 || null xs then [] else head xs : take (dec n) (tail xs)   -- needs size 16-  conjureWithMaxSize 13 "take" (take' :: Int -> [A] -> [A])+  conjureWithMaxSize 16 "take" (take' :: Int -> [A] -> [A])     [ val (0 :: Int)     , val ([] :: [A])     , value "null" (null :: [A] -> Bool)

@@ -2,6 +2,25 @@ ============================  +v0.3.2+------++* significant runtime reduction in several benchmarks, e.g.:+	- take is now reachable in about 5 seconds+* improved candidate generation:+	- faster runtime+	- fewer redundant/invalid candidates+* limit recursive calls to use deconstructors+	- test to find deconstructors automatically+* improve recursion evaluation method (`revaluate` replaces `recursexpr`)+* add fibonacci benchmark+* minor:+	- record runtimes with one decimal place instead of two+	- add longshot benchmark+	- add intercalate to the list benchmark+	- add stub `Conjure.Constructors` module++ v0.3.0 ------ 

@@ -3,7 +3,7 @@ -- Copyright (C) 2021 Rudy Matela -- Distributed under the 3-Clause BSD licence (see the file LICENSE). name:                code-conjure-version:             0.3.0+version:             0.3.2 synopsis:            conjure Haskell functions out of partial definitions description:   Conjure is a tool that produces Haskell functions out of partial definitions.@@ -65,7 +65,7 @@ source-repository this   type:            git   location:        https://github.com/rudymatela/conjure-  tag:             v0.3.0+  tag:             v0.3.2  library   exposed-modules: Conjure@@ -74,12 +74,13 @@                  , Conjure.Expr                  , Conjure.Spec                  , Conjure.Utils+                 , Conjure.Constructors   other-extensions: TemplateHaskell, CPP   build-depends: base >= 4 && < 5                , leancheck >= 0.9.6                , template-haskell                , speculate >= 0.4.6-               , express >= 0.1.10+               , express >= 0.1.12   hs-source-dirs:      src   default-language:    Haskell2010 

@@ -0,0 +1,27 @@+-- fibonacci.hs: conjuring a fibonacci function+import Conjure++fibonacci :: Int -> Int+fibonacci 0  =  1+fibonacci 1  =  1+fibonacci 2  =  2+fibonacci 3  =  3+fibonacci 4  =  5+fibonacci 5  =  8+fibonacci 6  =  13+fibonacci 7  =  21++as :: Args+as  =  args{maxSize=13,maxRecursiveCalls=2}++main :: IO ()+main  =  do+  conjureWith as "fibonacci n" fibonacci+    [ val (1::Int)+    , value "+" ((+) :: Int -> Int -> Int)+    , value "dec" (subtract 1 :: Int -> Int)+    , value "<=" ((<=) :: Int -> Int -> Bool)+    ]+-- expected function:+-- fibonacci n  =  if n <= 1 then 1 else fibonacci (dec n) + fibonacci (dec (dec n))+--                 1  2 3  4      5      6          7   8  9        10  11   12  13

@@ -32,6 +32,11 @@ [x,y]   +++ [z,w]    =  [x,y,z,w] [x,y,z] +++ [w,v,u]  =  [x,y,z,w,v,u] +(\/) :: [Int] -> [Int] -> [Int]+[x] \/ [y]  =  [x,y]+[x,y] \/ [z,w]  =  [x,z,y,w]+[x,y,z] \/ [w,v,u]  =  [x,w,y,v,z,u]+ main :: IO () main = do   -- length xs  =  if null xs then 0 else 1 + length (tail xs)@@ -113,4 +118,14 @@     [ val ([] :: [Int])     , value ":" ((:) :: Int -> [Int] -> [Int])     , value "foldr" (foldr :: (Int -> [Int] -> [Int]) -> [Int] -> [Int] -> [Int])+    ]++  -- intercalate+  -- xs \/ ys  =  if null xs then ys else head xs : (ys \/ tail xs)+  conjure "\\/" (\/)+    [ val ([] :: [Int])+    , value ":" ((:) :: Int -> [Int] -> [Int])+    , value "head" (head :: [Int] -> Int)+    , value "tail" (tail :: [Int] -> [Int])+    , value "null" (null :: [Int] -> Bool)     ]

@@ -7,8 +7,21 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   bench/ill-hit.hs+bench/longshot: \+  bench/longshot.hs \+  mk/toplibs+bench/longshot.o: \+  src/Conjure/Utils.hs \+  src/Conjure/Spec.hs \+  src/Conjure.hs \+  src/Conjure/Expr.hs \+  src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \+  src/Conjure/Conjurable.hs \+  bench/longshot.hs bench/self: \   bench/self.hs \   mk/toplibs@@ -18,6 +31,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   bench/self.hs bench/take-drop: \@@ -29,6 +43,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   bench/take-drop.hs eg/arith: \@@ -40,6 +55,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/arith.hs eg/bools: \@@ -51,6 +67,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/bools.hs eg/factorial: \@@ -62,8 +79,21 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/factorial.hs+eg/fibonacci: \+  eg/fibonacci.hs \+  mk/toplibs+eg/fibonacci.o: \+  src/Conjure/Utils.hs \+  src/Conjure/Spec.hs \+  src/Conjure.hs \+  src/Conjure/Expr.hs \+  src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \+  src/Conjure/Conjurable.hs \+  eg/fibonacci.hs eg/ints: \   eg/ints.hs \   mk/toplibs@@ -73,6 +103,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/ints.hs eg/list: \@@ -84,6 +115,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/list.hs eg/spec: \@@ -95,6 +127,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/spec.hs eg/tapps: \@@ -106,6 +139,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   eg/tapps.hs mk/All.o: \@@ -114,6 +148,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   mk/All.hs mk/Toplibs.o: \@@ -122,6 +157,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs \   mk/Toplibs.hs proto/u-conjure.o: \@@ -132,11 +168,16 @@ src/Conjure/Conjurable.o: \   src/Conjure/Utils.hs \   src/Conjure/Expr.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs+src/Conjure/Constructors.o: \+  src/Conjure/Utils.hs \+  src/Conjure/Constructors.hs src/Conjure/Engine.o: \   src/Conjure/Utils.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs src/Conjure/Expr.o: \   src/Conjure/Utils.hs \@@ -147,12 +188,14 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs src/Conjure/Spec.o: \   src/Conjure/Utils.hs \   src/Conjure/Spec.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs src/Conjure/Utils.o: \   src/Conjure/Utils.hs@@ -166,6 +209,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs test/conjurable: \   test/Test.hs \@@ -183,6 +227,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs test/expr: \   test/Test.hs \@@ -205,6 +250,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs test/Test: \   test/Test.hs \@@ -221,6 +267,7 @@   src/Conjure.hs \   src/Conjure/Expr.hs \   src/Conjure/Engine.hs \+  src/Conjure/Constructors.hs \   src/Conjure/Conjurable.hs test/utils: \   test/utils.hs \

@@ -26,6 +26,7 @@   , conjureAreEqual   , conjureMkEquation   , A, B, C, D, E, F+  , conjureIsDeconstructor   ) where @@ -33,6 +34,7 @@ import Test.LeanCheck.Utils import Test.LeanCheck.Error (errorToFalse) import Conjure.Expr hiding (application)+import Conjure.Constructors import Test.Speculate.Expr import Data.Functor ((<$>)) import Control.Applicative ((<*>))@@ -189,6 +191,10 @@                       ((e':_):_) | typ e' == typ e -> etiers                       _                            -> tf etc +conjureIsDeconstructor :: Conjurable f => f -> Int -> Expr -> Expr -> Expr -> Bool+conjureIsDeconstructor f maxTests  =  isDeconstructionE+                                   .  take maxTests+                                   .  grounds (conjureTiersFor f)  instance Conjurable () where   conjureEquality  =  reifyEquality

@@ -0,0 +1,165 @@+-- |+-- Module      : Conjure.Constructors+-- Copyright   : (c) 2021 Rudy Matela+-- License     : 3-Clause BSD  (see the file LICENSE)+-- Maintainer  : Rudy Matela <rudy@matela.com.br>+--+-- This module is part of 'Conjure'.+--+-- This module defines the 'Constructors' typeclass+-- that allows listing constructors of a type+-- encoded as 'Expr's+--+-- You are probably better off importing "Conjure".+{-# Language DeriveDataTypeable, StandaloneDeriving #-} -- for GHC < 7.10+module Conjure.Constructors+  ( Constructors (..)+  , Fxpr+  , Fxpress (..)+  , sumFxpr+  , factFxpr+  , nullFxpr+  , isZeroFxpr+  )+where++import Conjure.Utils+import Data.Express+import Data.Express.Express+import Data.Express.Fixtures+import Data.Typeable (Typeable)++type Fxpr  =  [([Expr],Expr)]++sumFxpr :: Fxpr+sumFxpr  =+  [ [nil]           =-  zero+  , [(xx -:- xxs)]  =-  xx -+- (var "recurse" (undefined :: [Int] -> Int) :$ xxs)+  ]+  where+  (=-) = (,)+  infixr 0 =-++factFxpr :: Fxpr+factFxpr  =  undefined++nullFxpr :: Fxpr+nullFxpr  =+  [ [nil]          =- false+  , [(xx -:- xxs)] =- false+  ]+  where+  (=-) = (,)+  infixr 0 =-++isZeroFxpr :: Fxpr+isZeroFxpr  =+  [ [zero]  =- true+  , [inc xx] =- false+  ]+  where+  inc = undefined -- TODO: define me+  (=-) = (,)+  infixr 0 =-+++class Typeable a => Fxpress a where+  fvl :: Fxpr -> a+  fvl (([],e):_)  =  evl e+  fvl _           =  error "fvl: incomplete pattern match"++instance Fxpress ()+instance Fxpress Int+instance Fxpress Bool+instance Fxpress Char+instance Fxpress a => Fxpress [a]+instance Fxpress a => Fxpress (Maybe a)+instance (Fxpress a, Fxpress b) => Fxpress (Either a b)++instance (Constructors a, Fxpress b) => Fxpress (a -> b) where+  fvl cs x  =  fvl [ (ps,exp //- bs)+                   | (p:ps,exp) <- cs+                   , bs <- maybeToList (match (expr1 x) p)+                   ]+-- TODO: add support for recursion+++class Express a => Constructors a where+  expr1 :: a -> Expr+  constructors :: a -> [Expr]++instance Constructors () where+  expr1  =  val+  constructors _  =  [val ()]++instance Constructors Bool where+  expr1  =  val+  constructors _  =  [val False, val True]++constructorsNum :: (Num a, Express a) => a -> [Expr]+constructorsNum x  =  [ hole x -- <= 0 -- val (0 -: x)+                      , value "inc" ((+1) ->: x) :$ hole x+                      ]++expr1Num :: (Ord a, Num a, Express a) => a -> Expr+expr1Num x+  | x <= 0     =  val x+  | otherwise  =  value "inc" ((+1) ->: x) :$ val (x-1)++instance Constructors Int where+  expr1  =  expr1Num+  constructors  =  constructorsNum++instance Constructors Integer where+  expr1  =  expr1Num+  constructors  =  constructorsNum++instance Constructors Char where+  expr1  =  val+  constructors _  =  []++instance Express a => Constructors [a] where+  expr1 xs  =  case xs of+               [] -> val xs+               (y:ys) -> value ":" ((:) ->>: xs) :$ val y :$ val ys+  constructors xs  =  [ val ([] -: xs)+                      , value ":" ((:) ->>: xs) :$ hole x :$ hole xs+                      ]+    where+    x  =  head xs+++instance (Express a, Express b) => Constructors (a,b) where+  expr1 (x,y)  =  value "," ((,) ->>: (x,y))+               :$ val x :$ val y+  constructors xy  =  [value "," ((,) ->>: xy) :$ hole x :$ hole y]+    where+    (x,y) = (undefined,undefined) -: xy++instance (Express a, Express b, Express c) => Constructors (a,b,c) where+  expr1 (x,y,z)  =  value ",," ((,,) ->>>: (x,y,z))+                 :$ val x :$ val y :$ val z++  constructors xyz  =  [value ",," ((,,) ->>>: xyz) :$ hole x :$ hole y :$ hole z]+    where+    (x,y,z) = (undefined,undefined,undefined) -: xyz++instance Express a => Constructors (Maybe a) where+  expr1 mx@Nothing   =  value "Nothing" (Nothing -: mx)+  expr1 mx@(Just x)  =  value "Just"    (Just   ->: mx) :$ val x+  constructors mx  =  [ value "Nothing" (Nothing -: mx)+                      , value "Just" (Just ->: mx) :$ hole x+                      ]+    where+    x  =  Just undefined -: mx+++instance (Express a, Express b) => Constructors (Either a b) where+  expr1 lx@(Left x)   =  value "Left"  (Left  ->: lx) :$ val x+  expr1 ry@(Right y)  =  value "Right" (Right ->: ry) :$ val y+  constructors exy  =  [ value "Left" (Left ->: exy) :$ hole x+                       , value "Right" (Right ->: exy) :$ hole y+                       ]+    where+    x  =  Left undefined -: exy+    y  =  Right undefined -: exy

@@ -29,12 +29,13 @@  import Data.Express import Data.Express.Fixtures hiding ((-==-))+import qualified Data.Express.Triexpr as T  import Test.LeanCheck import Test.LeanCheck.Tiers import Test.LeanCheck.Error (errorToTrue, errorToFalse, errorToNothing) -import Test.Speculate.Reason (isRootNormalE)+import Test.Speculate.Reason (Thy, rules, equations, canReduceTo, printThy) import Test.Speculate.Engine (theoryFromAtoms, groundBinds)  import Conjure.Expr@@ -132,10 +133,10 @@   where   pr n []  =  putStrLn $ "cannot conjure"   pr n ((is,cs,es):rs)  =  do-    -- when (n==1) $ putStrLn $ unlines $ map show es     putStrLn $ "-- looking through "             ++ show (length cs)             ++ " candidates of size " ++ show n+    -- when (n<=6) $ putStrLn $ unlines $ map show es     case is of       []     ->  pr (n+1) rs       (i:_)  ->  do putStrLn $ showEq i@@ -163,7 +164,7 @@   tests  =  [ffxx //- bs | bs <- dbss]   implementationsT  =  mapT (vffxx -==-) $ filterT implements candidatesT   implements e  =  apparentlyTerminates rrff e-                && ffxx ?=? recursexpr maxRecursionSize vffxx e+                && requal (vffxx,e) ffxx e   candidatesT  =  filterT (\e -> typ e == typ ffxx) allCandidatesT   allCandidatesT  =  take maxSize                   $  candidateExprs nm f maxEquationSize maxRecursiveCalls (===) es@@ -172,10 +173,10 @@   (rrff:xxs)  =  unfoldApp vffxx    (===)  =  conjureAreEqual f maxTests-  e1 ?=? e2  =  isTrueWhenDefined (e1 -==- e2)+  requal dfn e1 e2  =  isTrueWhenDefined dfn (e1 -==- e2)   (-==-)  =  conjureMkEquation f -  isTrueWhenDefined e  =  all (errorToFalse . eval False) $ map (e //-) dbss+  isTrueWhenDefined dfn e  =  all (errorToFalse . reval dfn maxRecursionSize False) $ map (e //-) dbss    bss, dbss :: [[(Expr,Expr)]]   bss  =  take maxSearchTests $ groundBinds (conjureTiersFor f) ffxx@@ -194,16 +195,68 @@                -> (Expr -> Expr -> Bool)                -> [Expr]                -> [[Expr]]-candidateExprs nm f sz mc (===) es  =-  enumerateAppsFor efxs keep $ nub $ (ef:exs) ++ es ++ [conjureIf f]+candidateExprs nm f sz mc (===) es  =  as \/ ts   where+  ts  =  filterT keepIf+      $  foldAppProducts (conjureIf f) [cs, as, rs]+      \/ foldAppProducts (conjureIf f) [cs, rs, as]+  cs  =  filterT (`notElem` [val False, val True])+      $  forN (hole (undefined :: Bool))+  as  =  forN efxs+  rs  =  forR efxs+  forN h  =  enumerateAppsFor h keep [exs ++ es]+  forD h  =  enumerateAppsFor h (const True) [exs ++ ds]+  forR h  =  filterT (\e -> (ef `elem`) (vars e))+          $  enumerateAppsFor h keep $ [exs ++ es] \/ recs   efxs  =  conjureVarApplication nm f   (ef:exs)  =  unfoldApp efxs-  keep e  =  isRootNormalE thy e && count (== ef) (vars e) <= mc+  keep e  =  isRootNormalE thy e+          && count (== ef) (vars e) <= mc   thy  =  theoryFromAtoms (===) sz . (:[]) . nub-       $  conjureHoles f ++ [val False, val True] ++ es ++ [conjureIf f]+       $  conjureHoles f ++ [val False, val True] ++ es+  ds  =  map snd $ deconstructors f 60 es+  recs  =  filterT (efxs /=)+        $  foldAppProducts ef [forD h | h <- conjureArgumentHoles f] +-- | Example:+--+-- > > deconstructors and 60+-- > >   [ val False+-- > >   , val True+-- > >   , value "null" (null::[Bool]->Bool)+-- > >   , value "head" (head :: [Bool] -> Bool)+-- > >   , value "tail" (tail :: [Bool] -> [Bool])+-- > >   , value "drop1" (drop 1 :: [Bool] -> [Bool])+-- > >   ]+-- > [tail :: [Bool] -> [Bool]]+--+-- In this case, inc is a deconstructor as it converges for more than half the+-- values:+--+-- > > deconstructors (negate :: Int -> Int) 60+-- > >   [ value "eq0" ((==0) :: Int -> Bool)+-- > >   , val (0 :: Int)+-- > >   , value "==" ((==) :: Int -> Int -> Bool)+-- > >   , value "dec" (subtract 1 :: Int -> Int)+-- > >   , value "inc" ((+1) :: Int -> Int)+-- > >   ]+-- > [ ((0 ==) :: Int -> Bool,dec :: Int -> Int)+-- > , ((0 ==) :: Int -> Bool,inc :: Int -> Int)+-- > ]+deconstructors :: Conjurable f => f -> Int -> [Expr] -> [(Expr, Expr)]+deconstructors f maxTests es  =+  [ (z, d)+  | d <- es+  , h <- take 1 [h | h <- hs, mtyp (d :$ h) == mtyp h]+  , z <- take 1 [z | z <- es2, mtyp (z :$ h) == mtyp b && isDeconstructor h z d]+  ]+  where+  b  =  hole (undefined :: Bool)+  hs  =  nub $ conjureArgumentHoles f+  isDeconstructor  =  conjureIsDeconstructor f maxTests+  es2  =  es ++ [e1 :$ e2 | e1 <- es, e2 <- es, isWellTyped (e1 :$ e2)] + candidatesTD :: (Expr -> Bool) -> Expr -> [Expr] -> [[Expr]] candidatesTD keep h primitives  =  filterT (not . hasHole)                                 $  town [[h]]@@ -224,3 +277,52 @@   replacementsFor :: Expr -> [[Expr]]   replacementsFor h  =  filterT (\e -> typ e == typ h)                      $  primitiveApplications primitives+++-- hardcoded filtering rules++keepIf :: Expr -> Bool+keepIf (Value "if" _ :$ ep :$ ex :$ ey)+  | ex == ey  =  False+  | anormal ep  =  False+  | otherwise  =  case binding ep of+                  Just (v,e) -> v `notElem` values ex+                  Nothing -> True+  where+  anormal (Value "==" _ :$ e1 :$ e2) | isVar e2 || isConst e1  =  True+  anormal _                                                    =  False+  binding :: Expr -> Maybe (Expr,Expr)+  binding (Value "==" _ :$ e1 :$ e2) | isVar e1   =  Just (e1,e2)+                                     | isVar e2   =  Just (e2,e1)+  binding _                                       =  Nothing+keepIf _  =  error "Conjure.Engine.keepIf: not an if"++++--- normality checks ---++isRootNormal :: Thy -> Expr -> Bool+isRootNormal thy e  =  null $ T.lookup e trie+  where+  trie  =  T.fromList (rules thy)++isRootNormalE :: Thy -> Expr -> Bool+isRootNormalE thy e  =  isRootNormal thy e+                    &&  null (filter (e ->-) [e2 //- bs | (_,bs,e2) <- T.lookup e trie])+  where+  trie  =  T.fromList $ equations thy ++ map swap (equations thy)+  (->-)  =  canReduceTo thy+++--- tiers utils ---++productsWith :: ([a] -> a) -> [ [[a]] ] -> [[a]]+productsWith f  =  mapT f . products+-- TODO: move to LeanCheck?++delayedProductsWith :: ([a] -> a) -> [ [[a]] ] -> [[a]]+delayedProductsWith f xsss  =  productsWith f xsss `addWeight` length xsss+-- TODO: move to LeanCheck?++foldAppProducts :: Expr -> [ [[Expr]] ] -> [[Expr]]+foldAppProducts ef  =  delayedProductsWith (foldApp . (ef:))

@@ -6,7 +6,7 @@ -- -- This internal module reexports 'Data.Express' along with a few other -- utilities.-{-# LANGUAGE CPP #-}+{-# LANGUAGE CPP, TupleSections #-} module Conjure.Expr   ( module Data.Express   , module Data.Express.Fixtures@@ -30,6 +30,9 @@   , ($$**)   , ($$|<)   , possibleHoles+  , isDeconstructionE+  , revaluate+  , reval    , enumerateApps   , enumerateAppsFor@@ -44,6 +47,9 @@ import Data.Express.Utils.Typeable import Data.Express.Fixtures hiding ((-==-)) +import Data.Dynamic+import Control.Applicative ((<$>)) -- for GHC <= 7.8+ import Test.LeanCheck (filterT, (\/), delay, productWith, productMaybeWith)  -- | /O(n)/.@@ -277,7 +283,7 @@  -- -- Expression enumeration -- -- -enumerateAppsFor :: Expr -> (Expr -> Bool) -> [Expr] -> [[Expr]]+enumerateAppsFor :: Expr -> (Expr -> Bool) -> [[Expr]] -> [[Expr]] enumerateAppsFor  =  enumerateApps3For  enumerateApps :: (Expr -> Bool) -> [Expr] -> [[Expr]]@@ -311,16 +317,51 @@                       [] -> Nothing                       es -> Just es -enumerateApps3For :: Expr -> (Expr -> Bool) -> [Expr] -> [[Expr]]-enumerateApps3For h keep es  =  for h+enumerateApps3For :: Expr -> (Expr -> Bool) -> [[Expr]] -> [[Expr]]+enumerateApps3For h keep ess  =  for h   where   hs :: [Expr]-  hs  =  possibleHoles es+  hs  =  possibleHoles . concat $ take 1 ess   for :: Expr -> [[Expr]]-  for h  =  [e | e <- es, typ h == typ e]-         :  foldr (\/) [] [ filterT keep $ productWith (:$) (for hf) (for hx)-                          | hf <- hs-                          , hx <- hs-                          , Just hfx <- [hf $$ hx]-                          , typ h == typ hfx-                          ]+  for h  =  filterT (\e -> typ h == typ e) ess \/ delay apps+    where+    apps  =  foldr (\/) []+          [  filterT keep $ productWith (:$) (for hf) (for hx)+          |  hf <- hs+          ,  hx <- hs+          ,  Just hfx <- [hf $$ hx]+          ,  typ h == typ hfx+          ]++-- Like 'isDeconstruction' but lifted over the 'Expr' type.+isDeconstructionE :: [Expr] -> Expr -> Expr -> Bool+--                   [a] -> (a -> Bool) -> (a -> a) -> Bool+isDeconstructionE [] _ _  =  error "isDeconstructionE: empty list of test values"+isDeconstructionE es ez ed | all isIllTyped [f :$ e | e <- es, f <- [ez,ed]]  =  error "isDeconstructionE: types do not match"+isDeconstructionE es ez ed  =  isDeconstruction es (eval False . (ez :$)) (ed :$)++recursiveToDynamic :: (Expr,Expr) -> Int -> Expr -> Maybe Dynamic+recursiveToDynamic (efxs, ebody) n  =  fmap snd . re n+  where+  (ef':exs')  =  unfoldApp efxs+  re :: Int -> Expr -> Maybe (Int, Dynamic)+  re n _  | n <= 0  =  error "recursiveToDynamic: recursion limit reached"+  re n (Value "if" _ :$ ec :$ ex :$ ey)  =  case evaluate ec of+    Nothing    -> Nothing+    Just True  -> re n ex+    Just False -> re n ey+  re n e  =  case unfoldApp e of+    [] -> error "recursiveToDynamic: empty application unfold"  -- should never happen+    [e] -> (n,) <$> toDynamic e+    (ef:exs) | ef == ef' -> re (n-1) $ ebody //- zip exs' exs+             | otherwise -> foldl ($$) (re n ef) exs+  Just (n,d1) $$ e2  =  case re n e2 of+                        Nothing -> Nothing+                        Just (n', d2) -> (n',) <$> dynApply d1 d2+  _ $$ _             =  Nothing++revaluate :: Typeable a => (Expr,Expr) -> Int -> Expr -> Maybe a+revaluate dfn n e  =  recursiveToDynamic dfn n e >>= fromDynamic++reval :: Typeable a => (Expr,Expr) -> Int -> a -> Expr -> a+reval dfn n x e = fromMaybe x (revaluate dfn n e)

@@ -21,7 +21,16 @@   , iterateUntil   , mzip   , groupOn+#if __GLASGOW_HASKELL__ < 710   , sortOn+#endif+  , takeUntil+  , takeNextWhile+  , takeNextUntil+  , deconstructions+  , isDeconstruction+  , idIO+  , mapHead   ) where @@ -32,6 +41,8 @@ import Data.Tuple import Data.Typeable +import System.IO.Unsafe+ count :: (a -> Bool) -> [a] -> Int count p  =  length . filter p @@ -59,3 +70,44 @@ sortOn :: Ord b => (a -> b) -> [a] -> [a] sortOn f = sortBy (compare `on` f) #endif++takeUntil :: (a -> Bool) -> [a] -> [a]+takeUntil p  =  takeWhile (not . p)++takeNextWhile :: (a -> a -> Bool) -> [a] -> [a]+takeNextWhile (?)  =  t+  where+  t (x:y:xs) | x ? y  =  x : t (y:xs)+             | otherwise  =  [x]+  t xs  =  xs++takeNextUntil :: (a -> a -> Bool) -> [a] -> [a]+takeNextUntil (?)  =  takeNextWhile (not .: (?))+  where+  (.:)  =  (.) . (.)++deconstructions :: (a -> Bool) -> (a -> a) -> a -> [a]+deconstructions z d x  =  takeUntil z+                       $  iterate d x++-- | The deconstruction is considered valid if it converges+--   for more than half of the given values.+isDeconstruction :: [a] -> (a -> Bool) -> (a -> a) -> Bool+isDeconstruction xs z d  =  count is xs >= l `div` 2+  where+  is x  =  length (take l $ deconstructions z d x) < l+  l  =  length xs++-- | __WARNING:__+--   uses 'unsafePerformIO' and should only be used for debugging!+--+-- > > idIO print 10+-- > 10+-- > 10+idIO :: (a -> IO ()) -> a -> a+idIO action x  =  unsafePerformIO $ do+  action x+  return x++mapHead :: (a -> a) -> [a] -> [a]+mapHead f (x:xs)  =  f x : xs

@@ -11,4 +11,4 @@ extra-deps: - leancheck-0.9.6 - speculate-0.4.6-- express-0.1.10+- express-0.1.12

@@ -1,42 +1,42 @@ sum :: [Int] -> Int -- testing 4 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4--- looking through 13 candidates of size 5--- looking through 26 candidates of size 6--- looking through 59 candidates of size 7--- looking through 140 candidates of size 8--- looking through 326 candidates of size 9--- looking through 776 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4+-- looking through 5 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 15 candidates of size 7+-- looking through 27 candidates of size 8+-- looking through 53 candidates of size 9+-- looking through 101 candidates of size 10 sum xs  =  if null xs then 0 else head xs + sum (tail xs)  sum :: [Int] -> Int -- testing 6 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4--- looking through 13 candidates of size 5--- looking through 26 candidates of size 6--- looking through 59 candidates of size 7--- looking through 140 candidates of size 8--- looking through 326 candidates of size 9--- looking through 776 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4+-- looking through 5 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 15 candidates of size 7+-- looking through 27 candidates of size 8+-- looking through 53 candidates of size 9+-- looking through 101 candidates of size 10 sum xs  =  if null xs then 0 else head xs + sum (tail xs)  sum :: [Int] -> Int -- testing 6 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4--- looking through 13 candidates of size 5--- looking through 26 candidates of size 6--- looking through 59 candidates of size 7--- looking through 140 candidates of size 8--- looking through 326 candidates of size 9--- looking through 776 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4+-- looking through 5 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 15 candidates of size 7+-- looking through 27 candidates of size 8+-- looking through 53 candidates of size 9+-- looking through 101 candidates of size 10 sum xs  =  if null xs then 0 else head xs + sum (tail xs) 

@@ -0,0 +1,37 @@+qsort :: [Int] -> [Int]+-- testing 60 combinations of argument values+-- looking through 2 candidates of size 1+-- looking through 2 candidates of size 2+-- looking through 3 candidates of size 3+-- looking through 11 candidates of size 4+-- looking through 28 candidates of size 5+-- looking through 72 candidates of size 6+-- looking through 207 candidates of size 7+-- looking through 611 candidates of size 8+-- looking through 1779 candidates of size 9+-- looking through 5301 candidates of size 10+-- looking through 16103 candidates of size 11+-- looking through 49113 candidates of size 12+cannot conjure+pow :: Int -> Int -> Int+-- testing 5 combinations of argument values+-- looking through 4 candidates of size 1+-- looking through 3 candidates of size 2+-- looking through 13 candidates of size 3+-- looking through 20 candidates of size 4+-- looking through 80 candidates of size 5+-- looking through 172 candidates of size 6+-- looking through 614 candidates of size 7+-- looking through 1675 candidates of size 8+cannot conjure+pow :: Int -> Int -> Int+-- testing 5 combinations of argument values+-- looking through 4 candidates of size 1+-- looking through 2 candidates of size 2+-- looking through 15 candidates of size 3+-- looking through 26 candidates of size 4+-- looking through 111 candidates of size 5+-- looking through 307 candidates of size 6+-- looking through 1122 candidates of size 7+-- looking through 3727 candidates of size 8+cannot conjure

@@ -2,26 +2,26 @@ -- testing 60 combinations of argument values -- looking through 4 candidates of size 1 -- looking through 0 candidates of size 2--- looking through 48 candidates of size 3+-- looking through 32 candidates of size 3 x ? y  =  x + y  (?) :: Int -> Int -> Int -- testing 60 combinations of argument values -- looking through 4 candidates of size 1 -- looking through 0 candidates of size 2--- looking through 48 candidates of size 3+-- looking through 32 candidates of size 3 x ? y  =  x * y  i :: Int -> Int -- testing 60 combinations of argument values -- looking through 3 candidates of size 1--- looking through 3 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 18 candidates of size 3 i x  =  x + 1  d :: Int -> Int -- testing 60 combinations of argument values -- looking through 3 candidates of size 1--- looking through 3 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 18 candidates of size 3 cannot conjure

@@ -2,32 +2,36 @@ -- testing 60 combinations of argument values -- looking through 1 candidates of size 1 -- looking through 1 candidates of size 2--- looking through 3 candidates of size 3--- looking through 7 candidates of size 4--- looking through 13 candidates of size 5--- looking through 23 candidates of size 6--- looking through 45 candidates of size 7--- looking through 111 candidates of size 8--- looking through 301 candidates of size 9--- looking through 789 candidates of size 10--- looking through 1919 candidates of size 11--- looking through 4539 candidates of size 12--- looking through 10873 candidates of size 13+-- looking through 1 candidates of size 3+-- looking through 1 candidates of size 4+-- looking through 1 candidates of size 5+-- looking through 1 candidates of size 6+-- looking through 1 candidates of size 7+-- looking through 5 candidates of size 8+-- looking through 21 candidates of size 9+-- looking through 60 candidates of size 10+-- looking through 136 candidates of size 11+-- looking through 288 candidates of size 12+-- looking through 601 candidates of size 13 drop x y  =  if null y || x == 0 then y else drop (dec x) (tail y)  take :: Int -> [A] -> [A] -- testing 60 combinations of argument values -- looking through 2 candidates of size 1 -- looking through 2 candidates of size 2--- looking through 6 candidates of size 3--- looking through 18 candidates of size 4--- looking through 34 candidates of size 5--- looking through 94 candidates of size 6--- looking through 268 candidates of size 7--- looking through 792 candidates of size 8--- looking through 2378 candidates of size 9--- looking through 6912 candidates of size 10--- looking through 20324 candidates of size 11--- looking through 61034 candidates of size 12--- looking through 184544 candidates of size 13-cannot conjure+-- looking through 2 candidates of size 3+-- looking through 6 candidates of size 4+-- looking through 10 candidates of size 5+-- looking through 14 candidates of size 6+-- looking through 26 candidates of size 7+-- looking through 54 candidates of size 8+-- looking through 122 candidates of size 9+-- looking through 280 candidates of size 10+-- looking through 636 candidates of size 11+-- looking through 1512 candidates of size 12+-- looking through 3618 candidates of size 13+-- looking through 8400 candidates of size 14+-- looking through 19152 candidates of size 15+-- looking through 43184 candidates of size 16+take x y  =  if null y || x == 0 then [] else head y:take (dec x) (tail y)+

@@ -1,7 +1,7 @@ double :: Int -> Int -- testing 4 combinations of argument values -- looking through 3 candidates of size 1--- looking through 3 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 5 candidates of size 3 double x  =  x + x @@ -9,24 +9,24 @@ -- testing 4 combinations of argument values -- looking through 4 candidates of size 1 -- looking through 0 candidates of size 2--- looking through 29 candidates of size 3+-- looking through 13 candidates of size 3 add x y  =  x + y  square :: Int -> Int -- testing 3 combinations of argument values -- looking through 3 candidates of size 1--- looking through 3 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 5 candidates of size 3 square x  =  x * x  tnpo :: Int -> Int -- testing 3 combinations of argument values -- looking through 3 candidates of size 1--- looking through 3 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 5 candidates of size 3--- looking through 20 candidates of size 4+-- looking through 0 candidates of size 4 -- looking through 13 candidates of size 5--- looking through 97 candidates of size 6+-- looking through 0 candidates of size 6 -- looking through 42 candidates of size 7 tnpo x  =  x + (x + (x + 1)) 

@@ -1,44 +1,44 @@ and :: [Bool] -> Bool -- testing 14 combinations of argument values -- looking through 2 candidates of size 1--- looking through 3 candidates of size 2--- looking through 6 candidates of size 3--- looking through 6 candidates of size 4--- looking through 16 candidates of size 5--- looking through 41 candidates of size 6--- looking through 87 candidates of size 7--- looking through 214 candidates of size 8--- looking through 592 candidates of size 9-and ps  =  null ps || head ps && and (tail ps)+-- looking through 2 candidates of size 2+-- looking through 4 candidates of size 3+-- looking through 4 candidates of size 4+-- looking through 6 candidates of size 5+-- looking through 15 candidates of size 6+-- looking through 37 candidates of size 7+-- looking through 88 candidates of size 8+-- looking through 200 candidates of size 9+-- looking through 464 candidates of size 10+and ps  =  if null ps then True else head ps && and (tail ps)  or :: [Bool] -> Bool -- testing 14 combinations of argument values -- looking through 2 candidates of size 1--- looking through 3 candidates of size 2--- looking through 6 candidates of size 3--- looking through 6 candidates of size 4--- looking through 16 candidates of size 5--- looking through 41 candidates of size 6--- looking through 87 candidates of size 7--- looking through 214 candidates of size 8--- looking through 592 candidates of size 9--- looking through 1503 candidates of size 10--- looking through 3987 candidates of size 11-or ps  =  not (null ps || not (head ps || or (tail ps)))+-- looking through 2 candidates of size 2+-- looking through 4 candidates of size 3+-- looking through 4 candidates of size 4+-- looking through 6 candidates of size 5+-- looking through 15 candidates of size 6+-- looking through 37 candidates of size 7+-- looking through 88 candidates of size 8+-- looking through 200 candidates of size 9+-- looking through 464 candidates of size 10+or ps  =  if null ps then False else head ps || or (tail ps)  and :: [Bool] -> Bool -- testing 14 combinations of argument values -- looking through 2 candidates of size 1--- looking through 3 candidates of size 2--- looking through 6 candidates of size 3--- looking through 8 candidates of size 4+-- looking through 2 candidates of size 2+-- looking through 4 candidates of size 3+-- looking through 6 candidates of size 4 and ps  =  foldr (&&) True ps  or :: [Bool] -> Bool -- testing 14 combinations of argument values -- looking through 2 candidates of size 1--- looking through 3 candidates of size 2--- looking through 6 candidates of size 3--- looking through 8 candidates of size 4+-- looking through 2 candidates of size 2+-- looking through 4 candidates of size 3+-- looking through 6 candidates of size 4 or ps  =  foldr (||) False ps 

@@ -1,7 +1,7 @@ factorial :: Int -> Int -- testing 6 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 0 candidates of size 3 -- looking through 2 candidates of size 4 factorial n  =  product (enumFromTo 1 n)@@ -9,14 +9,14 @@ factorial :: Int -> Int -- testing 6 combinations of argument values -- looking through 3 candidates of size 1--- looking through 5 candidates of size 2--- looking through 8 candidates of size 3--- looking through 26 candidates of size 4--- looking through 59 candidates of size 5--- looking through 167 candidates of size 6--- looking through 581 candidates of size 7--- looking through 1654 candidates of size 8--- looking through 5736 candidates of size 9--- looking through 17617 candidates of size 10+-- looking through 2 candidates of size 2+-- looking through 5 candidates of size 3+-- looking through 6 candidates of size 4+-- looking through 20 candidates of size 5+-- looking through 27 candidates of size 6+-- looking through 87 candidates of size 7+-- looking through 167 candidates of size 8+-- looking through 421 candidates of size 9+-- looking through 968 candidates of size 10 factorial n  =  if n == 0 then 1 else n * factorial (dec n) 

@@ -0,0 +1,17 @@+fibonacci :: Int -> Int+-- testing 8 combinations of argument values+-- looking through 2 candidates of size 1+-- looking through 2 candidates of size 2+-- looking through 6 candidates of size 3+-- looking through 1 candidates of size 4+-- looking through 11 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 27 candidates of size 7+-- looking through 20 candidates of size 8+-- looking through 95 candidates of size 9+-- looking through 148 candidates of size 10+-- looking through 431 candidates of size 11+-- looking through 925 candidates of size 12+-- looking through 2377 candidates of size 13+fibonacci n  =  if n <= 1 then 1 else fibonacci (dec n) + fibonacci (dec (dec n))+

@@ -1,59 +1,59 @@ second :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3 second xs  =  head (tail xs)  third :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4 third xs  =  head (tail (tail xs))  sum :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4--- looking through 13 candidates of size 5--- looking through 26 candidates of size 6--- looking through 59 candidates of size 7--- looking through 140 candidates of size 8--- looking through 326 candidates of size 9--- looking through 776 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4+-- looking through 5 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 15 candidates of size 7+-- looking through 27 candidates of size 8+-- looking through 53 candidates of size 9+-- looking through 101 candidates of size 10 sum xs  =  if null xs then 0 else head xs + sum (tail xs)  product :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4--- looking through 13 candidates of size 5--- looking through 26 candidates of size 6--- looking through 59 candidates of size 7--- looking through 140 candidates of size 8--- looking through 326 candidates of size 9--- looking through 776 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4+-- looking through 5 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 15 candidates of size 7+-- looking through 27 candidates of size 8+-- looking through 53 candidates of size 9+-- looking through 101 candidates of size 10 product xs  =  if null xs then 1 else head xs * product (tail xs)  sum :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 8 candidates of size 4+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 5 candidates of size 4 sum xs  =  foldr (+) 0 xs  product :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 8 candidates of size 4+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 5 candidates of size 4 product xs  =  foldr (*) 1 xs 

@@ -1,85 +1,85 @@ length :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 1 candidates of size 2--- looking through 2 candidates of size 3--- looking through 3 candidates of size 4--- looking through 5 candidates of size 5--- looking through 11 candidates of size 6--- looking through 20 candidates of size 7--- looking through 45 candidates of size 8--- looking through 79 candidates of size 9+-- looking through 0 candidates of size 2+-- looking through 1 candidates of size 3+-- looking through 0 candidates of size 4+-- looking through 1 candidates of size 5+-- looking through 0 candidates of size 6+-- looking through 5 candidates of size 7+-- looking through 8 candidates of size 8+-- looking through 19 candidates of size 9 length xs  =  if null xs then 0 else 1 + length (tail xs)  reverse :: [Int] -> [Int] -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 4 candidates of size 2--- looking through 9 candidates of size 3--- looking through 24 candidates of size 4--- looking through 65 candidates of size 5--- looking through 215 candidates of size 6--- looking through 673 candidates of size 7--- looking through 2174 candidates of size 8--- looking through 7100 candidates of size 9--- looking through 23503 candidates of size 10--- looking through 78714 candidates of size 11+-- looking through 2 candidates of size 2+-- looking through 5 candidates of size 3+-- looking through 9 candidates of size 4+-- looking through 23 candidates of size 5+-- looking through 57 candidates of size 6+-- looking through 147 candidates of size 7+-- looking through 381 candidates of size 8+-- looking through 1014 candidates of size 9+-- looking through 2736 candidates of size 10+-- looking through 7447 candidates of size 11 reverse xs  =  if null xs then xs else reverse (tail xs) ++ unit (head xs)  sort :: [Int] -> [Int] -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 4 candidates of size 2--- looking through 6 candidates of size 3--- looking through 12 candidates of size 4--- looking through 31 candidates of size 5--- looking through 98 candidates of size 6--- looking through 287 candidates of size 7--- looking through 790 candidates of size 8--- looking through 2188 candidates of size 9--- looking through 6290 candidates of size 10+-- looking through 2 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 6 candidates of size 4+-- looking through 11 candidates of size 5+-- looking through 21 candidates of size 6+-- looking through 49 candidates of size 7+-- looking through 119 candidates of size 8+-- looking through 272 candidates of size 9+-- looking through 625 candidates of size 10 sort xs  =  if null xs then xs else insert (head xs) (sort (tail xs))  (++) :: [Int] -> [Int] -> [Int] -- testing 60 combinations of argument values -- looking through 3 candidates of size 1 -- looking through 3 candidates of size 2--- looking through 12 candidates of size 3--- looking through 39 candidates of size 4--- looking through 83 candidates of size 5--- looking through 290 candidates of size 6--- looking through 1013 candidates of size 7--- looking through 3482 candidates of size 8--- looking through 11171 candidates of size 9--- looking through 36185 candidates of size 10--- looking through 123417 candidates of size 11+-- looking through 3 candidates of size 3+-- looking through 12 candidates of size 4+-- looking through 21 candidates of size 5+-- looking through 30 candidates of size 6+-- looking through 102 candidates of size 7+-- looking through 351 candidates of size 8+-- looking through 969 candidates of size 9+-- looking through 2625 candidates of size 10+-- looking through 7086 candidates of size 11 xs ++ ys  =  if null xs then ys else head xs:(tail xs ++ ys)  length :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 1 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 1 candidates of size 3--- looking through 4 candidates of size 4--- looking through 2 candidates of size 5--- looking through 10 candidates of size 6+-- looking through 2 candidates of size 4+-- looking through 1 candidates of size 5+-- looking through 7 candidates of size 6 length xs  =  foldr (const (1 +)) 0 xs  reverse :: [Int] -> [Int] -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 1 candidates of size 3--- looking through 5 candidates of size 4+-- looking through 0 candidates of size 4 -- looking through 1 candidates of size 5--- looking through 17 candidates of size 6--- looking through 37 candidates of size 7+-- looking through 8 candidates of size 6+-- looking through 13 candidates of size 7 reverse xs  =  foldr (flip (++) . unit) [] xs  sort :: [Int] -> [Int] -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2+-- looking through 0 candidates of size 2 -- looking through 0 candidates of size 3 -- looking through 2 candidates of size 4 sort xs  =  foldr insert [] xs@@ -88,7 +88,22 @@ -- testing 60 combinations of argument values -- looking through 3 candidates of size 1 -- looking through 0 candidates of size 2--- looking through 9 candidates of size 3+-- looking through 0 candidates of size 3 -- looking through 4 candidates of size 4 xs ++ ys  =  foldr (:) ys xs++(\/) :: [Int] -> [Int] -> [Int]+-- testing 60 combinations of argument values+-- looking through 3 candidates of size 1+-- looking through 3 candidates of size 2+-- looking through 3 candidates of size 3+-- looking through 12 candidates of size 4+-- looking through 21 candidates of size 5+-- looking through 30 candidates of size 6+-- looking through 102 candidates of size 7+-- looking through 351 candidates of size 8+-- looking through 969 candidates of size 9+-- looking through 2625 candidates of size 10+-- looking through 7086 candidates of size 11+xs \/ ys  =  if null xs then xs else head xs:ys \/ tail xs 

@@ -1,29 +1,29 @@ sum :: [Int] -> Int -- testing 3 combinations of argument values -- looking through 1 candidates of size 1--- looking through 2 candidates of size 2--- looking through 2 candidates of size 3--- looking through 2 candidates of size 4--- looking through 5 candidates of size 5--- looking through 10 candidates of size 6--- looking through 19 candidates of size 7--- looking through 34 candidates of size 8--- looking through 64 candidates of size 9--- looking through 129 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 1 candidates of size 3+-- looking through 1 candidates of size 4+-- looking through 2 candidates of size 5+-- looking through 2 candidates of size 6+-- looking through 5 candidates of size 7+-- looking through 10 candidates of size 8+-- looking through 17 candidates of size 9+-- looking through 28 candidates of size 10 sum xs  =  if null xs then 0 else head xs + sum (tail xs)  (++) :: [Int] -> [Int] -> [Int] -- testing 3 combinations of argument values -- looking through 2 candidates of size 1 -- looking through 2 candidates of size 2--- looking through 6 candidates of size 3--- looking through 18 candidates of size 4--- looking through 38 candidates of size 5--- looking through 110 candidates of size 6--- looking through 334 candidates of size 7--- looking through 1018 candidates of size 8--- looking through 2958 candidates of size 9--- looking through 8614 candidates of size 10--- looking through 25910 candidates of size 11+-- looking through 2 candidates of size 3+-- looking through 6 candidates of size 4+-- looking through 10 candidates of size 5+-- looking through 14 candidates of size 6+-- looking through 50 candidates of size 7+-- looking through 182 candidates of size 8+-- looking through 506 candidates of size 9+-- looking through 1310 candidates of size 10+-- looking through 3298 candidates of size 11 xs ++ ys  =  if null xs then ys else head xs:(tail xs ++ ys) 

@@ -1,30 +1,30 @@ third :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4 third xs  =  head (tail (tail xs))  product :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 5 candidates of size 4--- looking through 13 candidates of size 5--- looking through 26 candidates of size 6--- looking through 59 candidates of size 7--- looking through 140 candidates of size 8--- looking through 326 candidates of size 9--- looking through 776 candidates of size 10+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 2 candidates of size 4+-- looking through 5 candidates of size 5+-- looking through 5 candidates of size 6+-- looking through 15 candidates of size 7+-- looking through 27 candidates of size 8+-- looking through 53 candidates of size 9+-- looking through 101 candidates of size 10 product xs  =  if null xs then 1 else head xs * product (tail xs)  product :: [Int] -> Int -- testing 60 combinations of argument values -- looking through 2 candidates of size 1--- looking through 2 candidates of size 2--- looking through 3 candidates of size 3--- looking through 8 candidates of size 4+-- looking through 1 candidates of size 2+-- looking through 2 candidates of size 3+-- looking through 5 candidates of size 4 product xs  =  foldr (*) 1 xs 

@@ -18,4 +18,49 @@    , holds n $ \xs ys -> length xs >= length ys                     ==> zipWith (<>) xs (ys <> repeat mempty) == mzip xs (ys :: [[Int]])++  , takeUntil (== 5) [1..] == [1,2,3,4]+  , takeUntil (> 4)  [1..] == [1,2,3,4]++  , takeNextWhile (<) []  ==  ([]::[Int])+  , takeNextWhile (<) [0]  ==  [0]+  , takeNextWhile (<) [0,1]  ==  [0,1]+  , takeNextWhile (<) [0,1,2]  ==  [0,1,2]+  , takeNextWhile (<) [0,1,2,1,0]  ==  [0,1,2]+  , takeNextWhile (/=) [3,2,1,0,0,0] == [3,2,1,0]+  , takeNextUntil (==) [3,2,1,0,0,0] == [3,2,1,0]+  , takeNextUntil (>) [0,1,2,1,0] == [0,1,2]++  , deconstructions null tail [1,2,3 :: Int]+    == [ [1,2,3]+       , [2,3]+       , [3]+       ]+  , deconstructions null tail ([] :: [Int]) == []+  , deconstructions (==0) (`div`2) 15+    == [15, 7, 3, 1]++  ,       isDec m (null :: [A] -> Bool) tail+  , not $ isDec m (null :: [A] -> Bool) id+  ,       isDec m (null :: [A] -> Bool) (drop 1)+  ,       isDec m (null :: [A] -> Bool) (drop 2)+  ,       isDec m (null :: [A] -> Bool) (drop 3)+  ,       isDec m (<0) (\x -> x-1 :: Int)+  ,       isDec m (<0) (\x -> x-2 :: Int)+  ,       isDec m (==0) (\x -> x-1 :: Int)+  , not $ isDec m (==0) (\x -> x-2 :: Int)+  ,       isDec m (==0) (\x -> x `div` 2 :: Int)+  ,       isDec m (==0) (\x -> x `quot` 2 :: Int)   ]+  where+  m  =  n `div` 60+++-- Checks if the given pair of functions are a valid deconstruction+-- for Listable values.+-- The deconstruction is considered valid if it converges+-- for more than 50% of values.+isDec :: Listable a+      => Int+      -> (a -> Bool) -> (a -> a) -> Bool+isDec m  =  isDeconstruction (take m list)