cflp 2009.1.23.1 → 2009.1.23.2

raw patch · 3 files changed

+193/−1 lines, 3 files

Files

• cflp.cabal +3/−1
• src/CFLP/Strategies/DepthCounter.lhs +88/−0
• src/CFLP/Strategies/DepthLimit.lhs +102/−0

@@ -1,5 +1,5 @@ Name:          cflp-Version:       2009.1.23.1+Version:       2009.1.23.2 Cabal-Version: >= 1.6 Synopsis:      Constraint Functional-Logic Programming in Haskell Description:   This package provides combinators for constraint@@ -30,7 +30,9 @@   Exposed-Modules:  CFLP                     CFLP.Strategies                     CFLP.Strategies.CallTimeChoice+                    CFLP.Strategies.DepthCounter                     CFLP.Strategies.DepthFirst+                    CFLP.Strategies.DepthLimit                     CFLP.Tests                     CFLP.Tests.CallTimeChoice                     CFLP.Tests.HigherOrder

@@ -0,0 +1,88 @@+% Depth Monitoring for Non-Deterministic Computations.+% Sebastian Fischer (sebf@informatik.uni-kiel.de)++This module provides a strategy transformer that extends the+evaluation context with a counter for the search depth.++> {-# LANGUAGE+>       GeneralizedNewtypeDeriving,+>       MultiParamTypeClasses,+>       OverlappingInstances,+>       FlexibleInstances,+>       TypeFamilies+>   #-}+>+> module CFLP.Strategies.DepthCounter (+>+>   DepthCounter(..), Depth, DepthCtx, countDepth+>+>  ) where+>+> import Control.Monad+>+> import CFLP.Control.Monad.Update+>+> import CFLP.Control.Strategy++The interface of an evaluation context that can store a depth counter+is given by the following type class.++> class DepthCounter c+>  where+>   currentDepth   :: c -> Int+>   incrementDepth :: c -> c -> c++The first argument of `incrementDepth` will always be ignored and is+only used to support the type checker.++We define uniform liftings for depth counters over arbitrary context+transformers.++> instance (DepthCounter c, Transformer t) => DepthCounter (t c)+>  where+>   currentDepth = currentDepth . project+>+>   incrementDepth _ c = replace c (incrementDepth undefined (project c))++A depth context adds a counter for the depth.++> data DepthCtx c = DepthCtx Int c++It is an instance of `DepthCounter`.++> instance DepthCounter (DepthCtx c)+>  where+>   currentDepth     (DepthCtx d _) = d+>   incrementDepth _ (DepthCtx d c) = DepthCtx (d+1) c++It also is a transformer for evaluation contexts++> instance Transformer DepthCtx+>  where+>   project (DepthCtx _ c) = c+>   replace (DepthCtx d _) = DepthCtx d++We define a strategy transformer for depth counting.++> newtype Depth s a = Depth { fromDepth :: s a }+>  deriving (Monad, MonadPlus, Enumerable)+>+> type instance Ctx (Depth s) = DepthCtx (Ctx s)+> type instance Res (Depth s) = Depth (Res s)++The operation `countDepth` the `Depth` constructor.++> countDepth :: s a -> Depth s a+> countDepth = Depth++The strategy-transformer instance increments the counter at each+non-deterministic choice.++> instance DepthCounter c => StrategyT c Depth+>  where+>   liftStrategy _ = Depth+>   baseStrategy _ = fromDepth+>+>   extendContext _ = DepthCtx 0+>+>   extendChoices c _ = map (update (return . incrementDepth c)>>)

@@ -0,0 +1,102 @@+% Depth Limiting for Non-Deterministic Computations.+% Sebastian Fischer (sebf@informatik.uni-kiel.de)++This module provides a strategy transformer that extends the+evaluation context with a limit for the search depth.++> {-# LANGUAGE+>       GeneralizedNewtypeDeriving,+>       MultiParamTypeClasses,+>       OverlappingInstances,+>       FlexibleInstances,+>       TypeFamilies+>   #-}+>+> module CFLP.Strategies.DepthLimit (+>+>   DepthLimiter(..), DepthLim, DepthLimCtx, limitDepth, setDepthLimit+>+>  ) where+>+> import Control.Monad+>+> import CFLP.Control.Monad.Update+>+> import CFLP.Control.Strategy+>+> import CFLP.Strategies.DepthCounter++The interface of an evaluation context that can store a depth limit+is given by the following type class.++> class DepthLimiter c+>  where+>   depthLimit      :: c -> Int+>   resetDepthLimit :: c -> Int -> c -> c++We define uniform liftings for depth limiters over arbitrary context+transformers.++> instance (DepthLimiter c, Transformer t) => DepthLimiter (t c)+>  where+>   depthLimit = depthLimit . project+>+>   resetDepthLimit _ l c = replace c (resetDepthLimit undefined l (project c))++The default limit is 100, but you can use the operation+`setDepthLimit` in computations to change it.++> defaultLimit :: Int+> defaultLimit = 100+>+> setDepthLimit :: (Monad s, DepthLimiter c, MonadUpdate c s)+>               => c -> Int -> s ()+> setDepthLimit c l = update (return . resetDepthLimit c l)++A depth limiting context adds a depth limit to the evaluation context.++> data DepthLimCtx c = DepthLimCtx Int c++It is an instance of `DepthLimiter`.++> instance DepthLimiter (DepthLimCtx c)+>  where+>   depthLimit (DepthLimCtx l _) = l+>+>   resetDepthLimit _ l (DepthLimCtx _ c) = DepthLimCtx l c++It also is a transformer for evaluation contexts++> instance Transformer DepthLimCtx+>  where+>   project (DepthLimCtx _ c) = c+>   replace (DepthLimCtx l _) = DepthLimCtx l++We define a strategy transformer for depth limiting.++> newtype DepthLim s a = DepthLim { fromDepthLim :: s a }+>  deriving (Monad, MonadPlus, Enumerable)+>+> type instance Ctx (DepthLim s) = DepthLimCtx (Ctx s)+> type instance Res (DepthLim s) = DepthLim (Res s)++The operation `depthCounter` the `Depth` constructor.++> limitDepth :: s a -> DepthLim s a+> limitDepth = DepthLim++The strategy-transformer instance increments the counter at each+non-deterministic choice and prunes the choices if the limit is+exceeded.++> instance (DepthCounter c, DepthLimiter c) => StrategyT c DepthLim+>  where+>   liftStrategy _ = DepthLim+>   baseStrategy _ = fromDepthLim+>+>   extendContext _ = DepthLimCtx defaultLimit+>+>   extendChoices c _ xs+>     | currentDepth c < depthLimit c+>       = map (update (return . incrementDepth c)>>) xs+>     | otherwise = []