What is the relationship between Monad and single threaded?
When I am learning Monod, I want to know which path is best for understanding Haskell Monad. Many people like Bartosz Milewski suggested Monads for functional programming is the best stuff. After reading part of this article, I got the same feeling, but in 4.2 Array transforms
, I have no idea how to understand the Monad summary as I missed some kind of foundation at the bottom of page 16:
"Creating M in an abstract data type ensures that it is single-threaded and therefore safe to implement in-place update assignment. It is important to use data abstraction for this purpose. Otherwise, you would write programs such as (\x -> (assign i v x ; assign i w x ))
that violate the single-threaded property."
I don't know why Philip Wadler is discussing here single threading
? data M a = State -> (a, State)
must be very important to ensure a single thread, why?
To do this, I am implementing the code in this section 4.2 Array transforms
where I assume my array is like Arr [("ok", 0), ("no", 1)]
, and index
is a string, value 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 it is not helpful for me to understand the above summary. I hope one enthusiastic person can explain more about this!
source to share
In Haskell, something seems to be [("ok", 0), ("no", 1)]
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 different things called arrays: immutable arrays and mutable arrays.
Immutable arrays are simply alternative representations of some kinds of functions along with some information about their domains.
Wadler discusses modified arrays that can actually be modified. We don't actually process these arrays; rather, we are dealing with values that serve as pointers to them. In languages like ML, Java, C, etc., you can "follow" a pointer any time you access it or change its values. But this will completely break Haskell's information transparency, which is critical to understanding and optimizing.
So instead, we wrap the encapsulation of the changes into an array in an abstract monad. All sorts of things happen under the hood that break the rules, but what exposes 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
allows you to create an array in a pure function, mutate in all sorts of ways, and then produce a clean result. IO
on the other hand, allows you to mix array creation and modification with other activities IO
.
*
In GHC it can be an array because GHC offers a named extension OverloadedLists
, but even in GHC it is unlikely to be an array.
source to share