A couple of days ago, Hal Daume III asked
what does fixST do?
Briefly, fixST allows recursive definitions of values in the ST monad. As you can guess, there's a bunch of such operators for different monads, the most famous being "fixIO", the corresponding operator for the IO monad. These operators are known as "value recursion operators". Maybe, list, IO, lazy and strict ST monads, the output monad, environment monad (and various combinations thereof) are examples of monads that have such operators. However, it is not necessarily the case that every monad has an associated value recursion operator. For instance, as far as I know, there is no such operator for the continuation monad. To understand how these operators work, may be I can suggest an exercise. It's a variant of Richard Bird's "replaceMin" problem. Given a datatype of the form: data Tree a = L a | B (Tree a) (Tree a) the aim is to write a function: replaceMin :: Tree Int -> Tree Int such that replaceMin replaces all the elements with the minimum one in the tree. For instance: Main> replaceMin (B (L 2) (B (L 3) (L 4))) B (L 2) (B (L 2) (L 2)) It is indeed very easy to write a two-pass solution: First traverse to get the minimum, then reconstruct the tree using this value. The challenge is to solve this problem in one pass. Richard Bird gave a solution in 1984. (I'm not going to copy the solution here, it's quite a well known algorithm..) Now consider an extension to the problem, where we not only want to transform the tree, but also want to print the nodes as we traverse it. The type of replaceMin becomes: replaceMin :: Tree Int -> IO (Tree Int) For instance: Main> replaceMin (B (L 2) (B (L 3) (L 4))) >>= print 2 3 4 B (L 2) (B (L 2) (L 2)) Again, a two pass solution is easy. Can you solve this in one pass as well? To do so, you'll have to use fixIO.. This exercise should clear up the use of fixIO, and indirectly that of fixST. You can easily imagine numbering the nodes for instance, where you can use the ST monad to keep track of numbers. Than, you'd need fixST. For a solution to this problem (and a more detailed discussion), visit: http://www.cse.ogi.edu/PacSoft/projects/rmb/repMin.html For info on value recursion operators in general: http://www.cse.ogi.edu/PacSoft/projects/rmb/ -Levent.