Using unsafePerformIO safely?

39

From page 17 of 51 in Launchbury and Peyton-Jone’s State in Haskell:

dfs g vs = runST (
              newArr (bounds g) False `thenST` \ marks ->
              search marks vs
           )
  where search :: MutArr s Vertex Bool -> [Vertex]
                  -> ST s [Tree Vertex]
        search marks   []   = returnST []
        search marks (v:vs) = readArr marks v `thenST` \ visited ->
                              if visited then
                                 search marks vs
                              else
                                writeArr marks v True `thenST_`
                                search marks (g!v)    `thenST` \ ts ->
                                search marks vs       `thenST` \ us ->
                                returnST ((Node v ts): us)

where:

type Graph = Array Vertex [Vertex]
data Tree a = Node a [Tree a]

Here’s one way to rewrite that original code for dfs:

dfs g vs = unsafePerformIO (
              newIOArray (bounds g) False >>= \ marks ->
              search marks vs
           )
  where search :: IOArray Vertex Bool -> [Vertex]
                  -> IO [Tree Vertex]
        search marks   []   = return []
        search marks (v:vs) = readIOArray marks v >>= \ visited ->
                              if visited then
                                 search marks vs
                              else
                                writeIOArray marks v True >>
                                search marks (g!v)    >>= \ ts ->
                                search marks vs       >>= \ us ->
                                return ((Node v ts): us)

Even though the use of side effects in both definitions is basically the same, the IO version would be a violation of the given rule (it not being “free of side effects”) - in this case the presence of side effects is of no consequence, as they cannot be observed outside the scope of dfs.

1 Like