Haskell `回文 = 反向 >>= (==)`

Question

有人可以解释一下 Haskell 中回文的这个函数是如何工作的：

palindrome :: Eq a => [a] -> Bool
palindrome = reverse >>= (==)

-- type declarations
reverse :: [a] -> [a]
>>= :: Monad m => m a -> (a -> m b) -> m b
(reverse >>=) :: ([a] -> [a] -> b) -> [a] -> b
(==) :: Eq a => a -> a -> Bool

特别是，Monad 类型类在函数上的定义是如何工作的，以及它如何以某种方式将 (==) 的输入数量从两个列表减少到一个列表？

Answer 1

这有点令人兴奋，所以带上:-)

monad 是一个类型构造函数，它接受一个类型参数。例如，Maybe就是这样一个类型构造函数。所以，Maybe是一个 monad，然后Maybe Int是那个 monad 中的 monadic 值。类似地，IO是一个 monad，然后IO Int是那个 monad 中的 monadic 值。

现在，也可以从具有两个类型参数的类型构造函数中创建 monad 。为此，我们只需要修复第一个。例如，看看Either：它有两个参数，但一个 monad 必须只有一个。所以我们修复了第一个参数。因此Either Bool是一个 monad，然后Either Bool Int是那个 monad 中的一个 monadic 值。类似地，Either String是一个完全不同的monad，然后Either String Int是那个 monad 中的 monadic 值。

另一方面，看看函数是如何表示的：

a -> b

但这只是中缀运算符的诡计，类似于5 + 42or "foo" <> "bar"。这个中缀符号可以像这样“规范化”：

(->) a b

所以实际上，“函数”可以看作是一个具有两个类型参数的类型构造函数，就像 doEither一样。对于“函数”构造函数来说，这些参数都有特定的含义——一个是“函数输入”，另一个是“函数输出”。

好的，现在我们准备将函数视为 monad。就像 with 一样Either，为了做到这一点，我们必须修复第一个类型参数。因此，例如，(->) Bool是一个 monad，然后(->) Bool Int（也称为Bool -> Int）是该 monad 中的一个 monadic 值。同样，(->) String是一个完全不同的monad，然后(->) String Int（也称为String -> Int）是该 monad 中的一个 monadic 值。

给你一个直觉，一种看待它的方式是这样的 monad 中的 monadic 值意味着“承诺”——也就是说，“你给我一个String，我给你一个Int背”。然后标准的 monadic 组合让您可以将这些承诺组合在一起，就像您组合IO动作一样。

陪我到此为止？好的，很好。

现在让我们看看如何实现绑定（又名>>=）。的签名>>=如下：

(>>=) :: m a -> (a -> m b) -> m b

现在让我们将其专门用于函数。让我们说，现在，那个m ~ (->) Bool。然后我们有：

(>>=) :: (->) Bool a -> (a -> (->) Bool b) -> (->) Bool b

或者，如果我们以(->)中缀形式重写构造函数，我们得到：

(>>=) :: (Bool -> a) -> (a -> (Bool -> b)) -> (Bool -> b)

所以你看 - 绑定接受“承诺a”，然后是一个函数从a“承诺b”，然后返回“承诺b”。那么，实现是微不足道的：

(>>=) :: (Bool -> a) -> (a -> (Bool -> b)) -> (Bool -> b)
(>>=) promiseOfA f = \theBool -> f (promiseOfA theBool) theBool

这里我们创建了一个新的“promise”，它是一个接受 的函数，Bool这个“promise”所做的是将给定的传递给Bool“promise of a”，然后将结果传递a给函数f，它返回一个“promise of b”，然后我们将其传递给它Bool以最终获得结果b。

这里要注意：看看如何theBool使用两次 - 首先传递给promiseOfA，然后再次传递给f? 这就是“减少参数数量”的地方。这是我们传递参数两次的地方。

但是，当然，这不仅仅适用于Bools。任何输入类型都是公平的游戏。所以我们可以这样概括：

(>>=) :: (input -> a) -> (a -> (input -> b)) -> (input -> b)
(>>=) promiseOfA f = \i -> f (promiseOfA i) i

（与标准库中的实际定义进行比较）。

呼！

好的，现在我们终于准备好查看您的原始示例。首先，看看reverse。由于它是一个函数，我们可以将其视为 monad 中的一个 monadic 值(->) [a]——即“承诺[a]”，其中“输入”也是[a]。

然后，签名(==)：

(==) :: Eq x => x -> x -> Bool

（请注意，我故意替换a为x：不要将它与afromreverse的签名混淆- 它们是两个不同的as，不必是相同的类型）

我们可以将此签名视为一个函数，它接受一个x并返回另一个类型为 的函数x -> Bool。所以：

(==) :: x -> (x -> Bool)

这可以看作是 bind 的第二个参数， type 的一个a -> m b。为了这么认为，我们必须说，a ~ x和m ~ (->) x和b ~ Bool。所以这里有问题的 monad 是(->) x- 即输入类型为 的“承诺” x。

可是等等！为了将此函数绑定到reverse，它们需要在同一个 monad 中！这意味着x ~ [a]. 这反过来意味着类型(==)被固定到：

(==) :: [a] -> ([a] -> Bool)

因此，当我们(>>=)将其reverse作为第一个参数和(==)第二个参数传递时，我们得到：

reverse >>= (==) 
= \i -> (==) (reverse i) i   -- by my definition above
= \i -> reverse i == i