Applicative functor 的`(<*>)` 定义？

Question

一些Haskell源代码（参见ref）：

-- | Sequential application.
--
-- A few functors support an implementation of '<*>' that is more
-- efficient than the default one.
(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 id

-- | Lift a binary function to actions.
--
-- Some functors support an implementation of 'liftA2' that is more
-- efficient than the default one. In particular, if 'fmap' is an
-- expensive operation, it is likely better to use 'liftA2' than to
-- 'fmap' over the structure and then use '<*>'.
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

有三件事让我很困惑：

1) (<*>) 根据 liftA2 定义，其中 liftA2 根据 (<*>) 定义。它是如何工作的？我看不出明显的 "recursion-break" 案例...

2) id 是一个 a -> a 函数。为什么它作为 (a -> b -> c) 函数传递给 liftA2？

3) fmap id x 总是等于 x，因为仿函数必须保留适当的身份。因此 (<*>) (fmap id x) = (<*>) (x) 其中 x = f a - a 类型的函子本身（顺便说一句，a 类型的函子可以从纯范畴论的角度来解释吗？函子只是范畴之间的映射，它没有进一步的 "typification"... 似乎最好说 - “[=25 类型的容器=] 为定义明确的 Haskell 类型的每个实例定义了一个 (endo) 函子。所以 (<*>) (f a) 而根据定义 (<*>) 期望 f(a' -> b'): 因此，让它工作的唯一方法是故意将 a 绑定为 (a' -> b')。但是当我运行 :t \x -> (<*>) (fmap id x) 在 gchi ，它吐出一些令人兴奋的东西：f (a -> b) -> f a -> f b - 我无法解释。

谁能一步步解释它是如何工作的以及为什么它甚至可以编译？ P.S。如果需要，欢迎使用类别理论术语。

Answer 1

1) (<*>) is defined in terms of liftA2, where liftA2 is defined in terms of (<*>). How does it work? I see no obvious "recursion-break" case...

这不是递归。在您的 Applicative 实例中，您可以同时定义它们或只定义一个。如果您只定义 (<*>)，则 liftA2 是从 (<*>) 定义的，反之亦然。

2) id is an a -> a function. Why is it passed into liftA2 as an (a -> b -> c) function?

统一工作如下，

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 id

liftA2 :: (a -> b -> c) -> f a -> f b -> f c

id     :  u -> u 
liftA2 : (a -> (b -> c) -> f a -> f b -> f c
------------------------------------------------------
u = a
u = b->c

id     :  (b->c) -> (b->c)
liftA2 : ((b->c) -> (b->c)) -> f (b->c) -> f b -> f c
------------------------------------------------------

liftA2 id : f (b->c) -> f b -> f c

3.

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 h x = (<*>) (fmap h x)

将第一个参数从 f 重命名为 h，以防止混淆，因为 f 也显示在类型

中

h    :: a -> (b -> c)
x    :: f a
fmap :: (a -> d) -> f a -> f d
------------------------------
d  = b -> c
h    :: a -> (b->c)
x    :: f a
fmap :: (a -> (b->c)) -> f a -> f (b->c)
----------------------------------------
fmap h x :: f (b -> c)


fmap h x :: f (b -> c)
(<*>)    :: f (b -> c) -> f b -> f c
-------------------------------------
(<*>) fmap h x  :: f b -> f c

编辑：

一致性

为了显示两个公式的一致性，首先让我们先将 liftA2 改写成更简单的形式。我们可以使用下面的公式去掉 fmap 并只使用 pure 和 <*>

fmap h x = pure h <*> x

最好把所有的点都放在定义中。所以我们得到，

  liftA2 h u v  
= (<*>) (fmap h u) v
= fmap h u <*> v
= pure h <*> u <*> v

所以我们要检查

的一致性

u <*> v      = liftA2 id u v 
liftA2 h u v = pure h <*> u <*> v

首先我们需要属性那 pure id <*> u = u

  u <*> v 
= liftA2 id u v 
= pure id <*> u <*> v
= u <*> v

对于第二个，我们需要 liftA2 的属性。 applicative 的属性通常以 pure 和 <*> 的形式给出，所以我们需要先推导它。所需的公式来自 pure h <*> pure x = pure (h x).

  liftA2 h (pure x) v 
= pure h <*> pure x <*> v 
= pure (h x) <*> v
= liftA2 (h x) v

这需要 h : t -> a -> b -> c。一致性证明变成，

  liftA2 h u v 
= pure h <*> u <*> v
= pure h `liftA2 id` u `liftA2 id` v   
= liftA2 id (liftA2 id (pure h) u) v 
= liftA2 id (liftA2 h u) v 
= liftA2 h u v

Answer 2

在这里我不同意 GHC 开发人员的编码风格:)

我想说一个人永远不应该写

ap = liftA2 id

而是使用等价物

ap = liftA2 ($)

由于后者明确表示我们正在解除申请运营

（实际上，由于非常技术性的原因，GHC 开发人员无法在此内部模块中使用 $，正如下面评论中所指出的那样。因此，至少他们有一个很好的选择理由。 )

现在，您可能想知道为什么可以使用 id 而不是 $。正式地，我们有

($) f x
= f x
= (id f) x
= id f x

因此，eta-contracting x 然后 f，我们得到 ($) = id。

确实，($) 是 id 的 "special case"。

id :: a -> a
-- choose a = (b -> c) as a special case
id :: (b -> c) -> (b -> c)
id :: (b -> c) -> b -> c
($):: (b -> c) -> b -> c

因此，主要区别在于：id 是任何类型 a 上的身份，而 ($) 是任何功能类型 b -> c 上的 "identity" ].后者最好可视化为一个二元函数（应用），但它可以等效地被认为是一个函数类型上的一元函数（恒等式）。

Answer 3

1) (<*>) is defined in terms of liftA2, where liftA2 is defined in terms of (<*>). How does it work? I see no obvious "recursion-break" case...

每个实例负责覆盖两者中的至少一个。这在 class:

顶部的 pragma 中以机器可读的方式记录

{-# MINIMAL pure, ((<*>) | liftA2) #-}

此 pragma 声明实例编写者必须至少定义 pure 函数和其他两个函数中的至少一个。

id is an a -> a function. Why is it passed into liftA2 as an (a -> b -> c) function?

如果id :: a -> a，我们可以选择a ~ d -> e得到id :: (d -> e) -> d -> e。传统上，id 的这一特殊专业拼写为 ($) —— 也许您以前见过这个！

3) ...

我没有...实际上看到您陈述的事实有任何矛盾。所以我不确定如何为你解释矛盾。但是，你的符号有一些不妥之处，可能与你的思维错误有关，所以让我们简单谈谈。

你写

Thus (<*>) (fmap id x) = (<*>) (x) where x = f a.

这不太对； x 的类型对于某些 Functor f 是 f a，但不一定等于 f a.

by the way, how can a-typifying of the functor can be explained from the pure category theory's point of view? functor is just a mapping between categories, it has no further "typification"... seems like it is better to say - "a container of type a with an (endo)functor defined for each instance of assumed category Hask of well-defined Haskell types

函子由两部分构成：对象到对象的映射，以及与对象映射兼容的箭头到箭头的映射。在 Haskell Functor 实例声明中，如

instance Functor F where fmap = fmapForF

F 是从对象到对象的映射（源和目标类别中的对象都是类型，而 F 是接受类型并产生类型的东西）和fmapForF 是从箭头到箭头的映射。

I run :t \x -> (<*>) (fmap id x) in the gchi, it spits out something mind-blowing: f (a -> b) -> f a -> f b - which I fail to explain.

嗯，您已经观察到 fmap id x = x，这意味着 \x -> (<*>) (fmap id x) = \x -> (<*>) x。对于任何函数 f、f = \x -> f x（直到一些现在不重要的小问题），特别是 \x -> (<*>) (fmap id x) = (<*>)。所以 ghci 给你 (<*>) 的类型，因为它应该。

Answer 4

对于问题 1，您遗漏了一个非常重要的上下文。

class Functor f => Applicative f where
    {-# MINIMAL pure, ((<*>) | liftA2) #-}

您引用的那些定义属于class。这意味着实例可以覆盖它们。此外，MINIMAL pragma 表示为了工作，至少其中之一必须在实例中被覆盖。因此，每当在特定实例中覆盖一个递归时，就会发生递归中断。这就像 Eq class 定义 (==) 和 (/=) 的方式一样，您只需在手写实例中提供一个定义.

对于问题二，a -> b -> c 是 shorthand for a -> (b -> c)。因此它与（让我们重命名变量以避免冲突）d -> d 统一为 (b -> c) -> (b ->c)。（切线地，这也是 ($) 的类型。）

对于三个 - 你是完全正确的。继续简化！

\x -> (<*>) (fmap id x)
\x -> (<*>) x
(<*>)

所以 ghci 给你返回 (<*>) 的类型真的不应该是一个惊喜，不是吗？

Applicative functor 的`(<*>)` 定义？

`(<*>)` definition for the Applicative functor?

haskell

applicative