Haskell如何进行Beta转换派生类型？

Question

我正在通过 fp-course exercise. There is a question 挡住我的路来学习 Haskell。不知道Haskell怎么推断出lift2 (<$>) (,)的类型，结果是Functor k => (a1 -> k a2) -> a1 -> k (a1, a2).

我已经尝试了lift2 (<$>)的类型，并通过GHCI的命令:t lift2 (<$>)进行了验证。步骤如下。
我知道lift2 :: Applicative k => (a -> b -> c) -> k a -> k b -> k c
我也知道(<$>) :: Functor f => (m -> n) -> (f m) -> (f n)
然后通过lambda演算的Beta转换，我可以算出lift2 (<$>)的类型是
(Applicative k, Functor f) => k (m -> n) -> k (f m) -> k (f n) 将 a 替换为 (m -> n)，将 b 替换为 (f m)，将 c 替换为 (f n)

当我想弄清楚lift2 (<$>) (,)的类型时，它阻止了我。
我知道(,) :: a -> b -> (a,b)
还有 lift2 (<$>) :: (Applicative k, Functor f) => k (m -> n) -> k (f m) -> k (f n).
Haskell如何将lift2 (<$>)应用到(,)？
lift2 (<$>)的第一个变量是Applicative k => k (m -> n).
要应用的值为(,) :: a -> b -> (a, b)
如何将 k、m、n 替换为 a、b？

GHCI 的答案是 lift2 (<$>) (,) :: Functor k => (a1 -> k a2) -> a1 -> k (a1, a2)，输入 :t lift2 (<$>) (,)。我自己无法推断出这个答案。

所以我有 2 个问题。
1.Could有人一步一步地告诉我推理吗？
2.In 这种情况下的转换似乎不是 lambda 演算中的 Beta 转换（可能是我错了）。转换是什么？

Answer 1

类型推导是一个机械的事情。^(*)关键是函数箭头->实际上是一个二进制 operator这里，右边关联（而应用/并列关联在左边）

因此A -> B -> C其实就是A -> (B -> C)其实就是(->) A ((->) B C)其实就是((->) A) (((->) B) C)。在这种形式中，很明显它由两部分组成，因此可以与例如匹配。 f t，注意等价物 f ~ ((->) A) 和 t ~ (((->) B) C)（或伪代码 f ~ (A ->)，以及正常表示法的 t ~ (B -> C)）。

当“应用”两个类型术语时，会执行 结构统一。两个术语的结构匹配，它们的子部分匹配，结果等价被标记为“替换”（... ~ ...）可用于执行并确保进一步简化结果类型术语（和如果因此发现某些不兼容性，则该类型将被拒绝）。

这遵循根植于 Modus Ponens 逻辑规则的一般结构/类型推导规则：

      A -> B     C
     --------------
           B         , where   A ~ C

因此，

liftA2 :: A f =>       (   a     -> b   -> c  ) -> f      a         -> f b -> f c
       (<$>) :: F h =>  (d -> e) -> h d -> h e
             (,) ::                                s -> (t -> (s, t))
---------------------------------------------------------------------------------
liftA2 (<$>) (,) ::                                                    f b -> f c
---------------------------------------------------------------------------------
                                  b ~ h d         f ~ (s->)
                        a ~ d->e         c ~ h e        a ~ t->(s,t)
                           \_ _ _ _ _ _ _ _ _ _ _ _ _ _ a ~ d->e
                       ----------------------------------------------------
                                                          d ~ t   e ~ (s,t)

liftA2 (<$>) (,) ::         f     b    -> f     c       
                  ~         (s -> b  ) -> (s -> c      )
                  ~  F h => (s -> h d) -> (s -> h e    )
                  ~  F h => (s -> h t) -> (s -> h (s,t))

（Applicative写A，Functor写F作为缩写）。当没有更多类型变量可供替换时，替换停止。

对于在每个步骤中选择要替换的类型变量有一定的自由度，但结果项将等同于一致重命名 的类型变量，无论如何。例如我们可以选择

                  ~  F h => (s -> h d) -> (s -> h e    )
                  ~  F h => (s -> h d) -> (s -> h (s,t))
                  ~  F h => (s -> h d) -> (s -> h (s,d))

在此过程中发现了 Applicative ((->) s) 约束。它会检查，因为此实例存在于所有 s。我们可以在 GHCi 的提示符下输入 :i Applicative 来查看它。查看它打印的实例列表，我们发现 instance Applicative ((->) a) -- Defined in `Control.Applicative'.

如果没有这样的实例，类型推导将停止并报告错误，它不会直接跳过它。但是由于约束成立，它就消失了，因为它不约束派生类型 Functor h => (s -> h t) -> (s -> h (s,t))。它已经“融入”了。

实例定义了 (f <*> g) x = f x $ g x 但类型派生中不需要定义本身，只需要它存在的事实。至于liftA2，则定义为

liftA2 h f g x = (h <$> f <*> g) x   -- for any Applicative (sans the `x`)
               = (h  .  f <*> g) x   -- for functions
               = (h . f) x (g x)
               = f x `h` g x         -- just another combinator

（是的，(<*>) = liftA2 ($)），所以

liftA2 (<$>) (,) g s = (,) s <$> g s
                     = do { r <- g s       -- in pseudocode, with
                          ; return (s, r)  --  "Functorial" Do
                          }

或者换句话说，liftA2 (<$>) (,) = \ g s -> (s ,) <$> g s。

类型Functor m => (s -> m t) -> s -> m (s,t)。其中是我们得出的结果。

^(*) 另见：

Haskell: how to infer the type of an expression manually

Haskell如何进行Beta转换派生类型？

How does Haskell perform Beta conversion to derive a type?

haskell

type-inference

lambda-calculus

hindley-milner

applicative