what's the relationship between Monad and single threaded?

Question

When I study Monod I want to know what path is best for understanding Haskell's Monad. Many people such as Bartosz Milewski proposed that Monads for functional programming is the best material. After reading a part of this paper I got the same feeling, but in 4.2 Array transforms, I have no idea how to understand the summary about Monad as I miss some foundation in the bottom part of page 16:

"Making M into an abstract data type guarantees that single threading is preserved, and hence it is safe to implement assignment with an in-place update. The use of data abstraction is essential for this purpose. Otherwise, one could write programs such as (\x -> (assign i v x ; assign i w x )) that violate the single threading property."

I don't know why Philip Wadler discuss single threading here? data M a = State -> (a, State) must be very important for guaranteeing single threading, why?

For that I implement the code of this section 4.2 Array transforms, where I assume that my Array is like Arr [("ok", 0), ("no", 1)], and index is string, value is Int:

type M a = State -> (a, State)
data Arr = Arr [(Id, Val)] deriving (Show)
type State = Arr
type Id = String
type Val = Int
type Ix = Id

update ix val arr = updateNew ix val arr (Arr [])
           where updateNew ix val (Arr (x:xs)) (Arr newArr) = 
                case (fst x) == ix of
                   True -> Arr (newArr ++ ((ix,val):xs))
                   False -> updateNew ix val (Arr xs) (Arr (newArr ++ [x]))

assign :: Ix -> Val -> M ()
assign i v = \x -> ((), update i v x)

But this is not helpful for me to understand the above summary. I hope one enthusiastic person to explain more about it!

Answer 1

In Haskell, something like [("ok", 0), ("no", 1)] is not an array*, but rather a list. Haskell lists are immutable, so you don't even have to think about them changing. Arrays are another story. There are actually two very different things, both called arrays: immutable arrays and mutable arrays.

Immutable arrays are just alternative representations of certain sorts of functions along with some information about their domains.

Wadler is discussing mutable arrays, which can actually be changed. We don't actually handle these arrays directly; rather, we deal with values that serve as pointers to them. In languages like ML, Java, C, etc., you can "follow" a pointer any time you have one to access or modify the value(s) it points to. But that would completely break Haskell's referential transparency, which is critical to both understanding and optimizing it.

So what we do instead is encapsulate the changes to an array within an abstract monad. All sorts of things are going on under the hood that break the rules, but what gets exposed to you, the programmer, is guaranteed to make sense. There are actually two monads that can support mutable arrays in GHC: IO and ST s. ST s lets you, in a pure function, make an array, mutate it all sorts of ways, and then produce a pure result. IO, on the other hand, lets you intermix array creation and modifications with other IO actions.

* In GHC, it might be an array, because GHC offers an extension called OverloadedLists, but even in GHC it's very unlikely to be an array.