[Haskell] ST vs State

[David Menendez]

David Menendez writes:

> It's also possible to write ST in terms of State. 
> 
> Assume we have a Store ADT with this interface:
> 
>     data Store r
>     data STRef r a
>     withStore :: (forall r. Store r -> a) -> a
>     newRef    :: a -> Store r -> (STRef r a, Store r)
>     readRef   :: STRef r a -> Store r -> a
>     writeRef  :: STRef r a -> a -> Store r -> Store r
>     
> (The 'r' parameter is to make sure that references are only used with
> the Store that created them. The signature of withStore effectively
> gives every Store a unique value for r.)

Rats. The rank-2 type isn't enough to guarantee type-safety. You need a
monad (or linear types) to make sure that the Store is used
single-threadedly.
    
Using the API above, you can defeat the type checker.

    coerce :: a -> b
    coerce a = withStore (\s0 -> 
        let (r1,s1) = newRef a s0
            (r2,s2) = newRef undefined s0
        in readRef r2 s1)

(Of course, you would have needed a function like coerce to implement
the API in the first place.)
-- 
David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem>      |        of thermodynamics!"