为什么我们需要单子?

We want to program only using functions. ("functional programming (FP)" after all). Then, we have a first big problem. This is a program: f(x) = 2 * x g(x,y) = x / y How can we say what is to be executed first? How can we form an ordered sequence of functions (i.e. a program) using no more than functions? Solution: compose functions. If you want first g and then f, just write f(g(x,y)). This way, "the program" is a function as well: main = f(g(x,y)). OK, but ... More problems: some functions might fail (i.e. g(2,0), divide by 0). We have no "exceptions" in FP (an exception is not a function). How do we solve it? Solution: Let's allow functions to return two kind of things: instead of having g : Real,Real -> Real (function from two reals into a real), let's allow g : Real,Real -> Real | Nothing (function from two reals into (real or nothing)). But functions should (to be simpler) return only one thing. Solution: let's create a new type of data to be returned, a "boxing type" that encloses maybe a real or be simply nothing. Hence, we can have g : Real,Real -> Maybe Real. OK, but ... What happens now to f(g(x,y))? f is not ready to consume a Maybe Real. And, we don't want to change every function we could connect with g to consume a Maybe Real. Solution: let's have a special function to "connect"/"compose"/"link" functions. That way, we can, behind the scenes, adapt the output of one function to feed the following one. In our case: g >>= f (connect/compose g to f). We want >>= to get g's output, inspect it and, in case it is Nothing just don't call f and return Nothing; or on the contrary, extract the boxed Real and feed f with it. (This algorithm is just the implementation of >>= for the Maybe type). Also note that >>= must be written only once per "boxing type" (different box, different adapting algorithm). Many other problems arise which can be solved using this same pattern: 1. Use a "box" to codify/store different meanings/values, and have functions like g that return those "boxed values". 2. Have a composer/linker g >>= f to help connecting g's output to f's input, so we don't have to change any f at all. Remarkable problems that can be solved using this technique are: having a global state that every function in the sequence of functions ("the program") can share: solution StateMonad. We don't like "impure functions": functions that yield different output for same input. Therefore, let's mark those functions, making them to return a tagged/boxed value: IO monad.

总幸福!

Monads are just a convenient framework for solving a class of recurring problems. First, monads must be functors (i.e. must support mapping without looking at the elements (or their type)), they must also bring a binding (or chaining) operation and a way to create a monadic value from an element type (return). Finally, bind and return must satisfy two equations (left and right identities), also called the monad laws. (Alternatively one could define monads to have a flattening operation instead of binding.)

列表单子通常用于处理不确定性。绑定操作选择列表中的一个元素(直观地说，它们都在并行世界中)，让程序员对它们进行一些计算，然后将所有世界中的结果组合到一个列表中(通过连接或平铺嵌套列表)。下面是如何在Haskell的单元框架中定义一个排列函数:

perm [e] = [[e]]
perm l = do (leader, index) <- zip l [0 :: Int ..]
            let shortened = take index l ++ drop (index + 1) l
            trailer <- perm shortened
            return (leader : trailer)

下面是一个示例repl会话:

*Main> perm "a"
["a"]
*Main> perm "ab"
["ab","ba"]
*Main> perm ""
[]
*Main> perm "abc"
["abc","acb","bac","bca","cab","cba"]

需要注意的是，列表单子绝不是计算的副作用。一个数学结构是一个单子(即符合上面提到的接口和规律)并不意味着副作用，尽管副作用现象通常很好地适合单子框架。

如果你有一个类型构造函数和返回该类型族值的函数，你就需要单子。最终，你会想把这些函数组合在一起。这是回答为什么的三个关键要素。

让我详细说明一下。你有Int, String和Real和函数类型Int -> String, String -> Real等等。你可以很容易地组合这些函数，以Int -> Real结尾。生活是美好的。

然后，有一天，您需要创建一个新的类型家族。这可能是因为您需要考虑不返回值(Maybe)、返回错误(Either)、多个结果(List)等的可能性。

注意Maybe是一个类型构造函数。它接受一个类型，比如Int，然后返回一个新的类型，可能是Int。首先要记住，没有类型构造函数，没有单子。

当然，你想在你的代码中使用你的类型构造函数，很快你就会以像Int -> Maybe String和String -> Maybe Float这样的函数结束。现在，你不能轻易地组合你的功能。生活不再美好。

这时单子就来拯救我们了。它们允许你再次组合这类功能。你只需要改变成分。> = =。

我不认为IO应该被视为一个特别出色的单子，但它肯定是一个更令人震惊的初学者，所以我将用它来解释。

Naïvely为Haskell构建IO系统

对于纯函数式语言来说，最简单的IO系统(实际上也是Haskell最初使用的IO系统)是:

main₀ :: String -> String
main₀ _ = "Hello World"

在懒惰的情况下，这个简单的签名就足以实际构建交互式终端程序了——但是非常有限。最令人沮丧的是我们只能输出文本。如果我们增加一些更令人兴奋的输出可能性呢?

data Output = TxtOutput String
            | Beep Frequency

main₁ :: String -> [Output]
main₁ _ = [ TxtOutput "Hello World"
          -- , Beep 440  -- for debugging
          ]

很可爱，但当然，更现实的“替代输出”将写入文件。但是你也需要某种方法从文件中读取。任何机会吗?

当我们使用main₁程序并简单地将文件输送到流程(使用操作系统设施)时，我们实际上已经实现了文件读取。如果我们可以从Haskell语言中触发文件读取…

readFile :: Filepath -> (String -> [Output]) -> [Output]

这将使用一个“交互式程序”String->[Output]，给它一个从文件中获得的字符串，并产生一个简单地执行给定的非交互式程序。

这里有一个问题:我们实际上不知道文件何时被读取。[Output]列表确实给出了一个很好的输出顺序，但我们没有得到输入何时完成的顺序。

解决方案:让输入事件也成为要做的事情列表中的项目。

data IO₀ = TxtOut String
         | TxtIn (String -> [Output])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [Output])
         | Beep Double

main₂ :: String -> [IO₀]
main₂ _ = [ FileRead "/dev/null" $ \_ ->
             [TxtOutput "Hello World"]
          ]

好吧，现在你可能发现了一个不平衡:你可以读取一个文件并依赖于它输出，但你不能使用文件内容来决定是否也读取另一个文件。显而易见的解决方案:使输入事件的结果也是IO类型，而不仅仅是Output类型。这当然包括简单的文本输出，但也允许读取额外的文件等。

data IO₁ = TxtOut String
         | TxtIn (String -> [IO₁])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [IO₁])
         | Beep Double

main₃ :: String -> [IO₁]
main₃ _ = [ TxtIn $ \_ ->
             [TxtOut "Hello World"]
          ]

这实际上允许你在程序中表达任何你想要的文件操作(虽然可能性能不太好)，但这有点过于复杂:

Main₃可以分解出一系列的动作。为什么我们不简单地使用签名::IO₁，它有一个特例? 这些列表不再真正给出程序流程的可靠概述:大多数后续计算只会作为某些输入操作的结果被“宣布”。因此，我们不妨放弃列表结构，并简单地为每个输出操作添加一个“and then do”。

data IO₂ = TxtOut String IO₂
         | TxtIn (String -> IO₂)
         | Terminate

main₄ :: IO₂
main₄ = TxtIn $ \_ ->
         TxtOut "Hello World"
          Terminate

还不错!

那么这一切与单子有什么关系呢?

在实践中，您不希望使用普通构造函数来定义所有程序。需要有几个这样的基本构造函数，但对于大多数更高级别的东西，我们希望编写一个具有一些不错的高级签名的函数。事实证明，其中大多数看起来非常相似:接受某种有意义类型的值，并产生一个IO操作作为结果。

getTime :: (UTCTime -> IO₂) -> IO₂
randomRIO :: Random r => (r,r) -> (r -> IO₂) -> IO₂
findFile :: RegEx -> (Maybe FilePath -> IO₂) -> IO₂

这里显然有一个模式，我们最好这样写

type IO₃ a = (a -> IO₂) -> IO₂    -- If this reminds you of continuation-passing
                                  -- style, you're right.

getTime :: IO₃ UTCTime
randomRIO :: Random r => (r,r) -> IO₃ r
findFile :: RegEx -> IO₃ (Maybe FilePath)

Now that starts to look familiar, but we're still only dealing with thinly-disguised plain functions under the hood, and that's risky: each “value-action” has the responsibility of actually passing on the resulting action of any contained function (else the control flow of the entire program is easily disrupted by one ill-behaved action in the middle). We'd better make that requirement explicit. Well, it turns out those are the monad laws, though I'm not sure we can really formulate them without the standard bind/join operators.

无论如何，我们现在已经达到了一个IO的公式，它有一个合适的单子实例:

data IO₄ a = TxtOut String (IO₄ a)
           | TxtIn (String -> IO₄ a)
           | TerminateWith a

txtOut :: String -> IO₄ ()
txtOut s = TxtOut s $ TerminateWith ()

txtIn :: IO₄ String
txtIn = TxtIn $ TerminateWith

instance Functor IO₄ where
  fmap f (TerminateWith a) = TerminateWith $ f a
  fmap f (TxtIn g) = TxtIn $ fmap f . g
  fmap f (TxtOut s c) = TxtOut s $ fmap f c

instance Applicative IO₄ where
  pure = TerminateWith
  (<*>) = ap

instance Monad IO₄ where
  TerminateWith x >>= f = f x
  TxtOut s c >>= f = TxtOut s $ c >>= f
  TxtIn g >>= f = TxtIn $ (>>=f) . g

显然，这不是一个有效的IO实现，但原则上是可用的。

本杰明·皮尔斯在TAPL中说

一个类型系统可以看作是计算一种静态 近似于程序中项的运行时行为。

这就是为什么配备了强大类型系统的语言严格来说比类型差的语言更具表现力。你可以用同样的方式来思考单子。

正如@Carl和sigfpe所指出的那样，你可以为一个数据类型配备你想要的所有操作，而无需求助于单子、类型类或任何其他抽象的东西。然而，单子不仅允许你编写可重用的代码，还可以抽象出所有冗余的细节。

举个例子，假设我们想过滤一个列表。最简单的方法是使用filter函数:filter (> 3) [1..]10]，等于[4,5,6,7,8,9,10]。

filter的一个稍微复杂一点的版本也是从左向右传递累加器

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

获取所有i，使i <= 10, sum [1..]I] > 4, sum [1..I] < 25，我们可以写

filterAccum (\a x -> let a' = a + x in (a' > 4 && a' < 25, a')) 0 [1..10]

等于[3,4,5,6]。

或者我们可以重新定义nub函数，它从列表中删除重复的元素，使用filterAccum:

nub' = filterAccum (\a x -> (x `notElem` a, x:a)) []

nub' [1,2,4,5,4,3,1,8,9,4] equals [1,2,4,5,3,8,9]. A list is passed as an accumulator here. The code works, because it's possible to leave the list monad, so the whole computation stays pure (notElem doesn't use >>= actually, but it could). However it's not possible to safely leave the IO monad (i.e. you cannot execute an IO action and return a pure value — the value always will be wrapped in the IO monad). Another example is mutable arrays: after you have leaved the ST monad, where a mutable array live, you cannot update the array in constant time anymore. So we need a monadic filtering from the Control.Monad module:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
   flg <- p x
   ys  <- filterM p xs
   return (if flg then x:ys else ys)

filterM对列表中的所有元素执行一个单体操作，生成元素，单体操作返回True。

一个带有数组的过滤示例:

nub' xs = runST $ do
        arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool)
        let p i = readArray arr i <* writeArray arr i False
        filterM p xs

main = print $ nub' [1,2,4,5,4,3,1,8,9,4]

按预期打印[1,2,4,5,3,8,9]。

还有一个带有IO单子的版本，它询问要返回哪些元素:

main = filterM p [1,2,4,5] >>= print where
    p i = putStrLn ("return " ++ show i ++ "?") *> readLn

E.g.

return 1? -- output
True      -- input
return 2?
False
return 4?
False
return 5?
True
[1,5]     -- output

最后一个例子，filterAccum可以用filterM来定义:

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

StateT单子，它在底层使用，只是一个普通的数据类型。

这个例子说明，单子不仅允许您抽象计算上下文和编写干净的可重用代码(由于单子的可组合性，正如@Carl解释的那样)，而且还可以统一对待用户定义的数据类型和内置原语。

答案当然是“我们没有”。与所有抽象一样，这是不必要的。

Haskell不需要单子抽象。在纯语言中执行IO并不是必需的。IO类型自己就能很好地处理这个问题。现有的do块的单方糖化可以替换为GHC中定义的bindIO、returnIO和failIO糖化。基础模块。(它不是关于hackage的文档模块，所以我必须指出它的文档来源。)所以不，没有必要抽象单子。

如果不需要它，为什么它会存在?因为人们发现许多计算模式形成了单一结构。结构的抽象允许编写跨该结构的所有实例的代码。更简单地说——代码重用。

在函数式语言中，最强大的代码重用工具是函数的组合。老的(.)::(b -> c) -> (a -> b) -> (a -> c)运算符非常强大。它可以很容易地编写小函数，并以最小的语法或语义开销将它们粘合在一起。

但在某些情况下，这些类型并不完全正确。当你有foo::(b ->也许c)和bar::(a ->也许b)你会做什么?foo。bar不进行类型检查，因为b和b可能不是相同的类型。

但是…几乎是对的。你只是需要一点回旋的余地。你想要把Maybe b看成是b，但是直接把它们看成是同一种类型不是一个好主意。这或多或少和空指针是一样的，Tony Hoare把空指针称为“十亿美元的错误”。因此，如果不能将它们视为同一类型，也许可以找到一种方法来扩展组合机制(.)提供的功能。

In that case, it's important to really examine the theory underlying (.). Fortunately, someone has already done this for us. It turns out that the combination of (.) and id form a mathematical construct known as a category. But there are other ways to form categories. A Kleisli category, for instance, allows the objects being composed to be augmented a bit. A Kleisli category for Maybe would consist of (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c) and id :: a -> Maybe a. That is, the objects in the category augment the (->) with a Maybe, so (a -> b) becomes (a -> Maybe b).

突然之间，我们将复合的功能扩展到了传统(.)操作无法处理的事情上。这是一种新的抽象力量的来源。Kleisli分类适用于更多类型，而不仅仅是Maybe。他们与每一种能够组合出合适类别的类型一起工作，并遵循类别法则。

左标识:id。F = F 右恒等式:f。Id = f 结合律:f。(g。H) = (f。g)。h

As long as you can prove that your type obeys those three laws, you can turn it into a Kleisli category. And what's the big deal about that? Well, it turns out that monads are exactly the same thing as Kleisli categories. Monad's return is the same as Kleisli id. Monad's (>>=) isn't identical to Kleisli (.), but it turns out to be very easy to write each in terms of the other. And the category laws are the same as the monad laws, when you translate them across the difference between (>>=) and (.).

那么为什么要这么麻烦呢?为什么在语言中有一个单子抽象?如上所述，它支持代码重用。它甚至可以在两个不同的维度上实现代码重用。

代码重用的第一个维度直接来自抽象的存在。您可以编写跨所有抽象实例工作的代码。有一个完整的Monad -loops包，由与Monad的任何实例一起工作的循环组成。

第二个维度是间接的，但它源于构图的存在。当组合很容易时，很自然地编写小的、可重用的代码块。同样，使用(.)操作符可以鼓励编写小型的、可重用的函数。

那么为什么抽象存在呢?因为它被证明是一种工具，可以在代码中实现更多的组合，从而创建可重用的代码，并鼓励创建更多可重用的代码。代码重用是编程的终极目标之一。单子抽象的存在是因为它将我们推向了圣杯。