Editing IO inside (section)

== Mutable data (references, arrays, hash tables...) ==

As you should know, every name in Haskell is bound to one fixed (immutable) value. This greatly simplifies understanding algorithms and code optimization, but it's inappropriate in some cases. As we all know, there are plenty of algorithms that are simpler to implement in terms of updatable variables, arrays and so on. This means that the value associated with a variable, for example, can be different at different execution points, so reading its value can't be considered as a pure function. Imagine, for example, the following code:

<haskell>
main = do let a0 = readVariable varA
              _  = writeVariable varA 1
              a1 = readVariable varA
          print (a0, a1)
</haskell>

Does this look strange?
# The two calls to <code>readVariable</code> look the same, so the compiler can just reuse the value returned by the first call.
# The result of the <code>writeVariable</code> call isn't used so the compiler can (and will!) omit this call completely.
# These three calls may be rearranged in any order because they appear to be independent of each other.

This is obviously not what was intended.  What's the solution? You already know this - use I/O actions! Doing that guarantees:

# the result of the "same" action (such as <span style="white-space: nowrap"><code>readVariable varA</code></span>) will not be reused
# each action will have to be executed
# the execution order will be retained as written

So, the code above really should be written as:

<haskell>
import Data.IORef
main = do varA <- newIORef 0  -- Create and initialize a new variable
          a0 <- readIORef varA
          writeIORef varA 1
          a1 <- readIORef varA
          print (a0, a1)
</haskell>

Here, <code>varA</code> has the type <span style="white-space: nowrap"><code>IORef Int</code></span> which means "a variable (reference) in the I/O monad holding a value of type <code>Int</code>". <code>newIORef</code> creates a new variable (reference) and returns it, and then read/write actions use this reference. The value returned by the <span style="white-space: nowrap"><code>readIORef varA</code></span> action depends not only on the variable involved but also on the moment this operation is performed so it can return different values on each call.

Arrays, hash tables and any other _mutable_ data structures are defined in the same way - for each of them, there's an operation that creates new "mutable values" and returns a reference to it. Then value-specific read and write operations in the I/O monad are used. The following code shows an example using mutable arrays:

<haskell>
import Data.Array.IO
main = do arr <- newArray (1,10) 37 :: IO (IOArray Int Int)
          a <- readArray arr 1
          writeArray arr 1 64
          b <- readArray arr 1
          print (a, b)
</haskell>

Here, an array of 10 elements with 37 as the initial value at each location is created. After reading the value of the first element (index 1) into <code>a</code> this element's value is changed to 64 and then read again into <code>b</code>. As you can see by executing this code, <code>a</code> will be set to 37 and <code>b</code> to 64.

Other state-dependent operations are also often implemented with I/O actions. For example, a random number generator should return a different value on each call. It looks natural to give it a type involving <code>IO</code>:

<haskell>
rand :: IO Int
</haskell>

Moreover, when you import a C routine you should be careful - if this routine is impure, i.e. its result depends on something "outside the Haskell program" (file system, memory contents, its own <code>static</code> internal state and so on), you should give it an <code>IO</code> type. Otherwise, the compiler can "optimize" repetitive calls to the definition with the same parameters!

For example, we can write a non-<code>IO</code> type for:

<haskell>
foreign import ccall
   sin :: Double -> Double
</haskell>

because the result of <code>sin</code> depends only on its argument, but

<haskell>
foreign import ccall
   tell :: Int -> IO Int
</haskell>

If you will declare <code>tell</code> as a pure function (without <code>IO</code>) then you may get the same position on each call!

=== Encapsulated mutable data: ST ===

If you're going to be doing things like sending text to a screen or reading data from a scanner, <code>IO</code> is the type to start with - you can then customise existing I/O operations or add new ones as you see fit. But what if that shiny-new (or classic) algorithm you're working on really only needs mutable state - then having to drag that <code>IO</code> type from <code>main</code> all the way through to wherever you're implementing the algorithm can get quite irritating.

Fortunately there is a better way!  One that remains totally pure and yet allows the use of references, arrays, and so on - and it's done using, you guessed it, Haskell's versatile type system (and one extension).

Remember our definition of <code>IO</code>?

<haskell>
newtype IO a = Act (RealWorld -> (a, RealWorld))
</haskell>

Well, the new <code>ST</code> type makes just one change:

<haskell>
newtype ST s a = Act' (s -> (a, s))
</haskell>

If we wanted to, we could use <code>ST</code> to define <code>IO</code>:

<haskell>
type IO a = ST RealWorld a
</haskell>

Let's add some extra definitions:

<haskell>
newSTRef     :: a -> ST s (STRef s a)      -- these are
readSTRef    :: STRef s a -> ST s a        --  usually
writeSTRef   :: STRef s a -> a -> ST s ()  -- primitive

newSTArray   :: Ix i => (i, i) -> ST s (STArray s i e) -- also usually primitive
              ⋮

instance Monad (ST s) where
    m >>= k  = let actual' (Act' m) = m in
               Act' $ \s1 -> case actual' m s1 of (x, s2) -> actual' (k x) s2
    return x = Act' $ \s1 -> (x, s1)
</haskell>

...that's right - this new <code>ST</code> type is also monadic!

So what's the big difference between the <code>ST</code> and <code>IO</code> types? In one word - <code>runST</code>:
<haskell>
runST :: (forall s . ST s a) -> a
</haskell>

Yes - it has a very unusual type. But that type allows you to run your stateful computation ''as if it was a pure definition!''

The <code>s</code> type variable in <code>ST</code> is the type of the local state.  Moreover, all the fun mutable stuff available for <code>ST</code> is quantified over <code>s</code>:
<haskell>
newSTRef  :: a -> ST s (STRef s a)
newArray_ :: Ix i => (i, i) -> ST s (STArray s i e)
</haskell>

So why does <code>runST</code> have such a funky type? Let's see what would happen if we wrote
<haskell>
makeSTRef :: a -> STRef s a
makeSTRef a = runST (newSTRef a)
</haskell>
This fails, because <code>newSTRef a</code> doesn't work for all state types <code>s</code> - it only works for the <code>s</code> from the return type <span style="white-space: nowrap"><code>STRef s a</code></span>.

This is all sort of wacky, but the result is that you can only run an <code>ST</code> computation where the output type is functionally pure, and makes no references to the internal mutable state of the computation. In exchange for that, there's no access to I/O operations like writing to or reading from the console. The monadic <code>ST</code> type only has references, arrays, and such that are useful for performing pure computations.

Just like <code>RealWorld</code>, the state type doesn't actually mean anything.  We never have an actual value of type <code>s</code>, for instance. It's just a way of getting the type system to do the work of ensuring purity is preserved - it's being used like another baton.

On the inside <code>runST</code> uses that newly-made baton to run the computation. When it finishes <code>runST</code> separates the resulting value from the final baton. This value is then returned by <code>runST</code>.

Because the internal implementations of <code>IO</code> and <code>ST</code> are so similar, there's this function:

<haskell>
stToIO :: ST RealWorld a -> IO a
</haskell>

The difference is that <code>ST</code> uses the type system to forbid unsafe behavior like extracting mutable objects from their safe <code>ST</code> wrapping, but allowing purely functional outputs to be performed with all the handy access to mutable references and arrays.

For example, here's a particularly convoluted way to compute the integer that comes after zero:

<haskell>
oneST :: ST s Integer -- note that this works correctly for any s
oneST = do var <- newSTRef 0
           modifySTRef var (+1)
           readSTRef var

one :: Int
one = runST oneST
</haskell>