`ap zip tail`表达式是如何工作的？

Question

我在想如何将f x = zip x (tail x)改写成点-free形式。于是我使用了pointfree程序，得到的结果是f = ap zip tail，其中ap是Control.Monad中的函数。

我不理解这个点-free定义是如何工作的。如果可以从类型的角度理解它，我希望我能理解它。

import Control.Monad (ap)
let f = ap zip tail
let g = ap zip
:info ap zip tail f g
ap :: Monad m => m (a -> b) -> m a -> m b
    -- Defined in `Control.Monad'
zip :: [a] -> [b] -> [(a, b)]   -- Defined in `GHC.List'
tail :: [a] -> [a]      -- Defined in `GHC.List'
f :: [b] -> [(b, b)]    -- Defined at <interactive>:3:5
g :: ([a] -> [b]) -> [a] -> [(a, b)]
    -- Defined at <interactive>:4:5

通过观察表达式ap zip tail，我会认为zip是 ap的第一个参数，而tail是ap的第二个参数。

Monad m => m (a -> b) -> m a -> m b
           \--------/   \---/
              zip        tail

但这是不可能的，因为zip和tail的类型与函数ap所需的类型完全不同。即使考虑到列表是某种单子。

- user7610

---

我能想到的唯一解释是，ap类型中的a变成了zip类型的[a] -> [b]。如果是这种情况，那么支配它的统一规则（如果这是正确的词）是什么？ - user7610

ghci显示类型为ap zip tail :: Monad ((->) [b]) => [b] -> [(b, b)]... 没有太多的调查，我会说Monad ((->) [b])是你想要了解的。 我认为http://learnyouahaskell.com/for-a-few-monads-more#reader可能会帮助你理解这里发生了什么。 - Adam Wagner

顺便提一下，zip <*> tail 是等价的，而且看起来更漂亮。 - daniel gratzer

对我来说，最漂亮的是原始的 f x = zip x (tail x)，可能是因为它是唯一一种让我立刻看到作者意图的形式。 - user7610

Answer 1

ap的类型标记是Monad m => m (a -> b) -> m a -> m b，你已经将zip和tail作为参数传递给它了，所以让我们看一下它们的类型标记。首先是tail :: [a] -> [a] ~ (->) [a] [a]（这里~是类型相等运算符），如果我们将这个类型与ap的第二个参数的类型进行比较，

 (->) [x]  [x] ~ m a
((->) [x]) [x] ~ m a

我们得到 a ~ [x] 和 m ~ ((->) [x]) ~ ((->) a)。现在我们可以看到我们所处的单子是 (->) [x]，而不是 []。如果我们将能够替换的内容替换到 ap 函数的类型签名中，我们会得到：

(((->) [x]) ([x] -> b)) -> (((->) [x]) [x]) -> (((->) [x]) b)

由于这不太易读，通常可以按以下方式编写：

  ([x] -> ([x] -> b)) -> ([x] -> [x]) -> ([x] -> b)
~ ([x] ->  [x] -> b ) -> ([x] -> [x]) -> ([x] -> b)

zip的类型为[x] -> [y] -> [(x, y)]。我们可以看到这与ap的第一个参数对齐。

[x]         ~    [x]   
[y]         ~    [x]   
[(x, y)]    ~    b

我已经将类型垂直列出，以便您可以轻松地查看哪些类型对齐。所以显然 x ~ x，y ~ x 和 [(x, y)] ~ [(x, x)] ~ b，因此我们可以完成将 b ~ [(x, x)] 替换到 ap 的类型签名中：

([x] -> [x] -> [(x, x)]) -> ([x] -> [x]) -> ([x] -> [(x, x)])
--   zip                        tail        ( ap  zip  tail )
--                                            ap  zip  tail u = zip u (tail u)

希望这样能为您澄清问题。

编辑: 正如danvari在评论中指出的那样，单子(->) a有时被称为reader单子。

- bheklilr

---

值得一提的是(->)是阅读器单子。 - dnaq

Answer 2

理解这个问题有两个方面：

1. 类型魔法
2. 实现中的信息流

首先，这帮助我理解类型魔法：

1) zip          : [a] → ( [a] → [(a,a)] )
2) tail         : [a] → [a]
3) zip <*> tail : [a] → [(a,a)]

4) <*> : Applicative f ⇒ f (p → q) → f p → f q

在这种情况下，对于<*>，

5) f x = y → x

请注意，在5中，f是一种类型构造器。将f应用于x会生成一种类型。此外，这里的=被重载为表示类型的等价。 y目前是一个占位符，在这种情况下，它是[a]，这意味着：

6) f x = [a] -> x

使用6，我们可以将1、2和3改写如下：

7) zip          : f ([a] → [(a,a)])
8) tail         : f [a]
9) zip <*> tail : f ([a] → [(a,a)])  →  f [a]  →  f [(a,a)]

所以，看着第4点，我们进行如下替换：

10) p = [a]
11) q = [(a,a)]
12) f x =  [a] → x

(再次重复6，这里又来了12)

其次是信息流，即实际功能。这更容易理解，从应用实例 y →的<*>的定义中可以清楚地看出，以下是使用不同标识符名称和使用中缀样式重写的内容：

13) g <*> h $ xs = g xs (h xs)

替换如下：

14) g = zip
15) h = tail

提供：

zip <*> tail $ xs        (Using 14 and 15)
  ==
zip xs (tail xs)         (Using 13 )

- algotrific

---

我仍然不清楚的部分是，您如何获得第5步（似乎是ghc自动推断我们要使用（->））。它能够自动执行此操作，因为它是唯一可用的applicative实例吗？ - achalk