From 07fae6d68aac2c2c398c010495d9542c1eb9b9b7 Mon Sep 17 00:00:00 2001 From: "simonpj@microsoft.com" Date: Mon, 2 Nov 2009 17:22:17 +0000 Subject: [PATCH] Improve documentation of 'rec' in do-notation Merge to 6.12 along with the main DoRec patch --- docs/users_guide/glasgow_exts.xml | 75 +++++++++++++++++++++++-------------- 1 file changed, 46 insertions(+), 29 deletions(-) diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml index f6879fe..0988279 100644 --- a/docs/users_guide/glasgow_exts.xml +++ b/docs/users_guide/glasgow_exts.xml @@ -871,8 +871,6 @@ the do-notation. The flag provides the necessary synta Here is a simple (albeit contrived) example: {-# LANGUAGE DoRec #-} -import Control.Monad.Fix - justOnes = do { rec { xs <- Just (1:xs) } ; return (map negate xs) } @@ -883,9 +881,9 @@ The background and motivation for recusrive do-notation is described in A recursive do for Haskell, by Levent Erkok, John Launchbury, Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania. -This paper is essential reading for anyone making non-trivial use of mdo-notation, -and we do not repeat it here. However, note that GHC uses a different syntax than the one -in the paper. +The theory behind monadic value recursion is explained further in Erkok's thesis +Value Recursion in Monadic Computations. +However, note that GHC uses a different syntax than the one described in these documents. @@ -913,30 +911,54 @@ while rec is monadic. (In Haskell let is really letrec, of course.) -The Control.Monad.Fix library introduces the MonadFix class. Its definition is: - +The static and dynamic semantics of rec can be described as follows: + + +First, +similar to let-bindings, the rec is broken into +minimal recursive groups, a process known as segmentation. +For example: -class Monad m => MonadFix m where - mfix :: (a -> m a) -> m a +rec { a <- getChar ===> a <- getChar + ; b <- f a c rec { b <- f a c + ; c <- f b a ; c <- f b a } + ; putChar c } putChar c - -The function mfix -dictates how the required recursion operation should be performed. For example, -justOnes desugars as follows: +The details of segmentation are described in Section 3.2 of +A recursive do for Haskell. +Segmentation improves polymorphism, reduces the size of the recursive "knot", and, as the paper +describes, also has a semantic effect (unless the monad satisfies the right-shrinking law). + + +Then each resulting rec is desugared, using a call to Control.Monad.Fix.mfix. +For example, the rec group in the preceding example is desugared like this: -justOnes = do { xs <- mfix (\xs' -> do { xs <- Just (1:xs'); return xs }) - ; return (map negate xs) } +rec { b <- f a c ===> (b,c) <- mfix (\~(b,c) -> do { b <- f a c + ; c <- f b a } ; c <- f b a + ; return (b,c) }) In general, the statment rec ss is desugared to the statement - vs <- mfix (\~vs -> do { ss; return vs }) +vs <- mfix (\~vs -> do { ss; return vs }) where vs is a tuple of the variables bound by ss. -Moreover, the original rec typechecks exactly -when the above desugared version would do so. (For example, this means that + +The original rec typechecks exactly +when the above desugared version would do so. For example, this means that the variables vs are all monomorphic in the statements -following the rec, because they are bound by a lambda.) +following the rec, because they are bound by a lambda. + + +The mfix function is defined in the MonadFix +class, in Control.Monad.Fix, thus: + +class Monad m => MonadFix m where + mfix :: (a -> m a) -> m a + + + + Here are some other important points in using the recursive-do notation: @@ -958,18 +980,13 @@ for Haskell's internal state monad (strict and lazy, respectively). -Unlike ordinary do-notation, but like let and where bindings, -name shadowing is not allowed; that is, all the names bound in a single mdo must +Like let and where bindings, +name shadowing is not allowed within a rec; +that is, all the names bound in a single rec must be distinct (Section 3.3 of the paper). - -Similar to let-bindings, GHC implements the segmentation technique described in Section 3.2 of -A recursive do for Haskell, -to break up a single rec statement into a sequence of statements with -rec groups of minimal size. This -improves polymorphism, reduces the size of the recursive "knot", and, as the paper -describes, also has a semantic effect (unless the monad satisfies the right-shrinking law). +It supports rebindable syntax (see ). @@ -979,7 +996,7 @@ describes, also has a semantic effect (unless the monad satisfies the right-shri GHC used to support the flag , which enabled the keyword mdo, precisely as described in -A recursive do for Haskell, +A recursive do for Haskell, but this is now deprecated. Instead of mdo { Q; e }, write do { rec Q; e }. -- 1.7.10.4