what does fixST do?
Levent Erkok
erkok@cse.ogi.edu
Tue, 12 Feb 2002 17:15:58 +0000
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.