% Randomization for CFL Computations
% Sebastian Fischer (sebf@informatik.unikiel.de)
This module provides a strategy transformer that randomly reorders
choices in the search space.
>
>
> module CFLP.Strategies.Random (
>
> Randomiser(..), Rnd, RndCtx, randomise
>
> ) where
>
> import Control.Monad
> import Control.Monad.Random
>
> import CFLP.Control.Monad.Update
>
> import CFLP.Control.Strategy
The interface of an evaluation context that can reorder choices
randomly is given by the following type class.
> class Randomiser c
> where
> getRandomGen :: c -> StdGen
> setRandomGen :: c -> StdGen -> c -> c
The first argument of `setRandomGen` will always be ignored and is
only used to support the type checker.
We define uniform liftings for randomisers over arbitrary context
transformers.
> instance (Randomiser c, Transformer t) => Randomiser (t c)
> where
> getRandomGen = getRandomGen . project
>
> setRandomGen _ r c = replace c (setRandomGen undefined r (project c))
A random context adds a counter for the depth.
> data RndCtx c = RndCtx StdGen c
It is an instance of `Randomiser`.
> instance Randomiser (RndCtx c)
> where
> getRandomGen (RndCtx r _) = r
> setRandomGen _ r (RndCtx _ c) = RndCtx r c
It also is a transformer for evaluation contexts
> instance Transformer RndCtx
> where
> project (RndCtx _ c) = c
> replace (RndCtx d _) = RndCtx d
We define a strategy transformer for depth counting.
> newtype Rnd s a = Rnd { fromRnd :: s a }
> deriving (Monad, MonadPlus, Enumerable)
>
> type instance Ctx (Rnd s) = RndCtx (Ctx s)
> type instance Res (Rnd s) = Rnd (Res s)
The strategytransformer instance shuffles each nondeterministic
choice.
> instance Randomiser c => StrategyT c Rnd
> where
> liftStrategy _ = Rnd
> baseStrategy _ = fromRnd
>
> extendChoices c _ xs =
> evalRand (shuffle xs >>= mapM (setRndGen c)) (getRandomGen c)
>
> shuffle :: MonadRandom rnd => [a] -> rnd [a]
> shuffle xs = shuffleWithLen (length xs) xs
>
> shuffleWithLen :: MonadRandom rnd => Int -> [a] -> rnd [a]
> shuffleWithLen 0 _ = return []
> shuffleWithLen len xs = do
> let len_1 = len1
> n <- getRandomR (0,len_1)
> let (ys,z:zs) = splitAt n xs
> liftM (z:) (shuffleWithLen len_1 (ys++zs))
>
> setRndGen :: (Randomiser c, Monad m, MonadUpdate c m)
> => c -> m a -> Rand StdGen (m a)
> setRndGen c x = do
> r <- getSplit
> return (update (return . setRandomGen c r) >> x)
The operation `random` adds randomisation to a strategy.
> randomise :: Monad s => s c -> Rnd s (RndCtx c)
> randomise = Rnd . liftM (RndCtx (mkStdGen 42))