haskell - 为什么要加入。 (flip fmap) 有类型 ((A -> B) -> A) -> (A -> B) -> B?

Question

一些在 ghci 中玩弄仿函数和 monad 的行为让我找到了一个我想更好地理解其类型和行为的值。
\x -> join . x的类型是 (Monad m) => (a -> m (m b)) -> (a -> m b)和 \y -> y . (flip fmap) 的类型是 (Functor f) => ((a -> b) -> f b) -> (f a -> c) .

ghci 8.2.2 版允许定义 h = join . (flip fmap) .

Why does h have type ((A -> B) -> A) -> (A -> B) -> B?

特别是，为什么仿函数和单子(monad)约束消失了？这真的是正确和预期的行为吗？作为后续，我还想问:

Why does evaluating h (\f -> f u) (\x -> x + v) for integers u and v give u + 2v in every case?

Answer 1

总之 : 由于类型推导，Haskell 知道 m和 f实际上是一个部分实例化的箭头。

派生类型

好吧，让我们算一下。函数join . (flip fmap)基本上是你给定的 lambda 表达式 \x -> join . x作为参数 (flip fmap) ， 所以:

h = (\x -> join . x) (flip fmap)

现在 lambda 表达式具有类型:

(\x -> join . x) :: Monad m =>   (a -> m (m b)) -> (a -> m b)

现在论据 flip fmap有类型:

flip fmap        :: Functor f => f c -> ((c -> d) -> f d)

(我们在这里使用 c 和 d 而不是 a 和 b 以避免混淆两种可能不同的类型)。

这意味着 flip fmap 的类型与 lambda 表达式的参数类型相同，因此我们知道:

  Monad m =>   a   -> m (m b)
~ Functor f => f c -> ((c -> d) -> f d)
---------------------------------------
a ~ f c, m (m b) ~ ((c -> d) -> f d)

所以我们现在知道 a与 f c 具有相同的类型(这是波浪号 ~ 的含义)。

但是我们必须做一些额外的计算:

  Monad m =>   m (m b)
~ Functor f => ((c -> d) -> f d)
--------------------------------
m ~ (->) (c -> d), m b ~ f d

因此我们知道 m与 (->) (c -> d) 相同(基本上这是一个我们知道输入类型的函数，这里是 (c -> d) ，输出类型是 m 的类型参数。

这意味着 m b ~ (c -> d) -> b ~ f d , 所以这意味着 f ~ (->) (c -> d)和 b ~ d .一个额外的结果是，由于 a ~ f c , 我们知道 a ~ (c -> d) -> c
因此，列出我们得出的内容:

f ~ m
m ~ (->) (c -> d)
b ~ d
a ~ (c -> d) -> c

所以我们现在可以“特化”我们的 lambda 表达式和我们的 flip fmap 的类型。功能:

(\x -> join . x)
    :: (((c -> d) -> c) -> (c -> d) -> (c -> d) -> d) -> ((c -> d) -> c) -> (c -> d) -> d
flip fmap
    ::  ((c -> d) -> c) -> (c -> d) -> (c -> d) -> d

和 flip fmap 的类型现在与 lambda 表达式的参数类型完全匹配。所以 (\x -> join . x) (flip fmap) 的类型是 lambda 表达式类型的结果类型，即:

(\x -> join . x) (flip fmap)
    :: ((c -> d) -> c) -> (c -> d) -> d

但是现在我们当然还没有得到这个函数的实现。然而，我们已经更进一步了。

派生实现

因为我们现在知道 m ~ (->) (c -> d) ，我们知道我们应该查找 arrow instance of a monad :

instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r

所以对于给定的函数 f :: r -> a , 作为左操作数和函数 k :: a -> (r -> b) ~ a -> r -> b作为操作数，我们构造了一个映射变量 x 的新函数至 k申请 f申请 x , 和 x .因此，这是一种对输入变量 x 执行某种预处理的方法。 ，然后在考虑预处理和原始 View 的情况下进行处理(这是人类读者可以使用的解释)。

现在 join :: Monad m => m (m a) -> m a 是 implemented as :

join :: Monad m => m (m a) -> m a
join x = x >>= id

所以对于 (->) r monad，这意味着我们将其实现为:

-- specialized for `m ~ (->) a
join f = \r -> id (f r) r

从 id :: a -> a (恒等函数)返回它的参数，我们可以进一步简化为:

-- specialized for `m ~ (->) a
join f = \r -> (f r) r

或更清洁:

-- specialized for `m ~ (->) a
join f x = f x x

所以它基本上被赋予了一个函数 f , 然后将参数两次应用于该函数。

此外，我们知道 Functor箭头类型的实例是 defined as :

instance Functor ((->) r) where
    fmap = (.)

所以它基本上被用作函数结果的“后处理器”:我们构造一个新函数，它将对给定函数进行后处理。

所以现在我们已经为给定的 Functor 专门化了足够多的函数。/ Monad ，我们可以将实现推导出为:

-- alternative implementation
h = (.) (\f x -> f x x) (flip (.))

或者通过使用更多的 lambda 表达式:

h = \a -> (\f x -> f x x) ((flip (.)) a)

我们现在可以进一步专门化为:

h = \a -> (\f x -> f x x) ((\y z -> z . y) a)

-- apply a in the lambda expression
h = \a -> (\f x -> f x x) (\z -> z . a)

-- apply (\z -> z . a) in the first lambda expression
h = \a -> (\x -> (\z -> z . a) x x)

-- cleaning syntax
h a = (\x -> (\z -> z . a) x x)

-- cleaning syntax
h a x = (\z -> z . a) x x

-- apply lambda expression
h a x = (x . a) x

-- remove the (.) part
h a x = x (a x)

所以 h基本上有两个参数: a和 x ，然后用 a 执行函数应用作为函数和 x作为参数，并将输出传递给 x再次发挥作用。

示例使用

作为示例用法，您使用:

h (\f -> f u) (\x -> x + v)

或者更好:

h (\f -> f u) (+v)

所以我们可以这样分析:

   h (\f -> f u) (+v)
-> (+v) ((\f -> f u) (+v))
-> (+v) ((+v) u)
-> (+v) (u+v)
-> ((u+v)+v)

所以我们添加 u+v至 v .