what does fixST do?

[Levent Erkok]

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.