我如何获得这个功能的类型：

Question

我试图让在玩“俄罗斯方块型”更好。我具备的功能：

(=<<) :: Monad m => (a -> m b) -> m a -> m b
zip :: [a] -> [b] -> [(a, b)]

而GHCI告诉我：

(zip =<<) :: ([b] -> [a]) -> [b] -> [(a, b)]

我有一个很难搞清楚如何在这最后的签名来自前两个到达。我的直觉（由于缺乏一个更好的词）是说=<<的第一个参数，即a -> mb是某种调和对zip的签名，那么它应该所有这一切脱落。但是我不知道如何去完成这个飞跃。可它分解为一系列易于遵循的步骤？

Answer 1

它有助于一切之前，做两件事情：

1. 把这些括号使x->y->z成为x->(y->z)
2. 重命名类型变量，以便有没有发生冲突

威特考虑到这一点，让我们改写类型

(=<<) :: Monad m => (a -> m b) -> (m a -> m b)
zip :: [x] -> ([y] -> [(x, y)])

现在，匹配类型。到=<<第一个参数是zip，所以(a -> m b)是一样的[x] -> ([y] -> [(x, y)])。

a          ->        m b
[x]        ->        ([y] -> [(x, y)])

所以a是[x]和m b是([y] -> [(x, y)])。在前缀符号重写->，我们得到-> [y] [(x, y)]，这是一样的(-> [y]) [(x, y)]。

m             b
(-> [y])      [(x, y)]

所以m是(-> [y])（这是一个单子确实）和b是[(x, y)]。

所以，现在我们知道了什么是a，什么是b，什么是m。让我们改写(m a -> m b)在这些方面：

(m            a)          ->          (m            b)
((-> [y])     [x])        ->          ((-> [y])     [(x, y)])

在中缀风格再次改写，我们得到

([y] -> [x])              ->          ([y] -> [(x, y)])

这是，多达变量名是相同的答案GHC是给你的。

Answer 2

(zip =<<)相当于(>>= zip)，这使得它可能有点更具有可读性。无论哪种方式，zip占据了这些功能的(a -> m b)插槽，为你正确地观察到。

一个更直观的改造，使正在思考=<<的元数。它“以”两个参数，因此，如果我们把它应用到一个，我们只能留下一个。因此，签名([b] -> [a]) -> [b] -> [(a, b)]是一元函数！

(zip =<<) :: ([b] -> [a]) -> ([b] -> [(a, b)])
             ------------    -----------------
                 m a'                m b'

那么什么是m？单子实例存在功能(r ->)（或，可替换地，(->) r）。因此，在这种情况下r :: [b]（因此m :: ([b] ->)），a' :: [a]和b' :: [(a, b)]。

因此，zip适合就像我们断言开头：

a'  -> m b'                    -- substitute [(a,b)] for b'
a'  -> m [(a, b)]              -- substitute [a] for a'
[a] -> m [(a, b)]              -- substitute ([b] ->) for m
[a] -> ([b] -> [(a,b)])

[a] -> [b] -> [(a,b)]

Answer 3

只要把它们写下来一个在另一个具有垂直取向的辅助手段，而一贯重命名的类型变量，因此没有意外捕获：

(=<<) :: Monad m => (a1  ->     m    b1       ) -> m a1 -> m b1
zip   ::             [a] -> ([b] ->  [(a, b)])
                     [a] -> ([b] ->) [(a, b)]
                     [a] -> (->) [b] [(a, b)]
-----------------------------------------------------------
               a1 ~ [a] ,  m ~ (->) [b] ,  b1 ~ [(a, b)]               (*)
-----------------------------------------------------------
(zip =<<) :: Monad m =>                            m a1 -> m b1
                                          ((->) [b]) a1 -> ((->) [b]) b1
                                            ([b] -> a1) -> ([b] -> b1)
                                           ([b] -> [a]) -> ([b] -> [(a, b)])
                                           ([b] -> [a]) ->  [b] -> [(a, b)]

只要Monad ((->) [b])实例存在。其它：

> :i Monad
class Monad (m :: * -> *) where
    .......
instance Monad ((->) r) -- Defined in `GHC.Base'

如果我们按照功能单子的具体情况的类型，我们可以看到，(g =<< f) x == g (f x) x，等等

(zip =<<) f xs = zip (f xs) xs

从中很容易看出它的类型的意思。

---

(*)是从类型的成功substitution unification和a1 -> m b1产生的[a] -> [b] -> [(a, b)]（这是[a] -> ([b] -> [(a, b)])，当完全括号，因为在->s类型关联到右侧）。或完全前缀的形式，

    (->)  a1   ( m            b1       )
    (->)  [a]  ( ((->) [b])   [(a, b)] )