MonadFix
From HaskellWiki
m (formatting correction) 
(→Lazy algorithm interleaved with effects: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/118679/focus=118878) 

(One intermediate revision by one user not shown)  
Line 2:  Line 2:  
[[Category:Tutorials]]  [[Category:Tutorials]]  
−  The MonadFix typeclass provides the <hask>mfix</hask> method for value recursion. It can be used directly, or indirectly through the “[http://haskell.org/ghc/docs/  +  The MonadFix typeclass provides the <hask>mfix</hask> method for value recursion. It can be used directly, or indirectly through the “[http://haskell.org/ghc/docs/latest/html/users_guide/syntaxextns.html#recursivedonotation recursive do]” syntax extension (language extension <hask>RecursiveDo</hask>). It is useful for building cyclic data in monadic code. 
−  +  
−  +  
== What it is not and what it is ==  == What it is not and what it is ==  
Line 18:  Line 16:  
{  {  
    
−  !with  +  !with recsyntax 
!with mfix  !with mfix  
−  !with mdo  +  !with mdosyntax 
valign="top"  valign="top"  
<haskell>  <haskell>  
−  {# LANGUAGE  +  {# LANGUAGE RecursiveDo #} 
import Data.IORef  import Data.IORef  
data Node = Node Int (IORef Node)  data Node = Node Int (IORef Node)  
Line 73:  Line 71:  
{  {  
    
−  !with  +  !with recsyntax 
!with mfix  !with mfix  
−  !with mdo  +  !with mdosyntax 
valign="top"  valign="top"  
<haskell>  <haskell>  
−  {# LANGUAGE  +  {# LANGUAGE RecursiveDo #} 
import Data.IORef  import Data.IORef  
data Node = Node Int (IORef Node)  data Node = Node Int (IORef Node)  
Line 157:  Line 155:  
{  {  
    
−  !with  +  !with recsyntax 
!with mfix  !with mfix  
−  !with mdo  +  !with mdosyntax 
valign="top"  valign="top"  
<haskell>  <haskell>  
−  {# LANGUAGE  +  {# LANGUAGE RecursiveDo #} 
data BTree = Z  B Int BTree BTree deriving Show  data BTree = Z  B Int BTree BTree deriving Show  
repsum t = do  repsum t = do  
Line 220:  Line 218:  
}  }  
−  Note that  +  Note that the only laziness needed is just in the parameter <hask>s</hask> to the <hask>rep_x_sum</hask> algorithm. Increasing strictness in <hask>s</hask> will break it, for example this change: 
<haskell>  <haskell>  
−  +  (r',sr) < rep_x_sum r $! s  
</haskell>  </haskell>  
−  +  but increasing strictness in other things will not (make some other changes to see).  
−  +  
−  +  
−  +  
−  +  
If the given tree is mutable, we can choose to change the numbers inplace instead of building a new tree. Do not worry about race conditions of not knowing whether a number read is old or new — the first thing we do when we visit a node, we read its number to a variable name, so it is the old number; subsequently no matter what we do to the node, that variable name still refers to the old number, so we can rely on it. (For simplicity, only the numbers are mutable here, and the tree shape is immutable.)  If the given tree is mutable, we can choose to change the numbers inplace instead of building a new tree. Do not worry about race conditions of not knowing whether a number read is old or new — the first thing we do when we visit a node, we read its number to a variable name, so it is the old number; subsequently no matter what we do to the node, that variable name still refers to the old number, so we can rely on it. (For simplicity, only the numbers are mutable here, and the tree shape is immutable.)  
Line 236:  Line 230:  
{  {  
    
−  !with  +  !with recsyntax 
!with mfix  !with mfix  
−  !with mdo  +  !with mdosyntax 
valign="top"  valign="top"  
<haskell>  <haskell>  
−  {# LANGUAGE  +  {# LANGUAGE RecursiveDo #} 
import Data.IORef  import Data.IORef  
data BTree = Z  B (IORef Int) BTree BTree  data BTree = Z  B (IORef Int) BTree BTree 
Latest revision as of 18:36, 1 November 2015
Contents 
[edit] 1 What it is not and what it is
It is tempting to see “recursion” and guess it means performing actions recursively or repeatedly. No. It means recursion over values passed into and returned by actions; this is why it is called “value recursion”. An action may use a value to be returned by the same action, or even returned by another action several lines of code later. Some uses are: creating cyclic data structures; using monadic code to specify a graph or network.
[edit] 2 Examples
[edit] 2.1 Imperative cyclic linked lists
This example creates linked lists the imperative way: each node has a number and a pointer to the next node; a pointer is anwith recsyntax  with mfix  with mdosyntax 

{# LANGUAGE RecursiveDo #} import Data.IORef data Node = Node Int (IORef Node) mknode = do rec p < newIORef (Node 0 p) putStrLn "node created" return p main = do p < mknode Node x q < readIORef p print x Node y _ < readIORef q print y 
import Control.Monad.Fix import Data.IORef data Node = Node Int (IORef Node) mknode = mfix (\p > do p' < newIORef (Node 0 p) putStrLn "node created" return p') main = do p < mknode Node x q < readIORef p print x Node y _ < readIORef q print y 
{# LANGUAGE RecursiveDo #} import Data.IORef data Node = Node Int (IORef Node) mknode = mdo p < newIORef (Node 0 p) putStrLn "node created" return p main = do p < mknode Node x q < readIORef p print x Node y _ < readIORef q print y 
with recsyntax  with mfix  with mdosyntax 

{# LANGUAGE RecursiveDo #} import Data.IORef data Node = Node Int (IORef Node) mk2nodes = do rec p < newIORef (Node 0 r) r < newIORef (Node 1 p) putStrLn "nodes created" return p main = do p < mk2nodes Node x q < readIORef p print x Node y _ < readIORef q print y 
import Control.Monad.Fix import Data.IORef data Node = Node Int (IORef Node) mk2nodes = mfix (\ ~(p,r) > do p' < newIORef (Node 0 r) r' < newIORef (Node 1 p') putStrLn "nodes created" return (p',r')) >>= \(p,r) > return p main = do p < mk2nodes Node x q < readIORef p print x Node y _ < readIORef q print y 
{# LANGUAGE RecursiveDo #} import Data.IORef data Node = Node Int (IORef Node) mk2nodes = mdo p < newIORef (Node 0 r) r < newIORef (Node 1 p) putStrLn "nodes created" return p main = do p < mk2nodes Node x q < readIORef p print x Node y _ < readIORef q print y 
[edit] 2.2 Lazy algorithm interleaved with effects
A binary tree (immutable) with numbers at internal nodes is given. Replicate the tree but replace the numbers by their sum. Example in ASCII art (4+3+5+1=13) (leaves do nothing and are not shown):
given: answer: 4 13 / \ / \ 3 5 13 13 \ \ 1 13
Traverse the given tree just once. Moreover, as you traverse the given tree, print it out in some format (inorder format here, like ((3)4(5(1))), but you can modify for preorder or postorder).
Here is an approach. Given tree t and number s,given: answer: 4 s / \ / \ 3 5 (s s , 13) \ \ 1 s where s=13
So far this can be written in pure code, needing no Monad or MonadFix. But we also want to print something inside the algorithm, which brings in the IO Monad or the Writer Monad (this example uses IO); and to feed a return value back into a parameter in this monadic algorithm, we need MonadFix.
with recsyntax  with mfix  with mdosyntax 

{# LANGUAGE RecursiveDo #} data BTree = Z  B Int BTree BTree deriving Show repsum t = do rec (u,s) < rep_x_sum t s putStrLn "" return u rep_x_sum Z _ = return (Z, 0) rep_x_sum (B i l r) s = do putStr "(" (l',sl) < rep_x_sum l s putStr (show i) (r',sr) < rep_x_sum r s putStr ")" return (B s l' r', i + sl + sr) main = repsum (B 4 (B 3 Z Z) (B 5 Z (B 1 Z Z))) >>= print 
import Control.Monad.Fix data BTree = Z  B Int BTree BTree deriving Show repsum t = mfix (\ ~(u,s) > do (u',s') < rep_x_sum t s putStrLn "" return (u',s')) >>= \(u,s) > return u rep_x_sum Z _ = return (Z, 0) rep_x_sum (B i l r) s = do putStr "(" (l',sl) < rep_x_sum l s putStr (show i) (r',sr) < rep_x_sum r s putStr ")" return (B s l' r', i + sl + sr) main = repsum (B 4 (B 3 Z Z) (B 5 Z (B 1 Z Z))) >>= print 
{# LANGUAGE RecursiveDo #} data BTree = Z  B Int BTree BTree deriving Show repsum t = mdo (u,s) < rep_x_sum t s putStrLn "" return u rep_x_sum Z _ = return (Z, 0) rep_x_sum (B i l r) s = do putStr "(" (l',sl) < rep_x_sum l s putStr (show i) (r',sr) < rep_x_sum r s putStr ")" return (B s l' r', i + sl + sr) main = repsum (B 4 (B 3 Z Z) (B 5 Z (B 1 Z Z))) >>= print 
(r',sr) < rep_x_sum r $! s
but increasing strictness in other things will not (make some other changes to see).
If the given tree is mutable, we can choose to change the numbers inplace instead of building a new tree. Do not worry about race conditions of not knowing whether a number read is old or new — the first thing we do when we visit a node, we read its number to a variable name, so it is the old number; subsequently no matter what we do to the node, that variable name still refers to the old number, so we can rely on it. (For simplicity, only the numbers are mutable here, and the tree shape is immutable.)
with recsyntax  with mfix  with mdosyntax 

{# LANGUAGE RecursiveDo #} import Data.IORef data BTree = Z  B (IORef Int) BTree BTree repsum t = do rec s < rep_x_sum t s putStrLn "" return () rep_x_sum Z _ = return 0 rep_x_sum (B ref l r) s = do i < readIORef ref writeIORef ref s putStr "(" sl < rep_x_sum l s putStr (show i) sr < rep_x_sum r s putStr ")" return (i + sl + sr) main = do r4 < newIORef 4 r3 < newIORef 3 r5 < newIORef 5 r1 < newIORef 1 let t = (B r4 (B r3 Z Z) (B r5 Z (B r1 Z Z))) repsum t repsum t 
import Control.Monad.Fix import Data.IORef data BTree = Z  B (IORef Int) BTree BTree repsum t = mfix (\s > do s' < rep_x_sum t s putStrLn "" return s') >> return () rep_x_sum Z _ = return 0 rep_x_sum (B ref l r) s = do i < readIORef ref writeIORef ref s putStr "(" sl < rep_x_sum l s putStr (show i) sr < rep_x_sum r s putStr ")" return (i + sl + sr) main = do r4 < newIORef 4 r3 < newIORef 3 r5 < newIORef 5 r1 < newIORef 1 let t = (B r4 (B r3 Z Z) (B r5 Z (B r1 Z Z))) repsum t repsum t 
{# LANGUAGE RecursiveDo #} import Data.IORef data BTree = Z  B (IORef Int) BTree BTree repsum t = mdo s < rep_x_sum t s putStrLn "" return () rep_x_sum Z _ = return 0 rep_x_sum (B ref l r) s = do i < readIORef ref writeIORef ref s putStr "(" sl < rep_x_sum l s putStr (show i) sr < rep_x_sum r s putStr ")" return (i + sl + sr) main = do r4 < newIORef 4 r3 < newIORef 3 r5 < newIORef 5 r1 < newIORef 1 let t = (B r4 (B r3 Z Z) (B r5 Z (B r1 Z Z))) repsum t repsum t 
[edit] 3 MonadFix laws
Here are the laws of MonadFix and some implications.
 purity: mfix (return . h) = return (fix h)
 over pure things is the same as pure recursion.mfixdoes not add any monadic action of its own.mfix

 left shrinking: mfix (\x > a >>= \y > f x y) = a >>= \y > mfix (\x > f x y)
 A monadic action on the left (at the beginning) that does not involve the recursed value (here ) can be factored out ofx. Somfixdoes not change the number of times the action is performed, since putting it inside or outside makes no difference.mfix
 A monadic action on the left (at the beginning) that does not involve the recursed value (here
 sliding: if is strict,hmfix (liftM h . f) = liftM h (mfix (f . h))
 nesting: mfix (\x > mfix (\y > f x y)) = mfix (\x > f x x)
 these two laws are analogous to those of pure recursion, i.e., laws of .fix
 these two laws are analogous to those of pure recursion, i.e., laws of