Ticket #1169: Cont.hs

File Cont.hs, 8.9 KB (added by Andriy, 8 years ago)

Version 3 of the module source. Minor improvements.

Line 
1{-# OPTIONS -fallow-undecidable-instances #-}
2-- Search for -fallow-undecidable-instances to see why this is needed
3
4{- |
5Module      :  Control.Monad.Cont
6Copyright   :  (c) The University of Glasgow 2001,
7               (c) Jeff Newbern 2003-2007,
8               (c) Andriy Palamarchuk 2007
9License     :  BSD-style (see the file libraries/base/LICENSE)
10
11Maintainer  :  [email protected]
12Stability   :  experimental
13Portability :  non-portable (multi-parameter type classes)
14
15[Computation type:] Computations which can be interrupted and resumed.
16
17[Binding strategy:] Binding a function to a monadic value creates
18a new continuation which uses the function as the continuation of the monadic
19computation.
20
21[Useful for:] Complex control structures, error handling,
22and creating co-routines.
23
24[Zero and plus:] None.
25
26[Example type:] @'Cont' r a@
27
28The Continuation monad represents computations in continuation-passing style
29(CPS).
30In continuation-passing style function result is not returned,
31but instead is passed to another function,
32received as a parameter (continuation).
33Computations are built up from sequences
34of nested continuations, terminated by a final continuation (often @id@)
35which produces the final result.
36Since continuations are functions which represent the future of a computation,
37manipulation of the continuation functions can achieve complex manipulations
38of the future of the computation,
39such as interrupting a computation in the middle, aborting a portion
40of a computation, restarting a computation, and interleaving execution of
41computations.
42The Continuation monad adapts CPS to the structure of a monad.
43
44Before using the Continuation monad, be sure that you have
45a firm understanding of continuation-passing style
46and that continuations represent the best solution to your particular
47design problem.
48Many algorithms which require continuations in other languages do not require
49them in Haskell, due to Haskell's lazy semantics.
50Abuse of the Continuation monad can produce code that is impossible
51to understand and maintain.
52-}
53
54module Control.Monad.Cont (
55        MonadCont(..),
56        Cont(..),
57        mapCont,
58        withCont,
59        ContT(..),
60        mapContT,
61        withContT,
62        module Control.Monad,
63        module Control.Monad.Trans
64    -- * Example 1: Simple Continuation Usage
65    -- $simpleContExample
66
67    -- * Example 2: Using @callCC@
68    -- $callCCExample
69   
70    -- * Example 3: Using @ContT@ Monad Transformer
71    -- $ContTExample
72  ) where
73
74import Control.Monad
75import Control.Monad.Trans
76import Control.Monad.RWS
77
78class (Monad m) => MonadCont m where
79  {- | @callCC@ (call-with-current-continuation)
80  calls a function with the current continuation as its argument.
81  Provides an escape continuation mechanism for use with Continuation monads.
82  Escape continuations allow to abort the current computation and return
83  a value immediately.
84  They achieve a similar effect to 'Control.Monad.Error.throwError'
85  and 'Control.Monad.Error.catchError'
86  within an 'Control.Monad.Error.Error' monad.
87  Advantage of this function over calling @return@ is that it makes
88  the continuation explicit,
89  allowing more flexibility and better control (see the examples).
90
91  The standard idiom used with @callCC@ is to provide a lambda-expression
92  to name the continuation. Then calling the named continuation anywhere
93  within its scope will escape from the computation,
94  even if it is many layers deep within nested computations.
95  -}
96        callCC :: ((a -> m b) -> m a) -> m a
97
98{- |
99Continuation monad.
100@Cont r a@ is a CPS computation that produces an intermediate result
101of type @a@ within a CPS computation whose final result type is @r@.
102
103The @return@ function simply creates a continuation which passes the value on.
104
105The @>>=@ operator adds the bound function into the continuation chain.
106-}
107newtype Cont r a = Cont {
108
109  {- | Runs a CPS computation, returns its result after applying
110  the final continuation to it.
111  Parameters:
112
113  * a continuation computation (@Cont@).
114 
115  * the final continuation, which produces the final result (often @id@).
116  -}
117  runCont :: (a -> r) -> r
118}
119
120instance Functor (Cont r) where
121        fmap f m = Cont $ \c -> runCont m (c . f)
122
123instance Monad (Cont r) where
124        return a = Cont ($ a)
125        m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c
126
127instance MonadCont (Cont r) where
128        callCC f = Cont $ \c -> runCont (f (\a -> Cont $ \_ -> c a)) c
129
130mapCont :: (r -> r) -> Cont r a -> Cont r a
131mapCont f m = Cont $ f . runCont m
132
133withCont :: ((b -> r) -> (a -> r)) -> Cont r a -> Cont r b
134withCont f m = Cont $ runCont m . f
135
136{- |
137The continuation monad transformer.
138It can be used to add continuation handling to other monads.
139-}
140newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }
141
142instance (Monad m) => Functor (ContT r m) where
143        fmap f m = ContT $ \c -> runContT m (c . f)
144
145instance (Monad m) => Monad (ContT r m) where
146        return a = ContT ($ a)
147        m >>= k  = ContT $ \c -> runContT m (\a -> runContT (k a) c)
148
149instance (Monad m) => MonadCont (ContT r m) where
150        callCC f = ContT $ \c -> runContT (f (\a -> ContT $ \_ -> c a)) c
151
152instance MonadTrans (ContT r) where
153        lift m = ContT (m >>=)
154
155instance (MonadIO m) => MonadIO (ContT r m) where
156        liftIO = lift . liftIO
157
158-- Needs -fallow-undecidable-instances
159instance (MonadReader r' m) => MonadReader r' (ContT r m) where
160        ask       = lift ask
161        local f m = ContT $ \c -> do
162                r <- ask
163                local f (runContT m (local (const r) . c))
164
165-- Needs -fallow-undecidable-instances
166instance (MonadState s m) => MonadState s (ContT r m) where
167        get = lift get
168        put = lift . put
169
170-- -----------------------------------------------------------------------------
171-- MonadCont instances for other monad transformers
172
173instance (MonadCont m) => MonadCont (ReaderT r m) where
174        callCC f = ReaderT $ \r ->
175                callCC $ \c ->
176                runReaderT (f (\a -> ReaderT $ \_ -> c a)) r
177
178instance (MonadCont m) => MonadCont (StateT s m) where
179        callCC f = StateT $ \s ->
180                callCC $ \c ->
181                runStateT (f (\a -> StateT $ \s' -> c (a, s'))) s
182
183instance (Monoid w, MonadCont m) => MonadCont (WriterT w m) where
184        callCC f = WriterT $
185                callCC $ \c ->
186                runWriterT (f (\a -> WriterT $ c (a, mempty)))
187
188instance (Monoid w, MonadCont m) => MonadCont (RWST r w s m) where
189        callCC f = RWST $ \r s ->
190                callCC $ \c ->
191                runRWST (f (\a -> RWST $ \_ s' -> c (a, s', mempty))) r s
192
193mapContT :: (m r -> m r) -> ContT r m a -> ContT r m a
194mapContT f m = ContT $ f . runContT m
195
196withContT :: ((b -> m r) -> (a -> m r)) -> ContT r m a -> ContT r m b
197withContT f m = ContT $ runContT m . f
198
199{- $simpleContExample
200Calculating length of a list continuation-style:
201
202>calculateLength :: [a] -> Cont r Int
203>calculateLength l = return (length l)
204
205Here we use @calculateLength@ by making it to pass its result to @print@:
206
207>main = do
208>  runCont (calculateLength "123") print
209>  -- result: 3
210
211It is possible to chain 'Cont' blocks with @>>=@.
212
213>double :: Int -> Cont r Int
214>double n = return (n * 2)
215>
216>main = do
217>  runCont (calculateLength "123" >>= double) print
218>  -- result: 6
219-}
220
221{- $callCCExample
222This example gives a taste of how escape continuations work, shows a typical
223pattern for their usage.
224
225>-- Returns a string depending on the length of the name parameter.
226>-- If the provided string is empty, returns an error.
227>-- Otherwise, returns a welcome message.
228>whatsYourName :: String -> String
229>whatsYourName name =
230>  (`runCont` id) $ do                      -- 1
231>    response <- callCC $ \exit -> do       -- 2
232>      validateName name exit               -- 3
233>      return $ "Welcome, " ++ name ++ "!"  -- 4
234>    return response                        -- 5
235>
236>validateName name exit = do
237>  when (null name) (exit "You forgot to tell me your name!")
238
239Here is what this example does:
240
241(1) Runs an anonymous 'Cont' block and extracts value from it with
242@(\`runCont\` id)@. Here @id@ is the continuation, passed to the @Cont@ block.
243
244(1) Binds @response@ to the result of the following 'callCC' block,
245binds @exit@ to the continuation.
246
247(1) Validates @name@.
248This approach illustrates advantage of using 'callCC' over @return@.
249We pass the continuation to @validateName@,
250and interrupt execution of the @Cont@ block from /inside/ of @validateName@.
251
252(1) Returns the welcome message from the @callCC@ block.
253This line is not executed if @validateName@ fails.
254
255(1) Returns from the @Cont@ block.
256-}
257
258{-$ContTExample
259'ContT' can be used to add continuation handling to other monads.
260Here is an example how to combine it with @IO@ monad:
261
262>import Control.Monad.Cont
263>import System.IO
264>
265>main = do
266>  hSetBuffering stdout NoBuffering
267>  runContT (callCC askString) reportResult
268>
269>askString :: (String -> ContT () IO String) -> ContT () IO String
270>askString next = do
271>  liftIO $ putStrLn "Please enter a string"
272>  s <- liftIO $ getLine
273>  next s
274>
275>reportResult :: String -> IO ()
276>reportResult s = do
277>  putStrLn ("You entered: " ++ s)
278
279Action @askString@ requests user to enter a string,
280and passes it to the continuation.
281@askString@ takes as a parameter a continuation taking a string parameter,
282and returning @IO ()@.
283Compare its signature to 'runContT' definition.
284-}