Difference between revisions of "MonadSplit"
Jump to navigation
Jump to search
(MonadSplit) |
(renamed) |
||
| Line 1: | Line 1: | ||
| + | Moved to [[New monads/MonadSplit]]. |
||
| − | [[ Category:Code ]] |
||
| − | |||
| − | <haskell> |
||
| − | > module Control.Monad.MonadSplit where |
||
| − | > import Control.Monad |
||
| − | > import qualified Data.Sequence as S |
||
| − | |||
| − | MonadSplit, in a sense, represents the class of monads which have both |
||
| − | "mplus" and a new decomposition operator: "msplit" such that |
||
| − | |||
| − | l == (msplit l >>= \(x,xs) -> return x `mplus` xs) |
||
| − | |||
| − | > class MonadPlus m => MonadSplit m where |
||
| − | > msplit :: m a -> m (a, m a) |
||
| − | > miszero :: m a -> Bool |
||
| − | |||
| − | > instance MonadSplit [] where |
||
| − | > msplit [] = mzero |
||
| − | > msplit (x:xs) = return (x,xs) |
||
| − | > miszero = null |
||
| − | |||
| − | > instance MonadSplit Maybe where |
||
| − | > msplit Nothing = mzero |
||
| − | > msplit (Just x) = return (x, Nothing) |
||
| − | > miszero Nothing = True |
||
| − | > miszero (Just _) = False |
||
| − | |||
| − | This class allows us to implement several functions which were |
||
| − | previously implemented over lists only. |
||
| − | |||
| − | > foldMSl :: (MonadSplit m) => (a -> b -> m a) -> a -> m b -> m a |
||
| − | > foldMSl m i n | miszero n = return i |
||
| − | > | otherwise = do |
||
| − | > (x,xs) <- msplit n |
||
| − | > i' <- m i x |
||
| − | > foldMSl m i' xs |
||
| − | |||
| − | > foldMSr :: (MonadSplit m) => (a -> b -> m b) -> b -> m a -> m b |
||
| − | > foldMSr m i n | miszero n = return i |
||
| − | > | otherwise = do |
||
| − | > (x,xs) <- msplit n |
||
| − | > i' <- foldMSr m i xs |
||
| − | > m x i' |
||
| − | |||
| − | > scanMSl :: (MonadSplit m) => (a -> b -> m a) -> a -> m b -> m (m a) |
||
| − | > scanMSl m i n | miszero n = return (return i) |
||
| − | > | otherwise = do |
||
| − | > (x,xs) <- msplit n |
||
| − | > i' <- m i x |
||
| − | > return (return i) `mplus` scanMSl m i' xs |
||
| − | |||
| − | > scanMSr :: (MonadSplit m) => (a -> b -> m b) -> b -> m a -> m (m b) |
||
| − | > scanMSr m i n | miszero n = return (return i) |
||
| − | > | otherwise = do |
||
| − | > (x,xs) <- msplit n |
||
| − | > i' <- scanMSr m i xs |
||
| − | > (return . m x =<< i') `mplus` return i' |
||
| − | |||
| − | > initsM :: (MonadSplit m) => m a -> m (m a) |
||
| − | > initsM m | miszero m = return mzero |
||
| − | > | otherwise = return mzero `mplus` do |
||
| − | > (x,xs) <- msplit m |
||
| − | > a <- initsM xs |
||
| − | > return $ return x `mplus` a |
||
| − | |||
| − | > tailsM :: (MonadSplit m) => m a -> m (m a) |
||
| − | > tailsM m | miszero m = return mzero |
||
| − | > | otherwise = msplit m >>= \(x,xs) -> return m `mplus` tailsM xs |
||
| − | |||
| − | With cuts l = zip (inits l) (tails l), cutsM is the equivalent for MonadSplit. |
||
| − | |||
| − | > cutsM :: (MonadSplit m) => m a -> m (m a, m a) |
||
| − | > cutsM m | miszero m = return (mzero, mzero) |
||
| − | > | otherwise = return (mzero, m) `mplus` do |
||
| − | > (x,xs) <- msplit m |
||
| − | > (a,b) <- cutsM xs |
||
| − | > return $ (return x `mplus` a, b) |
||
| − | |||
| − | > insertM :: (MonadSplit m) => a -> m a -> m (m a) |
||
| − | > insertM i m = do |
||
| − | > (a,b) <- cutsM m |
||
| − | > return $ a `mplus` return i `mplus` b |
||
| − | |||
| − | > permuteM :: (MonadSplit m) => m a -> m (m a) |
||
| − | > permuteM m | miszero m = return mzero |
||
| − | > | otherwise = do |
||
| − | > (x,xs) <- msplit m |
||
| − | > xs' <- permuteM xs |
||
| − | > insertM x xs' |
||
| − | |||
| − | As it happens, permuteM can be expressed with foldMSr. |
||
| − | |||
| − | > permuteM2 :: (MonadSplit m) => m b -> m (m b) |
||
| − | > permuteM2 m = foldMSr insertM mzero m |
||
| − | |||
| − | permuteWithDel means to permute the list and all sublists. |
||
| − | |||
| − | > permuteWithDelM m | miszero m = return mzero |
||
| − | > | otherwise = do |
||
| − | > (x,xs) <- msplit m |
||
| − | > xs' <- permuteWithDelM xs |
||
| − | > insertM x xs' `mplus` return xs' |
||
| − | |||
| − | > permuteWithDelM2 m = foldMSr (\x xs -> insertM x xs `mplus` return xs) mzero m |
||
| − | |||
| − | An example instance for another datatype. |
||
| − | |||
| − | > instance MonadSplit S.Seq where |
||
| − | > miszero = S.null |
||
| − | > msplit s = case S.viewl s of |
||
| − | > S.EmptyL -> return (undefined, |
||
| − | > fail "msplit used on empty sequence") |
||
| − | > x S.:< xs -> return (x, xs) |
||
| − | |||
| − | A "generalized" searching function: |
||
| − | |||
| − | g is "generator", a function which accepts the current search space, an |
||
| − | element of input, and produces a new search space. |
||
| − | |||
| − | t is "tester", a function which evaluates generated solutions |
||
| − | |||
| − | and finally, i is "input". |
||
| − | |||
| − | > search :: (MonadSplit s, MonadPlus p) => |
||
| − | > (b -> p a -> s (p a)) -> (p a -> Bool) -> s b -> s (p a) |
||
| − | > search g t i = (foldMSr g mzero i) >>= (\x -> guard (t x) >> return x) |
||
| − | |||
| − | > test1 = search insertM (all (<4)) |
||
| − | |||
| − | test1 [1..2] => [[1,2],[2,1]] |
||
| − | test1 [1..4] => [] |
||
| − | |||
| − | > test2 = search (\x xs -> insertM x xs `mplus` return xs) (all (<4)) |
||
| − | |||
| − | test2 [1..4] => [[1,2,3],[2,1,3],[2,3,1],[2,3],[1,3,2],[3,1,2],[3,2,1], |
||
| − | [3,2],[1,3],[3,1],[3],[1,2],[2,1],[2],[1],[]] |
||
| − | |||
| − | </haskell> |
||
Revision as of 00:03, 17 December 2006
Moved to New monads/MonadSplit.