如何导出此函数的类型：

Question

我正在努力提高演奏水平 "type tetris"。我有以下功能：

(=<<) :: 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

(zip =<<) 等同于 (>>= zip)，这可能使其更具可读性。无论哪种方式，zip 都占据了这些函数中的 (a -> m b) 位置，正如您正确观察到的那样。

一个更直观的转换是考虑 =<< 的元数。它 "takes" 两个参数，所以如果我们将它应用于一个，我们应该只剩下一个。因此，签名 ([b] -> [a]) -> [b] -> [(a, b)] 是一元函数！

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

那么 m 是什么？ Monad 实例存在于函数 (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 2

在做其他事情之前先做两件事是有帮助的：

放入显式括号，使 x->y->z 变为 x->(y->z)
重命名类型变量以避免冲突

考虑到这一点，让我们重写类型

(=<<) :: 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])（这确实是一个 monad）并且 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 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'

如果我们按照 function monad 的特定情况下的类型，我们可以看到 (g =<< f) x == g (f x) x，所以

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

从中更容易查看其类型的含义。

(*) 是类型 a1 -> m b1 和 [a] -> [b] -> [(a, b)] 的 substitution resulting from the successful unification（完全括起来时是 [a] -> ([b] -> [(a, b)])，因为 ->类型中的 s 关联到右侧）。或者完全前缀形式，

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

如何导出此函数的类型：

How do I derive the type for this function:

haskell

types

composition