operational 0.2.1.1 → 0.2.1.2

raw patch · 4 files changed

+111/−16 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• doc/examples/BreadthFirstParsing.hs +78/−0
• doc/examples/PoorMansConcurrency.hs +5/−5
• operational.cabal +1/−1
• src/Control/Monad/Operational.hs +27/−10

@@ -0,0 +1,78 @@+{------------------------------------------------------------------------------+    Control.Monad.Operational+    +    Example:+    A reformulation of Koen Claessen's Parallel Parsing Processes+    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.9217++    For a detailed explanation, see also+    http://apfelmus.nfshost.com/articles/operational-monad.html#monadic-parser-combinators+------------------------------------------------------------------------------}+{-# LANGUAGE GADTs, Rank2Types, TypeSynonymInstances #-}+module BreadthFirstParsing where++import Control.Monad+import Control.Monad.Operational++{------------------------------------------------------------------------------+    At their core, a parser monad consists of just three+    primitive instructions+    +        symbol -- fetch the next character+        mzero  -- indicate parse failure+        mplus  -- non-deterministic choice between two parsers+    +    and an interpreter function+        +        parse :: Parser a -> (String -> [a])+    +    that applies a parser to a string and returns+    all the possible parse results.+------------------------------------------------------------------------------}+data ParserInstruction a where+    Symbol :: ParserInstruction Char+    MZero  :: ParserInstruction a+    MPlus  :: Parser a -> Parser a -> ParserInstruction a++type Parser = Program ParserInstruction++symbol = singleton Symbol++instance MonadPlus Parser where+    mzero     = singleton $ MZero+    mplus x y = singleton $ MPlus x y++-- apply a parser to a string+-- breadth first fashion: each input character is touched only once+parse :: Parser a -> String -> [a]+parse p = go (expand p)+    where+    go :: [Parser a] -> String -> [a]+    go ps []     = [a | Return a <- map view ps]+    go ps (c:cs) = go [p | (Symbol :>>= is) <- map view ps, p <- expand (is c)] cs++-- keep track of parsers that are run in parallel+expand :: Parser a -> [Parser a]+expand p = case view p of+    MPlus p q :>>= k  -> expand (p >>= k) ++ expand (q >>= k)+    MZero     :>>= k  -> []+    _                 -> [p]+++-- example+-- > parse parens "()(()())"+-- [()]     -- one parse+-- > parse parens "()((())"+-- []       -- no parse+parens :: Parser ()+parens = return () `mplus` (enclose parens >> parens)+    where+    enclose q = char '(' >> q >> char ')'++many :: Parser a -> Parser [a]+many p = mzero `mplus` liftM2 (:) p (many p) ++satisfy :: (Char -> Bool) -> Parser Char+satisfy p = do c <- symbol; if p c then return c else mzero++char c = satisfy (==c)

@@ -3,7 +3,7 @@          Example:     Koen Claessen's Poor Man's Concurrency Monad-    http://www.cs.chalmers.se/~koen/pubs/entry-jfp99-monad.html+    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039  ------------------------------------------------------------------------------} {-# LANGUAGE GADTs, Rank2Types #-}@@ -15,7 +15,7 @@  {------------------------------------------------------------------------------     A concurrency monad runs several processes in parallel-    and supports two operations+    and supports two primitive operations          fork  -- fork a new process         stop  -- halt the current one@@ -37,7 +37,7 @@ fork = singleton . Fork lift = singleton . Lift -    -- interpreter+-- interpreter runProcess :: Monad m => Process m a -> m () runProcess m = schedule [m]     where@@ -51,8 +51,8 @@     run (Fork p :>>= k) xs = schedule (xs ++ [x2,x1])  -- fork new process         where x1 = k (); x2 = p >>= k -    -- example-    --      > runProcess example   -- warning: runs indefinitely+-- example+--      > runProcess example   -- warning: runs indefinitely example :: Process IO () example = do         write "Start!"

@@ -1,5 +1,5 @@ Name:               operational-Version:            0.2.1.1+Version:            0.2.1.2 Synopsis:           Implementation of difficult monads made easy                     with operational semantics. Description:

@@ -13,8 +13,9 @@     -- $example          -- * Monad transformer-    ProgramT, ProgramViewT(..), viewT, liftProgram+    ProgramT, ProgramViewT(..), viewT,     -- $exampleT+    liftProgram,          ) where @@ -82,20 +83,26 @@ @ runCustomMonad :: CustomMonad a -> IO a runCustomMonad m = case view m of-    Return a            -> ...  -- done, return a result-    AskUserInput :>>= k -> ...  -- askUserInput instruction, continue with k+    Return a            -> return a -- done, return the result+    AskUserInput :>>= k -> do+        b <- waitForUserInput       -- wait for external user input+        runCustomMonad (k b)        -- proceed with next instruction @  The point is that you can now proceed in any way you like:-you can wait for the user to return input,+you can wait for the user to return input as shown, or you store the continuation @k@ and retrieve it when your web application receives another HTTP request, or you can keep a log of all user inputs on the client side an replay them,-and so on.+and so on. Moreover, you can implement different @run@ functions+for one and the same custom monad, which is useful for testing.+Also not that the result of the @run@ function does not need to be a monad at all.+ In essence, your custom monad allows you to express your web application as a simple imperative program,-while the underlying implementation maps this to-an event-drived model or some other control flow architecture.+while the underlying implementation can freely map this to+an event-drived model or some other control flow architecture+of your choice.  The possibilities are endless. More usage examples can be found here:@@ -141,6 +148,7 @@  @     type StackProgram a = Program StackInstruction a+    type Stack b        = [b] @  @@@ -199,9 +207,18 @@ singleton = Instr  -- | View type for inspecting the first instruction.+-- This is very similar to pattern matching on lists.+--+-- * The case @(Return a)@ means that the program contains no instructions+-- and just returns the result @a@.+--+-- *The case @(someInstruction :>>= k)@ means that the first instruction+-- is @someInstruction@ and the remaining program is given by the function @k@. data ProgramViewT instr m a where     Return :: a -> ProgramViewT instr m a-    (:>>=) :: instr b -> (b -> ProgramT instr m a ) -> ProgramViewT instr m a+    (:>>=) :: instr b+           -> (b -> ProgramT instr m a)+           -> ProgramViewT instr m a  -- | View function for inspecting the first instruction. viewT :: Monad m => ProgramT instr m a -> m (ProgramViewT instr m a)@@ -243,11 +260,11 @@         Plus :: ListT m a -> ListT m a -> PlusI m a @ -@   +@     type ListT m a = ProgramT (PlusI m) m a @ -@   +@     runList :: Monad m => ListT m a -> m [a]     runList = eval <=< viewT         where