如何手动推断'(.)的类型.(.).(.)"？

Question

在Edward Kmett的演讲中,Lenses,Folds和Traversals,在幻灯片"The Power is the Dot"中,他展示的(.) . (.) . (.)是

(a -> b) -> (c -> d -> e -> a) -> c -> d -> e -> b

我可以通过在GHCI中显示它的类型来看到它.但我也想知道原因.我想了解的另一件事是为什么有在从参数中经常换着花样(.)来(.) . (.)和(.) . (.) . (.):

(.)             :: (a -> b) -> (c ->           a) -> c ->           b
(.) . (.)       :: (a -> b) -> (c -> d ->      a) -> c -> d ->      b
(.) . (.) . (.) :: (a -> b) -> (c -> d -> e -> a) -> c -> d -> e -> b

PS我试图(.) . (.)通过扩展函数定义来解决自己(.) . (.).应用(.)我得到的定义后:

\x y z t -> x ((y z) t)

所以我推断了类型:

x :: a -> b
y :: c -> d -> a
z :: c
t :: d

但是我迷路了(.) . (.) . (.).而且我不知道这是否是进行手动类型推断的正确方法.

Answer 1

有功能,

instance Functor ((->) r) where
   -- fmap :: (a -> b) ->   f   a  ->   f   b
   --         (a -> b) -> (r -> a) -> (r -> b)
   fmap          p           q         x = p (q x)   -- fmap = (.)

所以你实际拥有的是fmap . fmap . fmap:

fmap               :: (a -> b) -> f       a   -> f       b
fmap . fmap        :: (a -> b) -> f (g    a)  -> f (g    b)
fmap . fmap . fmap :: (a -> b) -> f (g (h a)) -> f (g (h b))

是的

 (a -> b) -> (c -> (d -> (e -> a))) -> (c -> (d -> (e -> b)))   ~
 (a -> b) -> (c ->  d ->  e -> a)   -> (c ->  d ->  e -> b)     

为什么fmap . fmap :: (a -> b) -> f (g a) -> f (g b)？因为,

(fmap . fmap) foo = fmap (fmap foo)
{-
fmap            :: (a  ->  b) -> f a     -> f b
foo             ::  a  ->  b
fmap foo        ::               f a     -> f b
fmap foo        :: g a -> g b
fmap (fmap foo) ::               f (g a) -> f (g b)
-}

机械类型推导是关于类型变量的替换和一致重命名.在此处或此处查看更多信息.

Answer 2

(.) . (.) . (.) 分两步减少:首先减少没有圆括号的点:

((.) . (.) . (.)) f = (.) ((.) ((.) f))
                    = (.) ((.) (f .))
                    = (.) ((f .) .)
                    = ((f .) .) .)

第二个减少剩余的表达

((f .) .) .) g = ((f .) .) . g
               = \x -> ((f .) .) (g x)
               = \x -> (f .) . g x
               = \x y -> (f .) (g x y)
               = \x y -> f . g x y
               = \x y z -> f (g x y z)

所以首先n用n - 1圆点在括号中组成点.然后你将这个结构应用于函数f :: a -> b,g并得到(...((f .) .) ... .) g每个点对应一个g接收的参数的位置- 这就是为什么有一个模式:括号中的每个点处理一个参数,g你需要另一个点来组成这个点与之前的所有.在所有减少后,表达式变为

\x1 x2 ... xn -> f (g x1 x2 ... xn)

它的类型很明显.

一件好事是,如果我们有后缀运算符,我们可以编写(代码在Agda中)

open import Function renaming (_??_ to _?_) using ()

_% = _?_

postulate
  a b c d e : Set
  f : a -> b
  g : c -> d -> e -> a

fg : c -> d -> e -> b
fg = f % % ? g

而不是((f .) .) . g.