cflp 0.2.1 → 0.2.2

raw patch · 10 files changed

+97/−137 lines, 10 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• cflp.cabal +2/−3
• src/Control/CFLP.lhs +0/−1
• src/Control/CFLP/Tests/CallTimeChoice.lhs +3/−3
• src/Data/LazyNondet.lhs +2/−3
• src/Data/LazyNondet/Combinators.lhs +0/−77
• src/Data/LazyNondet/Matching.lhs +51/−3
• src/Data/LazyNondet/Narrowing.lhs +23/−35
• src/Data/LazyNondet/Primitive.lhs +5/−5
• src/Data/LazyNondet/Types.lhs +10/−6
• src/Data/LazyNondet/Types/List.lhs +1/−1

@@ -1,5 +1,5 @@ Name:          cflp-Version:       0.2.1+Version:       0.2.2 Cabal-Version: >= 1.2 Synopsis:      Constraint Functional-Logic Programming in Haskell Description:   This package provides combinators for constraint@@ -32,7 +32,6 @@                     Data.LazyNondet.Matching,                     Data.LazyNondet.Narrowing,                     Data.LazyNondet.Primitive,-                    Data.LazyNondet.Combinators,                     Control.CFLP.Tests,                     Control.CFLP.Tests.CallTimeChoice   Hs-Source-Dirs:   src@@ -43,7 +42,7 @@                     PatternGuards,                     TypeFamilies,                     RankNTypes-  Ghc-Options:      -Wall -fno-warn-orphans+  Ghc-Options:      -Wall -fno-warn-orphans -fno-warn-name-shadowing  Source-Repository head   type:     git

@@ -115,4 +115,3 @@    * an `evalPrint` operation that interactively shows (partial)     solutions of a constraint functional-logic computation.-

@@ -30,7 +30,7 @@ > ignoreFirstNarrowSecond :: Assertion > ignoreFirstNarrowSecond = assertResults comp [True,False] >  where->   comp cs u = ignot (error "illegal demand") (unknown cs u) cs+>   comp cs u = ignot (error "illegal demand") (unknown u) cs > > ignot :: CFLP cs m >       => Nondet cs m a -> Nondet cs m Bool -> cs -> Nondet cs m Bool@@ -45,7 +45,7 @@ > sharedVarsAreEqual :: Assertion > sharedVarsAreEqual = assertResults comp [[False,False],[True,True]] >  where->   comp cs u = two (unknown cs u)+>   comp _ u = two (unknown u) > > two :: Monad m => Nondet cs m a -> Nondet cs m [a] > two x = x ^: x ^: nil@@ -71,7 +71,7 @@ > sharedCompoundTerms :: Assertion > sharedCompoundTerms = assertResults comp [[True,False],[False,True]] >  where->   comp cs u = negHeads (unknown cs u) cs+>   comp cs u = negHeads (unknown u) cs > > negHeads :: CFLP cs m => Nondet cs m [Bool] -> cs -> Nondet cs m [Bool] > negHeads l cs = not (head l cs) cs ^: head l cs ^: nil

@@ -10,9 +10,9 @@ > >   ID, initID, withUnique, >->   Narrow(..), NarrowPolicy(..), unknown, +>   Narrow(..), unknown,  >->   failure, oneOf,+>   failure, oneOf, (?), > >   withHNF, caseOf, caseOf_, Match, >@@ -28,4 +28,3 @@ > import Data.LazyNondet.Matching > import Data.LazyNondet.Narrowing > import Data.LazyNondet.Primitive-> import Data.LazyNondet.Combinators

@@ -1,77 +0,0 @@-% Combinators for Programs on Lazy Non-Deterministic Data-% Sebastian Fischer (sebf@informatik.uni-kiel.de)--> {-# LANGUAGE->       FlexibleContexts,->       FlexibleInstances,->       MultiParamTypeClasses,->       FunctionalDependencies->   #-}->-> module Data.LazyNondet.Combinators (->->   cons, failure, oneOf, ConsRep(..)->-> ) where->-> import Data.Data-> import Data.LazyNondet.Types->-> import Control.Monad-> import Control.Monad.Constraint-> import Control.Monad.Constraint.Choice->-> import UniqSupply->-> oneOf :: (MonadConstr Choice m, ChoiceStore cs)->       => [Nondet cs m a] -> cs -> ID -> Nondet cs m a-> oneOf xs cs (ID us) = Typed (choice cs (uniqFromSupply us) (map untyped xs))--The operation `oneOf` takes a list of non-deterministic values and-returns a non-deterministic value that yields one of the elements in-the given list.--> failure :: MonadPlus m => Nondet cs m a-> failure = Typed mzero--A failing computation could be defined using `oneOf`, but we provide a-special combinator that does not need a supply of unique identifiers.--> class MkCons cs m a b | b -> m, b -> cs->  where->   mkCons :: a -> [Untyped cs m] -> b->-> instance (Monad m, Data a) => MkCons cs m a (Nondet cs m t)->  where->   mkCons c args = Typed (return (mkHNF (toConstr c) (reverse args)))->-> instance MkCons cs m b c => MkCons cs m (a -> b) (Nondet cs m t -> c)->  where->   mkCons c xs x = mkCons (c undefined) (untyped x:xs)->-> cons :: MkCons cs m a b => a -> b-> cons c = mkCons c []--The overloaded operation `cons` takes a Haskell constructor and yields-a corresponding constructor function for non-deterministic values.--> class ConsRep a->  where->   consRep :: a -> Constr->-> instance ConsRep b => ConsRep (a -> b)->  where->   consRep c = consRep (c undefined)--We provide an overloaded operation `consRep` that yields a `Constr`-representation for a constructor rather than for a constructed value-like `Data.Data.toConstr` does. We do not provide the base instance--    instance Data a => ConsRep a-     where-      consRep = toConstr--because this would require to allow undecidable instances. As a-consequence, specialized base instances need to be defined for every-used datatype. See `Data.LazyNondet.List` for an example of how to get-the representation of polymorphic constructors and destructors.

@@ -6,18 +6,21 @@ >       TypeFamilies, >       FlexibleContexts, >       FlexibleInstances,+>       MultiParamTypeClasses,+>       FunctionalDependencies, >       ExistentialQuantification >   #-} > > module Data.LazyNondet.Matching ( >->   Match, match, withHNF, caseOf, caseOf_+>   Match, match, ConsRep(..), cons, >+>   withHNF, failure, caseOf, caseOf_+> > ) where > > import Data.Data > import Data.LazyNondet.Types-> import Data.LazyNondet.Combinators > > import Control.Monad.State > import Control.Monad.Constraint@@ -106,6 +109,11 @@ The operation `match` is used to build destructor functions for non-deterministic values that can be used with `caseOf`. +> failure :: MonadPlus m => Nondet cs m a+> failure = Typed mzero++Failure is just a type version of `mzero`.+ > caseOf :: (MonadSolve cs m m, MonadConstr Choice m) >        => Nondet cs m a -> [Match a cs m b] -> cs -> Nondet cs m b > caseOf x bs = caseOf_ x bs failure@@ -117,7 +125,9 @@ >   withHNF x $ \hnf cs -> >   case hnf of >     FreeVar _ y -> caseOf_ (Typed y) bs def cs->     Delayed res -> caseOf_ (Typed (res cs)) bs def cs+>     Delayed p res+>       | p cs      -> delayed p (\cs -> caseOf_ (Typed (res cs)) bs def cs)+>       | otherwise -> caseOf_ (Typed (res cs)) bs def cs >     Cons _ idx args -> >       maybe def (\b -> branch (b cs) args) (lookup idx (map unMatch bs)) >@@ -132,3 +142,41 @@ to be checked how big the slowdown of using `caseOf` is compared to using `withHNF` directly. +> class MkCons cs m a b | b -> m, b -> cs+>  where+>   mkCons :: a -> [Untyped cs m] -> b+>+> instance (Monad m, Data a) => MkCons cs m a (Nondet cs m t)+>  where+>   mkCons c args = Typed (return (mkHNF (toConstr c) (reverse args)))+>+> instance MkCons cs m b c => MkCons cs m (a -> b) (Nondet cs m t -> c)+>  where+>   mkCons c xs x = mkCons (c undefined) (untyped x:xs)+>+> cons :: MkCons cs m a b => a -> b+> cons c = mkCons c []++The overloaded operation `cons` takes a Haskell constructor and yields+a corresponding constructor function for non-deterministic values.++> class ConsRep a+>  where+>   consRep :: a -> Constr+>+> instance ConsRep b => ConsRep (a -> b)+>  where+>   consRep c = consRep (c undefined)++We provide an overloaded operation `consRep` that yields a `Constr`+representation for a constructor rather than for a constructed value+like `Data.Data.toConstr` does. We do not provide the base instance++    instance Data a => ConsRep a+     where+      consRep = toConstr++because this would require to allow undecidable instances. As a+consequence, specialized base instances need to be defined for every+used datatype. See `Data.LazyNondet.List` for an example of how to get+the representation of polymorphic constructors and destructors.

@@ -8,26 +8,29 @@ > > module Data.LazyNondet.Narrowing ( >->   unknown, Narrow(..), NarrowPolicy(..)+>   unknown, Narrow(..), oneOf, (?) > > ) where >+> import Data.Maybe > import Data.LazyNondet.Types > > import Control.Monad.Constraint > import Control.Monad.Constraint.Choice >-> unknown :: (MonadConstr Choice m, Narrow cs a) => cs -> ID -> Nondet cs m a-> unknown cs u = freeVar u (narrowWithPolicy cs u)+> import UniqSupply+>+> unknown :: (MonadConstr Choice m, Narrow cs a) => ID -> Nondet cs m a+> unknown u = freeVar u (delayed (redelay u) (\cs -> narrow cs u))+>+> redelay :: ChoiceStore cs => ID -> cs -> Bool+> redelay (ID us) = isNothing . lookupChoice (uniqFromSupply us)  The application of `unknown` to a constraint store and a unique identifier represents a logic variable of an arbitrary type.   > class ChoiceStore cs => Narrow cs a >  where->   narrowPolicy :: NarrowPolicy cs a->   narrowPolicy = OnDemand-> >   narrow :: MonadConstr Choice m => cs -> ID -> Nondet cs m a  Logic variables of type `a` can be narrowed to head-normal form if@@ -37,35 +40,20 @@ non-deterministic generator using `oneOf`, but for specific types different strategies may be implemented. -The default policy is to narrow on demand in order to avoid-unnessesary choices in shared free variables that can lead to-exponential explosion of the search space.--A `NarrowPolicy` specifies whether a logic variable should be-- * narrowed whenever it is demanded according the current constraint-   store or-- * narrowed only on creation and shared on every demand.--> data NarrowPolicy cs a = OnDemand | OnCreation+> (?) :: (MonadConstr Choice m, ChoiceStore cs)+>     => Nondet cs m a -> Nondet cs m a -> ID -> Nondet cs m a+> (x ? y) u = delayed (redelay u) (\cs -> oneOf [x,y] cs u) -Using `OnDemand` can avoid unnessesary branching when accessing a-variable with an updated constraint store. Using `OnCreation` will-avoid the reexecution of a non-deterministic generator.+The operator `(?)` wraps the combinator `oneOf` to generate a delayed+non-deterministic choice that is executed whenever it is+demanded. Although the choice itself is reexecuted according to the+current constraint store, the arguments of `(?)` are shared among all+executions and *not* reexecuted. -> narrowWithPolicy :: (MonadConstr Choice m, Narrow cs a)->                  => cs -> ID -> Nondet cs m a-> narrowWithPolicy cs u = x->  where->   x = case policy x of->         OnDemand   -> delayed (`narrow`u)->         OnCreation -> narrow cs u->-> policy :: Narrow cs a => Nondet cs m a -> NarrowPolicy cs a-> policy _ = narrowPolicy+> oneOf :: (MonadConstr Choice m, ChoiceStore cs)+>       => [Nondet cs m a] -> cs -> ID -> Nondet cs m a+> oneOf xs cs (ID us) = Typed (choice cs (uniqFromSupply us) (map untyped xs)) -The function `narrowWithPolicy` narrows a logic variable or creates a-delayed execution that will be performed whenever the variable is-demanded. The definition uses a helper function in order to constrain-the type of the narrowing policy.+The operation `oneOf` takes a list of non-deterministic values and+returns a non-deterministic value that yields one of the elements in+the given list.

@@ -92,13 +92,13 @@ >     FreeVar u@(ID us) y -> >       get >>= maybe (return (fv u y)) (const (nf lkp cns fv y)) >             . lkp (uniqFromSupply us)->     Delayed resume -> get >>= nf lkp cns fv . resume+>     Delayed _ resume -> get >>= nf lkp cns fv . resume >     Cons typ idx args -> do >       nfs <- mapM (nf lkp cns fv) args >       return (cns (indexConstr typ idx) nfs) -The `nf` function is used by all normal-form functions and performs al-the work.+The `nf` function is used by all normal-form functions and performs+all the work.  > prim_eq :: MonadSolve cs m m >         => Untyped cs m -> Untyped cs m -> StateT cs m Bool@@ -115,7 +115,7 @@  We provide a generic comparison function for untyped non-deterministic data that is used to define a typed equality test in the-`Data.LazyNondet.Bool` module.+`Data.LazyNondet.Types.Bool` module.  > solveCons :: MonadSolve cs m m >           => Untyped cs m -> StateT cs m (HeadNormalForm cs m)@@ -123,7 +123,7 @@ >   hnf <- solve x >   case hnf of >     FreeVar _ y -> solveCons y->     Delayed res -> get >>= solveCons . res+>     Delayed _ res -> get >>= solveCons . res >     _ -> return hnf  The function `solveCons` is like `solve` but always yields a

@@ -37,7 +37,7 @@ > data HeadNormalForm cs m >   = Cons DataType ConIndex [Untyped cs m] >   | FreeVar ID (Untyped cs m)->   | Delayed (cs -> Untyped cs m)+>   | Delayed (cs -> Bool) (cs -> Untyped cs m) > > type Untyped cs m = m (HeadNormalForm cs m) @@ -59,7 +59,7 @@ representation of the data type and the index of the constructor, to enable pattern matching on the index. -Free (logic) variables are represented by `Unknown u x` where `u` is a+Free (logic) variables are represented by `FreeVar u x` where `u` is a uniqe identifier and `x` represents the result of narrowing the variable according to the constraint store passed to the operation that creates the variable.@@ -70,21 +70,25 @@ The function `freeVar` is used to put a name around a narrowed free variable. -> delayed :: Monad m => (cs -> Nondet cs m a) -> Nondet cs m a-> delayed resume = Typed . return . Delayed $ (untyped . resume)+> delayed :: Monad m => (cs -> Bool) -> (cs -> Nondet cs m a) -> Nondet cs m a+> delayed p resume = Typed . return . Delayed p $ (untyped . resume)  With `delayed` computations can be delayed to be reexecuted with the current constraint store whenever they are demanded. This is useful to avoid unessary branching when narrowing logic variables. Use with care: `delayed` intentionally destroys sharing! +The first parameter is a predicate on constraint stores that specifies+whether the result of pattern matching the constructed delayed value+should be delayed again.+ `Show` Instances ----------------  > instance Show (HeadNormalForm cs []) >  where >   show (FreeVar (ID u) _) = show (uniqFromSupply u)->   show (Delayed _) = "<delayed>"+>   show (Delayed _ _) = "<delayed>" >   show (Cons typ idx args)  >     | null args = show con >     | otherwise = unwords (("("++show con):map show args++[")"])@@ -101,7 +105,7 @@ > instance Show (HeadNormalForm cs (ConstrT cs [])) >  where >   show (FreeVar (ID u) _)  = show (uniqFromSupply u)->   show (Delayed _)         = "<delayed>"+>   show (Delayed _ _)         = "<delayed>" >   show (Cons typ idx [])   = show (indexConstr typ idx) >   show (Cons typ idx args) = >     "("++show (indexConstr typ idx)++" "++unwords (map show args)++")" 

@@ -43,7 +43,7 @@ > instance (ChoiceStore cs, Narrow cs a) => Narrow cs [a] >  where >   narrow cs = withUnique $ \u1 u2 -> ->                 oneOf [nil, unknown cs u1 ^: unknown cs u2] cs+>                 oneOf [nil, unknown u1 ^: unknown u2] cs  Some operations on lists: