您可以使用 (==) <*> reverse 找出列表是否为回文。它是如何工作的？

Question

我已经尝试使用类型完成此操作，但我仍然难以理解它是如何工作的。

鉴于：

> :t (==)
(==) :: Eq a => a -> a -> Bool

> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

> :t reverse
reverse :: [a] -> [a]

> :t (==) <*> reverse
(==) <*> reverse :: Eq a => [a] -> Bool

直觉上我可以理解它将相等运算符与反向组合在一起，它创建了一个函数来检查反向列表是否等于原始列表，但这实际上并没有比已经漂亮的信息更多的信息显而易见。

有人可以更详细地分析这里实际发生的事情的内部结构吗？

Answer 1

从(<*>)

的类型开始

> : t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

现在 (->) k 是 Applicative 的一个实例，带有实现

instance Applicative ((->) k) where
    pure a  = \_ -> a
    f <*> g = \k -> f k (g k)

特别是 (<*>) 专用于 (->) k 的类型是

(<*>) :: (k -> a -> b) -> (k -> a) -> (k -> b)

所以申请(==) <*> reverse是

(==) <*> reverse = \k -> (==) k (reverse k)
                 = \k -> k == reverse k

即它检查列表是否等于它的反向列表。

Answer 2

Chris Taylor 的回答恰到好处，但我觉得更直观的另一种看待方式是：Applicative 函数类型实例的作用是这样的：

"Feed"相同参数类型的两个函数的相同参数值；
将他们的结果与另一个函数结合起来。

所以基本上，如果您有 f :: t -> a 和 g:: t -> b，Applicative 实例允许您将函数 h :: a -> b -> c 映射到 a 和 b 结果，假设 f 和 g 将提供相同的参数。

所以想一想如何以一种不复杂的方式编写回文测试：

palindrome :: Eq a => [a] -> Bool
palindrome xs = xs == reverse xs

xs 在定义的右侧出现了两次：一次作为 == 的参数，第二次作为 reverse 的参数。这会自动告诉您可能有一种方法可以使用 (->) t 应用程序实例来消除重复。对此的另一种可能更直观的攻击是首先将函数重写为：

palindrome xs = id xs == reverse xs

...其中 id x = x 是 身份函数 ，它只是 returns 它的参数（并且是标准库函数）。现在您可以使用标准 Applicative 习语 (f <$> a0 <*> ... <*> an) 将其重写为：

-- Function that feed the same argument value to both `id` and `reverse`,
-- then tests their results with `==`: 
palindrome = (==) <$> id <*> reverse

现在我们可以询问是否有办法在重写中删除 id。由于 <$> 只是 shorthand for fmap，我们可以研究 Functor instance for (->) t，这只是表达函数组合的另一种方式：

instance Functor ((->) t) where
  -- Mapping `f` over a *function* `g` is just the same as composing `f`
  -- on the results of `g`.
  fmap f g = f . g

函数组合最重要的属性之一是对于任何函数 f:

f . id = f

因此将其应用于上面的 palindrome 版本，我们得到：

-- Since `f . id = f` for all `f`, then `(==) <$> id` is just `(==)`:
palindrome = (==) <*> reverse

您可以使用 (==) <*> reverse 找出列表是否为回文。它是如何工作的？

You can find out if a list is a palindrome using (==) <*> reverse. How does it work?

reverse

haskell

list

palindrome