haskell - 组合函数组合：(.).(.) 是如何工作的？

Question

(.)接受两个接受一个值并返回一个值的函数：

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

由于(.)需要两个参数，我觉得(.).(.)应该是无效的，但它很好：

(.).(.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

这里发生了什么？我意识到这个问题的措辞很糟糕......由于currying，所有函数实际上只需要一个参数。也许更好的说法是类型不匹配。

Answer 1

让我们首先为机械证明玩 typechecker。之后我将描述一种直观的思考方式。

我想申请(.)，(.)然后我会申请(.)结果。第一个应用程序帮助我们定义变量的一些等价性。

((.) :: (b -> c) -> (a -> b) -> a -> c) 
      ((.) :: (b' -> c') -> (a' -> b') -> a' -> c') 
      ((.) :: (b'' -> c'') -> (a'' -> b'') -> a'' -> c'')

let b = (b' -> c') 
    c = (a' -> b') -> a' -> c'

((.) (.) :: (a -> b) -> a -> c) 
      ((.) :: (b'' -> c'') -> (a'' -> b'') -> a'' -> c'')

然后我们开始第二个，但很快就卡住了......

let a = (b'' -> c'')

这是关键：我们想要let b = (a'' -> b'') -> a'' -> c''，但我们已经定义了b，因此我们必须尝试统一--- 尽可能匹配我们的两个定义。幸运的是，他们确实匹配

UNIFY b = (b' -> c') =:= (a'' -> b'') -> a'' -> c''
which implies 
      b' = a'' -> b''
      c' = a'' -> c''

有了这些定义/统一，我们可以继续申请

((.) (.) (.) :: (b'' -> c'') -> (a' -> b') -> (a' -> c'))

然后展开

((.) (.) (.) :: (b'' -> c'') -> (a' -> a'' -> b'') -> (a' -> a'' -> c''))

并清理它

substitute b'' -> b
           c'' -> c
           a'  -> a
           a'' -> a1

(.).(.) :: (b -> c) -> (a -> a1 -> b) -> (a -> a1 -> c)

老实说，这有点违反直觉。

---

这是直觉。先来看看fmap

fmap :: (a -> b) -> (f a -> f b)

它将功能“提升”为Functor. 我们可以反复应用

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

允许我们将功能提升到越来越深的Functors.

事实证明，数据类型(r ->)是 a Functor。

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

这应该看起来很熟悉。这意味着fmap.fmap转换为(.).(.). 因此，(.).(.)只是让我们将参数类型转换得越来越深(r ->) Functor。(r ->) Functor实际上就是Reader Monad，所以分层的Readers 就像拥有多种独立的全局、不可变状态。

或者像有多个不受fmaping 影响的输入参数。有点像在（> 1）arity函数的“只是结果”上编写一个新的延续函数。

---

最后值得注意的是，如果您认为这些东西很有趣，它构成了在 Control.Lens 中派生镜头背后的核心直觉。

Answer 2

让我们暂时忽略类型，只使用 lambda 演算。

• 脱糖中缀符号：
  (.) (.) (.)

• Eta-展开：
  (\ a b -> (.) a b) (\ c d -> (.) c d) (\ e f -> (.) e f)

• 内联 的定义(.)：
  (\ a b x -> a (b x)) (\ c d y -> c (d y)) (\ e f z -> e (f z))

• 替代品a：
  (\ b x -> (\ c d y -> c (d y)) (b x)) (\ e f z -> e (f z))

• 替代品b：
  (\ x -> (\ c d y -> c (d y)) ((\ e f z -> e (f z)) x))

• 替代品e：
  (\ x -> (\ c d y -> c (d y)) (\ f z -> x (f z)))

• 替代品c：
  (\ x -> (\ d y -> (\ f z -> x (f z)) (d y)))

• 替代品f：
  (\ x -> (\ d y -> (\ z -> x (d y z))))

• Resugar lambda 符号：
  \ x d y z -> x (d y z)

如果你问 GHCi，你会发现这具有预期的类型。为什么？因为函数箭头是右关联的以支持柯里化：类型(b -> c) -> (a -> b) -> a -> c真的意味着(b -> c) -> ((a -> b) -> (a -> c)). 同时，类型变量b可以代表任何类型，包括函数类型。看到连接了吗？

Answer 3

这是我认为首先掌握更一般的情况，然后考虑具体情况更简单的案例之一。所以让我们考虑函子。我们知道仿函数提供了一种将函数映射到结构上的方法——

class Functor f where
  fmap :: (a -> b) -> f a -> f b

但是如果我们有两层函子呢？例如，列表列表？在这种情况下，我们可以使用两层fmap

>>> let xs = [[1,2,3], [4,5,6]]
>>> fmap (fmap (+10)) xs
[[11,12,13],[14,15,16]]

但是模式f (g x)完全一样，(f . g) x所以我们可以写

>>> (fmap . fmap) (+10) xs
[[11,12,13],[14,15,16]]

是什么类型的fmap . fmap？

>>> :t fmap.fmap
  :: (Functor g, Functor f) => (a -> b) -> f (g a) -> f (g b)

我们看到它映射了我们想要的两层仿函数。但现在请记住，这(->) r是一个仿函数（来自 的函数类型r，您可能更喜欢将其读为(r ->)），它的仿函数实例是

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

对于一个函数来说，fmap就是函数组合！当我们组合两个fmaps 时，我们映射了函数函子的两个层次。我们最初有一些类型(->) s ((->) r a)，它等价于s -> r -> a，我们最终有一些类型s -> r -> b，所以类型(.).(.)必须是

(.).(.) :: (a -> b) -> (s -> r -> a) -> (s -> r -> b)

它采用它的第一个函数，并使用它来转换第二个（双参数）函数的输出。例如，该函数((.).(.)) show (+)是一个有两个参数的函数，它首先将其参数相加，然后将结果转换为Stringusing show：

>>> ((.).(.)) show (+) 11 22
"33"

---

然后有一个自然的概括来考虑更长的链fmap，例如

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

它映射了三层仿函数，相当于用三个参数组成的函数：

(.).(.).(.) :: (a -> b) -> (r -> s -> t -> a) -> (r -> s -> t -> b)

例如

>>> import Data.Map
>>> ((.).(.).(.)) show insert 1 True empty
"fromList [(1,True)]"

它将值True插入到带有 key 的空映射中1，然后将输出转换为带有 的字符串show。

---

这些函数通常很有用，所以有时你会看到它们被定义为

(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(.:) = (.).(.)

这样你就可以写

>>> let f = show .: (+)
>>> f 10 20
"30"

当然，(.:)可以给出一个更简单、更有针对性的定义

(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(f .: g) x y = f (g x y)

这可能有助于在(.).(.)某种程度上揭开神秘面纱。

Answer 4

这是相同现象的一个更简单的示例：

id :: a -> a
id x = x

id 的类型表示 id 应该采用一个参数。事实上，我们可以用一个参数来调用它：

> id "hello" 
"hello"

但事实证明，我们也可以用两个参数来称呼它：

> id not True
False

甚至：

> id id "hello"
"hello"

到底是怎么回事？理解的关键id not True是先看id not。显然，这是允许的，因为它将 id 应用于一个参数。的类型not是Bool -> Bool，所以我们知道afrom id 的类型应该是Bool -> Bool，所以我们知道这个 id 的出现有类型：

id :: (Bool -> Bool) -> (Bool -> Bool)

或者，用更少的括号：

id :: (Bool -> Bool) -> Bool -> Bool

所以这个 id 的出现实际上需要两个参数。

同样的推理也适用于id id "hello"和(.) . (.)。

Answer 5

你是对的，(.)只需要两个参数。您似乎只是对 haskell 的语法感到困惑。在表达式(.).(.)中，实际上是中间的点将另外两个点作为参数，就像在表达式100 + 200中一样，可以写成(+) 100 200。

(.).(.) === (number the dots)
(1.)2.(3.) === (rewrite using just syntax rules)
(2.)(1.)(3.) === (unnumber and put spaces)
(.) (.) (.) ===

应该更清楚的(.) (.) (.)是，第一个(.)将第二个(.)和第三个(.)作为它的论点。

Answer 6

是的，这是由于咖喱。(.)因为 Haskell 中的所有函数都只接受一个参数。您正在编写的是对每个组合的第一个部分调用，该调用(.)采用其第一个参数（组合的第一个函数）。

Answer 7

^{（首先阅读我关于函数组合、$ 运算符和无点样式的答案。）}

想象一下，你有一个简单的函数：它将 2 个数字相加，然后将结果取反。我们称之为foo：

foo a b = negate (a + b)

现在让我们一步一步让它变得无点，看看我们最终得到了什么：

foo a b = negate $ a + b
foo a b = negate $ (+) a b
foo a b = negate $ (+) a $ b
foo a b = negate . (+) a $ b
foo a   = negate . (+) a -- f x = g x is equivalent to f = g
foo a   = (.) negate ((+) a) -- any infix operator is just a function
foo a   = (negate.) ((+) a) -- (2+) is the same as ((+) 2)
foo a   = (negate.) $ (+) a
foo a   = (negate.) . (+) $ a
foo     = (negate.) . (+)
foo     = ((.) negate) . (+)
foo     = (.) ((.) negate) (+) -- move dot in the middle in prefix position
foo     = ((.) ((.) negate)) (+) -- add extra parentheses

(.) ((.) negate)现在让我们更仔细地分析表达式。它是函数的部分应用(.)，它的第一个参数是((.) negate). 我们可以进一步改造它吗？我们可以：

(.) ((.) negate)
(.) . (.) $ negate -- because f (f x) is the same as (f . f) x
(.)(.)(.) $ negate
((.)(.)(.)) negate

(.).(.)等价于(.)(.)(.)，因为在第一个表达式中，中间的点可以移动到前缀位置并用括号括起来，从而产生第二个表达式。

现在我们可以重写我们的foo函数：

foo = ((.).(.)) negate (+)
foo = ((.)(.)(.)) negate (+) -- same as previous one
foo = negate .: (+)
  where (.:) = (.).(.)

现在你知道这(.).(.)相当于(\f g x y -> f (g x y))：

(\f g x y -> f (g x y)) negate (+) 2 3 -- returns -5
((.).(.)) negate (+) 2 3 -- returns -5