Haskell/理解 Monad
![]() |
本頁正值覆寫,倘要翻閱前版,則請移步 斯處。 |
Notes and TODOs
編輯Loose ends:
- Explain monadic parser combinators! But in another chapter.
-
The basic triad "rock, scissors, paper" err, "reader, writer, state" is best introduced in another chapter, maybe entitled "A Zoo of Monads". Reader must include the famous function
[(a->b)] -> a -> [b]
also known assequence
! -
The
Random a
is too cute to not elaborate it further to probabilistic functional programming. The Monty Hall problem can be solved with that. Key: the implementation can be changed, it effectively becomes the Set-Monad then. Extension:guard
and backtracking. - Exceptions are a nice way to explain monads, too. See also [1].
介紹
編輯什麼是Monad
編輯定義:Monad是一個三元組 由類型構造器 和兩個多態函數
組成。兩個函數符合下列三個定律:
右單元 | |
左單元 | |
結合律 |
操作符 通常叫做"bind"。經常地,類型構造器 也稱作monad。
換句話說,一個monad就是一種類似隊列或者有限映射的抽象數據類型,所包含的兩個操作"bind"和"return"要滿足三個特性。一個特別需要注意的地方是一個monad 不是一個類型,而是一個"類型構造器",類似於一個從類型到類型的函數。並且,monad是一個非常抽像的概念,正如我們要看到的,"bind" 可能有很多不同的含義。
在Haskell里,我們可以將其定義為一個類型類
class Monad m where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b
所有的Monad
都假定滿足上面的三個定律。這個類是Haskell Prelude
的一部分,是在標準庫模塊Control.Monad
裏面定義的,並有一些擴展。
What use are Monads?
編輯After maturing in the mathematical discipline of category theory for some time, monads were introduced to programming when Eugenio Moggi showed[1] how they can unify the description of the semantics of different programming languages. Depending on the concrete monad chosen, different semantics emerge. For instance, mutable state can be modeled by the monad M a = s -> (a,s)
. Lists are a monad, too, and model nondeterminism and backtracking whereas the monad M a = Either e a
models exceptions.
One aim of the chapters on monads is to exemplify many of these different forms of computation. Of course, it's not our main interest to study programming language semantics, but it was Philip Wadler who noticed[2] [3] that we can directly implement Moggi's monads in Haskell. This is a powerful idea since each monad is a little minilanguage specially suited for a particular task. For instance, to program a state transformer, we can use a monad to model state. To solve a logic problem, we use the list monad to transparently handle backtracking. To handle failure and exceptions easily, we have the Either e
monad. And last but not least, there is the IO
monad to perform input/output, something that did not seem to fit well into a purely functional language. This and subsequent chapters are to guide you to through these minilanguages and to show they can simplify and structure your daily Haskell code.
But how can the rather short definition of monads given above relate all these very different forms of computation? They all share a common use pattern, namely the ability to combine two computations and into a compound computation by first "executing" and "then" binding, i.e. feeding the result to . This is what the operator captures and that's why it's called "bind". In other words, is similar to function composition. Of course, depending on the underlying monad, "executing" and "then" may have quite different meanings. Don't worry if this seems too abstract now, we will detail the genesis of with our first example monad in the section Stateful Computations.
Stateful Computations
編輯We will introduce with a practical example of stateful computations: random number generation. First, we will explain how a deterministic computer can generate "random" numbers. Then, we will introduce bind and return as useful functions for combining random number generators. And last but not least, the IO
monad will be introduced intuitively as a state transformer changing the "world state".
Random Number Generation
編輯Computers usually create random numbers by starting with a single random number (frequently called "seed") and applying some arithmetic operations to it to get a new random number. By repeating this process, we get a sequence of fairly random numbers. Of course, since each number is generated in a deterministic way from the previous one, they are not truly random, but pseudo-random numbers. But by choosing the arithmetic operations carefully to properly "scramble" the input number, they behave like real random numbers. To give an impression of how this "scrambling" works, here's an example function that generates a pseudo-random number from a previous one:
type Seed = Int
randomNext :: Seed -> Seed
randomNext rand =
if newRand > 0
then newRand
else newRand + 2147483647
where newRand = 16807 * lo - 2836 * hi
(hi,lo) = rand `divMod` 127773
There is much research on constructing good pseudo-random number generators, but fortunately, the Haskell standard library module System.Random
already implements a ready-to-use generator for us. However, its interface is best explained with randomNext
, so we will stick to that for now.
Let's implement a function that simulates a single roll of a die, i.e. that returns a random number from 1 to 6. But randomNext
uses large numbers since they can be scrambled much better, so we need to convert a Seed
to a number from 1 to 6. This can be done by dividing the Seed
by 6 and taking the remainder
toDieRoll :: Seed -> Int
toDieRoll seed = (seed `mod` 6) + 1
So, given an initial random Seed
, we can roll a die with it
toDieRoll 362354 -- hand-crafted initial random seed :-) 3
But something is missing: what if we want to roll the die a second time? For that, we have to generate a new random Seed
from the old one via randomNext
. In other words, we have to change the current Seed
, i.e. the state of our pseudo-random number generator. In Haskell, this can be accomplished by returning the new state in the result
rollDie :: Seed -> (Int, Seed)
rollDie seed = ((seed `mod` 6) + 1, randomNext seed)
This is the description of a state transformer: an initial state (the Seed
) is transformed to a new one while yielding a result (the Int
between 1 and 6). We can visualize it as:
To roll two dice and sum their pips, we can now feed the Seed
from the first roll to the second roll. Of course, we have to return the new state from the second dice roll as well for our function sumTwoDice
to be as useful as rollDie
:
sumTwoDice :: Seed -> (Int, Seed)
sumTwoDice seed0 =
let (die1, seed1) = rollDie seed0
(die2, seed2) = rollDie seed1
in (die1 + die2, seed2)
Again, a picture shows clearly how the state is passed from one rollDie
to the next. Note that randomNext
does not appear in the definition of sumTwoDice
, the state change it performs is already embedded in rollDie
. The function sumTwoDice
merely propagates the state updates.
This is the model that System.Random
employs, so we can now elaborate on its concrete interface. The library uses two type classes:RandomGen
andRandom
. Any instance of the former acts similar to ourSeed
, it's just called "random number generator", not "seed". This makes sense since the seed may have more complicated internals than just anInt
and is closely linked to the function that generates new pseudo-random numbers. In any case, the module exports a convenient random number generatorStdGen
and you most likely won't have to deal with theRandomGen
-class at all.
The interesting functions are those of the class Random
, in particular random
and randomR
. They are implemented for a few types like Bool
, Char
, Int
etc. so you can use them to generate different random things than numbers. The function randomR
returns a random number in a specified range, so that we can conveniently write
import System.Random
rollDie :: StdGen -> (Int, StdGen)
rollDie = randomR (1,6)
As a final note, you may want to compare random number creation in Haskell to its counterpart in imperative languages like C. In the latter, there usually is a "function" rand()
that returns a different and random result at each call but internally updates the random seed. Since Haskell is pure, the result of a function is determined solely by its parameters and manipulating the random seed has to manifest itself in the type.
練習 |
---|
.
|
Threading the State with bind
編輯>>
for the state monad is easier than >>=
. But it's meaningless for random numbers :-/ PICTUREs for the plumbing! Somehow shorten the discussion, mainly introduce return
more fluently. Expanding the definitions of the new combinators as exercises to check that the new code for sumTwoDice is the same as the old one.
In the last subsection, we've seen that state transformers like random number generators can be modeled by functions s -> (a,s)
where s
is the type of the state. Such a function takes a state and returns a result of type a
and a transformed state. However, programming with these functions is a bit tedious since we have to explicitly pass the state from one computation to the next one like in the definition of sumTwoDice
sumTwoDice :: Seed -> (Int, Seed)
sumTwoDice = \seed0 ->
let (die1, seed1) = rollDie seed0
(die2, seed2) = rollDie seed1
in (die1 + die2, seed2)
Each state has to be named and we have to take care to not pass the wrong state to the next function by accident.
Of course, we are Haskell programmers: if there are common patterns or boilerplate in our code, we should search for a way to abstract and capture them in a higher order function. Thus, we want to find something that can combine state transformers s -> (a,s)
to larger ones by passing the state from one to the next. A first attempt is an operator named "then"
(>>) :: (Seed -> (a,Seed)) -> (Seed -> (b,Seed)) -> (Seed -> (b,Seed))
which passes the state from the first computation to the second
(>>) m n = \seed0 ->
let (result1, seed1) = m seed0
(result2, seed2) = n seed1
in (result2, seed2)
By nesting it, we can already roll a die multiple times
rollDie >> (rollDie >> rollDie)
without seeing a single state! Unfortunately, (>>)
doesn't allow us to use the result of the first die roll in the following ones, it's simply ignored. In other words, this combinaton changes the random seed three times but only returns the pips from the last die roll. Rather pointless for random numbers, but we're on the right track. PICTURE FOR (>>)
!
We somehow need a way to pass the result from the first computation to the second, "then" is not yet general enough to allow the implementation of sumTwoDice
. But first, we should introduce a type synonym to simplify the type signatures
type Random a = Seed -> (a, Seed)
(>>) :: Random a -> Random b -> Random b
rollDie :: Random Int
sumTwoDice :: Random Int
Astonishingly, this gives an entirely new point of view: a value of type Random a
can be seen as a value of type a
that varies randomly. So, rollDie
can be interpreted as a number between 1 and 6 that "fidgets" and is sometimes "here" and sometimes "there" when asked about is value. We will explore this idea further, but for now, let's stick to our initial goal that Random a
is a simple shortcut for a state transformer. Just take a mental note about the observation that our aim of explicitely removing the state from our functions naturally asks for removing the state from our types, too.
Now, how to pass the result from one computation to the next? Well, we may simply give it as parameter to the next one
(>>=) :: Random a -> (a -> Random b) -> Random b
In other words, the second state transformer is now replaced by a function so that its result of type b
may depend on the previous result a
. The implementation is almost that of >>
(>>=) m g = \seed0 ->
let (result1, seed1) = m seed0
(result2, seed2) = (g result1) seed1
in (result2, seed2)
with the only difference being that g
now takes result1
as parameter. PICTURE!
This combinator named "bind" should finally allow us to implement sumTwoDice
. Let's see: we roll the first die and feed the result to a function that adds a second die roll to that
sumTwoDice :: Random Int
sumTwoDice = rollDie >>= (\die1 -> addToDie die1)
Adding the second die roll uses the remaining code from our original definition of sumTwoDice
.
addToDie :: Int -> Random Int
addToDie die1 = \seed1 ->
let (die2, seed2) = rollDie seed1
in (die1 + die2, seed2)
(Remember that Random Int = Seed -> (Int, Seed)
.) That's still unsatisfactory, since we would like to avoid all explicit state and just use >>=
a second time to feed the second dice roll to the sum
addToDie die1 = rollDie >>= (\die2 -> addThem die2)
where addThem die2 = \seed2 -> (die1 + die2, seed2)
That's the same as
addToDie die1 = rollDie >>= (\die2 -> (\seed2 -> (die1 + die2, seed2)))
which is almost
addToDie die1 = rollDie >>= (\die2 -> (die1 + die2))
though not quite since the latter doesn't type check since the sum has type Int
instead of the expected Random Int
. But we can convert the former into the latter with a helper function called "return"!
addToDie die1 = rollDie >>= (\die2 -> return (die1 + die2))
return :: a -> Random a
return x = \seed0 -> (x, seed0)
So, return
doesn't change the state but simply returns its argument as result. For random numbers, this means that return
creates a number that isn't random at all. Last but not least, we can drop the definition of addToDie
and directly write
sumTwoDice :: Random Int
sumTwoDice = rollDie >>= (\die1 ->
rollDie >>= (\die2 ->
return (die1 + die2)))
練習 |
---|
NOTE: Since import Prelude hiding ((>>=),return) to avoid compilation errors. |
To conclude, the quest of automating the passing of state from one computation to the next led us to the two operations that define a monad. Of course, this is just the beginning. The reader is probably not yet accustomed to the >>=
-combinator, how to program with it effectively? What about the three monad laws mentioned in the introduction? But before we embark to answer these questions in the next big section, let us emphasize the need for using >>=
as a main primitive in a slightly different example in the next subsection.
Input/Output needs bind
編輯IO
is the one type that requires the programmer to know what a monad is, the other monads are more or less optional. It makes abstract return
and bind
necessary. Explaining World -> (a, World) = IO a
and the need to hide the World
naturally leads to return
and >>=
. I guess we need to mention somewhere that main :: IO ()
is the link to the real world.
Performing input/output in a purely functional language like Haskell has long been a fundamental problem. How to implement operations like getChar
which returns the latest character that the user has typed or putChar c
which prints the character c
on the screen? Giving getChar
the type getChar :: Char
is not an option, since a pure function with no arguments must be constant. We somehow have to capture that getChar
also performs the side effect of interacting with the user. Likewise, a type putChar :: Char -> ()
is useless since the only value this function can return has to be ()
.
The breakthrough came when it was realized[4] that monads, i.e. the operations >>=
and return
can be used to elegantly deal with side effects. The idea is to give our two primitive operations the types
getChar :: IO Char
putChar :: Char -> IO ()
and interpret a value of type IO a
as a computation or action that performs a side effect before returning the value a
. This is rather abstract, so a more concrete way is to interpret IO
as a state transformer
type IO a = World -> (a, World)
that acts on and changes the "state of the world". In other words, printing a character takes the world and returns one where the character has been printed and reading a character returns a world where the character has been read. With this model, an action echo :: IO ()
that reads a character and immediately prints it to the screen would be written as
echo = \world0 ->
let (c , world1) = getChar world0
((), world2) = putChar c world1
in ((), world2)
Of course, this is a case for the bind combinator that passes the state of the world for us:
echo = getChar >>= putChar
But for IO a
, the use of >>=
is not a convenience, it is mandatory. This is because by passing around the world explicitly, we could write (either accidentally or even consciously) something that duplicates the world:
havoc = \world0 ->
let (c , world1) = getChar world0
((), world2) = putChar c world0
in ((), world2)
Now, where does putChar
get the character c
from? Did the state of world roll back similar to a time travel? This makes no sense, we have to ensure that the world is used in a single-threaded way. But this is easy to achieve: we just make IO a
an abstract data type and export only >>=
and return
for combining actions, together with primitive operations like putChar
.
There's even more: the model World -> (a,World)
for input/output just doesn't work, one of the exercises shows why. Also, there is no hope to extend it to concurrency and exceptions. In other words, it is imperative to make >>=
for composing effectful computations IO a
an abstract primitive operation.
練習 |
---|
|
Programming with bind and return
編輯Time to write programs! More complicated stuff for Random a
. Examples to code: St.Petersburg paradox, Lewis Carroll's pillow problem. Somewhere make explicit instances of the Monad
-class? Hm, we really need to incorporate the monad class in the type signatures. I'm not sure whether the nuclear waste metaphor is necessary?
In the last section, we showed how the two defining operations >>=
and return
of a monad arise as abstraction for composing state transformers. We now want to focus on how to program effectively with these.
Nuclear Waste Containers
編輯Random a
as fuzzy a
. Programming would be so much easier if we had extract :: Random a -> a
, bind is sooo unwieldy. Mental prevention: think of monads as "Nuclear waste containers", the waste may not leak outside at any cost. The thing closest to extract
we can have is join :: m (m a) -> m a
. The text probably talks too much about "monads as containers", I'm not sure what to do.
We saw that the bind operation takes a computation, executes it, and feeds its result to the next, like in
echo =
getChar >>=
\char -> putChar char sumTwoDice = rollDie >>=
\die1 -> rollDie >>=
\die2 -> return (die1 + die2)
(Note that for parsing, lambda expressions extend as far to the right as possible, so it's not necessary to put them in parantheses.) However, it could be tempting to "execute" a monadic action like IO a
with some hypothetical function
extract :: IO a -> a
in order to conveniently formulate
echo = return (putChar (extract getChar))
Of course, such a function does not make sense. For state transformers like Random a = Seed -> (a, Seed)
, it would have to invent a state and discard it again, thus regressing from our goal of passing the new state to the next computation.
Here's a metaphor to strengthen your mind against extract
:
- Think of a monadic computation
M a
as a container for a value of typea
that is unfortunately paired with highly dangerous nuclear waste. Under no circumstance should this tightly sealed container be opened toextract
thea
or the nuclear waste will leak out, resulting in a catastrophe!.
So, there are some like getChar :: IO Char
or rollDie :: Random Int
that produce a precious value but unfortunately cannot operate without tainting it with nuclear waste. But fortunately, we have our function
(>>=) :: Monad m => m a -> (a -> m b) -> m b
that nonetheless allows us to operate on the value contained in M a
by entering the container and applying the given function to the value inside it. This way, eveything happens inside the container and no nuclear materials leak out.
Arguably, this description of "bind" probably applies better to a function
fmap :: Monad m => (a -> b) -> m a -> m b
fmap f m = m >>= \x -> return (f x)
that takes a pure function into the container to transform the value within. You may notice that this is the defining mapping for functors, i.e. every monad is a functor. Apparently, fmap
is less general than >>=
since the latter expects the function to be lifted into the container to produce nuclear waste, too. The best what fmap
can do is
fmap' :: Monad m => (a -> (m b)) -> m a -> m (m b)
to produce a nested container. Of course, it is safe to open the inner container since the outer container still shields the environment from the nuclear waste
join :: Monad m => m (m a) -> m a
join m = m >>= id
In other words, we can describe the operation of >>=
as
m >>= g = join (fmap g m)
i.e. it lifts a waste-producing computation into the container and flattens the resulting nested containers.
We will explore this futher in #Monads as Containers.
Of course, we shouldn't take the nuclear waste metaphor too literally, since there usually is some way to "run" the computation. For instance, random numbers can be observed as an infinite list of random numbers produced by an initial random seed.
run :: Random a -> (Seed -> [a])
Only the IO
monad is a primitive in Haskell. How do we "run" it, then? The answer is that the link of a Haskell program to outside world is the function
main :: IO ()
which will be run by the operating system. In other words, the Haskell program itself ultimately produces nuclear waste, so there is no need to extract IO a -> a
.
練習 |
---|
|
do
-Notation
編輯
A common way to write the composition of multiple monadic computations is
sumTwoDice = do
die1 <-
rollDie die2 <-
rollDie return (die1 + die2)
Control Structures
編輯Needs a better title. Introduce sequence, fmap, liftMn, forM, mapM
and friends.
The three Monad Laws
編輯In the state monad, return
doesn't touch the state. That can be formulated abstractly with the first two monad laws. Hm, what about the third? How to motivate that? The third is intuitive: in the context of passing things around, order, not grouping matters (associativity).
Monads as containers
編輯Needs a better title. Introduce the second instances of monads, namely [a]
and Maybe a
. Shows that the operations return and bind are applicable to quite a range of problems. The more "exotic" example
data Tree a = Leaf a | Branch (Tree a) (Tree a)
belongs here, too, probably as exercise.
Lists
編輯concatMap
and sequence
..
Maybe
編輯Maybe Either
, too?
References
編輯- ↑ Moggi, Eugenio (1991). "Notions of Computation and Monads". Information and Computation 93 (1).
- ↑ w:Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
- ↑ w:Philip Wadler. The Essence of Functional Programming. Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1992.
- ↑ Simon Peyton Jones, Philip Wadler (1993). "Imperative functional programming". 20'th Symposium on Principles of Programming Languages.
理解 Monad |
習題解答 |
Monads |
理解 Monad >> 高級 Monad >> Monad 進階 >> MonadPlus >> Monadic parser combinators >> Monad transformers >> Monad 實務 |
Haskell |
Haskell基礎
>> 初級Haskell
>> Haskell進階
>> Monads
|