Editing Denotative (section)

== Being privately imperative ==

[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.2237&rep=rep1&type=pdf In 1994] researchers discovered a way to denotatively accommodate the imperative style by excluding the use of <i>externally visible</i> side-effects. For example:

<blockquote>
<haskell>
type Graph = Array Vertex [Vertex]
data Tree a = Node a [Tree a]

dfs :: Graph -> [Vertex] -> [Tree Vertex]
dfs g vs = runST (
              newSTArray (bounds g) False >>= \ marks ->
              search marks vs
           )
  where search :: STArray s Vertex Bool -> [Vertex]
                  -> ST s [Tree Vertex]
        search marks   []   = return []
        search marks (v:vs) = readSTArray marks v >>= \ visited ->
                              if visited then
                                 search marks vs
                              else
                                writeSTArray marks v True >>
                                search marks (g!v)    >>= \ ts ->
                                search marks vs       >>= \ us ->
                                return ((Node v ts): us)
</haskell>

:<small>from Figure 2 (page 17 of 51) of [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.3656&rep=rep1&type=pdf State in Haskell]</small>
</blockquote>

Even though <code>dfs</code>'s local definition:

<haskell>
        search :: STArray s Vertex Bool -> [Vertex] -> ST s [Tree Vertex]
</haskell>

uses mutability and sequencing, the use of <code>runST</code> keeps those imperative details confined to <code>dfs</code>, hence its denotative type:

<haskell>
dfs :: Graph -> [Vertex] -> [Tree Vertex]
</haskell>

Therefore to be denotative, a programming language only needs to avoid using side effects which are externally visible: namely those of I/O.