Bibliography

“Lazy Functional State Threads”, Launchbury and Peyton Jones (1993).

Motivation

Some algorithms and data-structures depend critically on destructive updates for efficiency e.g.:

• graph traversals (DFS, BFS);
• UNION-FIND.

The IO and ST monads allow us to express such algorithms in Haskell with the same complexity as an imperative language.

IO References

IO References

data IORef a    -- from Data.IORef
       -- a reference to a value of type `a'

newIORef :: a -> IO (IORef a)       -- create

readIORef :: IORef a -> IO a        -- read

writeIORef :: IORef a -> a -> IO () -- write

Example

import Data.IORef

main :: IO ()
main = do r <- newIORef 0
          incr r
          incr r
          v <- readIORef r
          print v -- ouputs 2

incr :: IORef Int -> IO ()
incr r = do v <- readIORef r
            writeIORef r (v+1)

Combined read-apply-write

modifyIORef :: IORef a -> (a -> a) -> IO ()

• read a reference
• apply a function to the current value
• write back the result

incr :: IORef Int -> IO ()
incr r =  do v <- readIORef r
             writeIORef r (v+1)

   -- is equivalent to:
incr :: IORef Int -> IO ()
incr r = modifyIORef r (+1)

Larger example

import Data.IORef
import Control.Monad (forM_)

-- sum all values in a list
-- using a mutable reference 
sumIO :: Num a => [a] -> IO a
sumIO xs = do
  r <- newIORef 0
  forM_ xs $
    \x -> modifyIORef r (+x) 
  readIORef r

Mutable Arrays

-- from Data.Array.IO

data IOArray i e
 -- indices `i' and elements `e'

-- NB: simplified types (no type classes)
newArray :: (i,i) -> e -> IO (IOArray i e)
newListArray :: (i,i) -> [e] -> IO (IOArray i e)

readArray :: IOArray i e -> i -> IO e 
writeArray :: IOArray i e -> i -> e -> IO ()

Example: random shuffle

shuffle :: [a] -> IO [a]
shuffle xs = do
    let n = length xs
    ar <- makeArray n xs
    forM [1..n] $ \i -> do
         j <- randomRIO (i,n)
         vi <- readArray ar i
         vj <- readArray ar j
         writeArray ar j vi
         return vj
   where
   makeArray :: Int -> [a] -> IO (IOArray Int a)
   makeArray n xs = newListArray (1,n) xs

Limitations

• The IO monad “taints” the types of every function using IORefs
• There is no “safe” function runIO :: IO a -> a because it would allow arbitrary input/output interleaved with pure computations
• However, just using mutable references internally should be safe
  • e.g. to implement an imperative algorithm and expose a pure interface
• This justifies a special monad named ST (state threads)

ST Monad

The ST Monad

data ST s a   -- from Control.Monad.ST

instance Monad (ST s) where ...

ST s a is a computation using mutable references that yields a value of type a.

The type parameter s is a phantom:

• ensures that references created in one ST computation do not “escape” outside its scope
• it is never instantiated and has no runtime cost!

ST references

data STRef s a   -- from Data.STRef
  -- mutable reference to a value `a'

newSTRef :: a -> ST s (STRef s a)

readSTRef :: STRef s a -> ST s a

writeSTRef :: STRef s a -> a -> ST s ()

modifySTRef :: STRef s a -> (a -> a) -> ST s ()

Example revisited

example :: ST s Int
example = do r <- newSTRef 0
             incr r
             incr r
             readSTRef r

incr :: STRef s Int -> ST s ()
incr r = modifySTRef r (+1)

Running ST computations

We use runST to run ST computations, e.g.:

> runST example
2
> :type runST example
runST example :: Int

The result is just an integer.

Running ST (cont.)

The type of runST is almost like:

runST :: ST s a -> a  -- NB: not quite right!

Runs an ST computation and yields a (pure) value a (more later).

Example: summing a list

sum' :: Num a => [a] -> a
sum' xs = runST $ do
  r <- newSTRef 0
  forM_ xs $
    \x -> modifySTRef r (+x)
  readSTRef r

Note that sum' is a pure function — it has exactly the same type as the Prelude sum.

Problem

What happens if we use a reference from one ST computation in another?

let r = runST (newSTRef 0)
    a = runST (readSTRef r)
    b = runST (writeSTRef r 1 >> return 1)
in  a + b

Types to the rescue!

let r = runST (newSTRef 0)
in ...

The real type of runST prevents the above:

runST :: (forall s. ST s a) -> a

runST does not admit a type that “leaks” references:

(forall s. ST s (STRef s Int)) -> STRef s Int

A longer example

Depth-first search (DFS) of a graph:

• integer vertices
• graph represented by an adjacency matrix (a purely functional array)
• internally uses a mutable array for marking visited vertices

type Graph = Array Vertex [Vertex] 
type Vertex = Int

Graph DFS

dfs g v =
  runST $ do marks <- newArray (bounds g) False 
             dfs' g [v] marks

dfs' g [] marks = return []
dfs' g (n:ns) marks = do
  vis <- readArray marks n
  if vis then
    dfs' g ns marks
    else do
       writeArray marks n True
       ns' <- dfs' g ((g!n)++ns) marks
       return (n:ns')

Graph DFS (cont.)

dfs' :: Graph -> [Vertex]
   -> STArray s Vertex Bool -> ST s [Vertex]

dfs :: Graph -> Vertex -> [Vertex]

The result of the auxiliary dfs' is a monadic computation but result of the wrapper dfs is just a list of vertices

Hence:

• dfs can freely combined with other Haskell functions;
• tested using QuickCheck;
• run in parallel

References and lazy evaluation

• Lazy evaluation works with imperative algorithms too
• Can be beneficial by allowing decoupling producers and consumers
• However: it can sometimes lead to space leaks

(Examples in the following slides.)

Example: space leak

sum' :: Num a => [a] -> a
sum' xs = runST $ do
   r <- newSTRef 0
   forM_ xs $ \x -> modifySTRef r (+x)
   readSTRef r

• modifySTRef does not force evaluation of the function(+x)
• allocates a large delayed expression \(0+x_1+x_2+ \cdots +x_n\) that is evaluated by readSTRef only at the end
• solution: use modifySTRef' instead of modifySTRef