为什么加入.(翻转fmap)有类型((A - > B) - > A) - >(A - > B) - > B？

Question

有些人在ghci玩弄着仿函数和monad,这让我得到了一个我希望更好理解其类型和行为的价值.

该类型的\x -> join . xIS (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).

为什么h有类型((A -> B) -> A) -> (A -> B) -> B？

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

为什么要评估h (\f -> f u) (\x -> x + v)整数u并v给出u + 2v每种情况？

Answer 1

简而言之:由于类型推断,Haskell知道m并且f实际上是部分实例化的箭头.

派生类型

好吧,让我们做数学.该函数join . (flip fmap)基本上是您给定的lambda表达式,\x -> join . x带有as参数(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避免两者之间的混淆可能是不同的类型).

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

  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

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

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

但是现在我们当然还没有获得这个功能的实现.然而,我们已经向前迈进了一步.

推导实施

既然我们现在知道了m ~ (->) (c -> d),我们知道应该查找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,然后在考虑预处理和原始视图的情况下进行处理(这是人类读者可以使用的解释).

现在join :: Monad m => m (m a) -> m a被实现为:

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

所以对于(->) rmonad来说,这意味着我们将其实现为:

-- 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箭头类型的实例定义为:

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.