logo标签列表

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

haskellcurryingpointfree
29

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

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

由于(.)需要两个参数，我觉得(.).(.)应该是无效的，但它完全没有问题：

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

这里发生了什么？我意识到这个问题表述得不好……所有函数都只需要一个参数，这要归功于柯里化。也许更好的说法是类型不匹配。

2
(.) 实际上接收一个参数并返回一个接收一个参数的函数。 - Wes
4
@Wes 从不同角度看，你可以说它需要三个参数 (.) f g a = f (g a)。 - Ingo
1
好的一点是，因为 (.) (+1) (*2) 3 可以工作 :) - Wes
1
你应该阅读Conal Elliott的[Semantic Editor Combinators]（http://conal.net/blog/posts/semantic-editor-combinators），其中这被称为`(return.return)`，其中`return = (.)`以了解此类事物的一般想法。 - AndrewC
1
@AndrewC是对的。关于SEC的另一个总结，请参阅luqui在另一个问题中的精彩回答。 - ntc2
1
可能是重复的问题：如何理解“(.) . (.)”？ - Sergey K.
7个回答
31

我先让我们来玩一下机械证明的类型检查器。之后我会描述一种直观的思考方式。

我想将(.)应用于(.)，然后再将(.)应用于结果。第一个应用帮助我们定义一些变量的等价性。

((.) :: (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 ->)是一个Functor。

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

这应该看起来非常熟悉。这意味着fmap.fmap转换为(.) (.)。因此，(.) (.)让我们可以转换更深层次的(r ->)Functor的参数类型。 (r ->)Functor实际上是ReaderMonad，所以分层的Reader就像拥有多个独立的全局不可变状态。

或者就像拥有多个输入参数，这些参数不会受到fmap的影响。有点像在“仅结果”上组合新的续延函数(>1)的性质函数。

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

6
天啊，你的直觉部分突然让这更加清晰了。 - Vlad the Impala
哈哈，我很高兴！这绝对是正确的思考方式 :) - J. Abrahamson
嗨，J. Abrahamson，我不明白你在我的问题/答案http://stackoverflow.com/questions/24029422/how-to-derive-the-type-of中突出显示的“((.) (.) (.) :: (b'' -> c'') -> (a' -> b') -> (a' -> c'))”步骤。非常感谢您提供任何指针！ - Jerry
这是我使用之前几步的统一结果，将 b' = a'' -> b'' 和 c' = a'' -> c'' 统一起来。为了到达这一步，它必须成立，因此用其联合替换表达式是一个有效的步骤。 - J. Abrahamson
15

先不考虑类型，我们使用 λ演算。

  • 去除中缀符号：
    (.) (.) (.)

  • 进行 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 (d y z))))

  • 替换 f:
    (\ x -> (\ d y -> (\ z -> x (d y z))))

  • 恢复 λ符号：
    \ x d y z -> x (d y z)

如果你询问 GHCi，你会发现这个函数的类型是符合预期的。为什么呢？因为函数箭头是右结合的，以支持柯里化(currying)：类型 (b -> c) -> (a -> b) -> a -> c 的真正意义是 (b -> c) -> ((a -> b) -> (a -> c))。同时，类型变量 b 可以代表任何类型，包括函数类型。看到联系了吗？

你能解释一下如何使用这个“boobs运算符”吗？ - eccstartup
1
@eccstartup: (.:) = (.) . (.); countWhere = length .: filter; countWhere = (length .) . filter; countWhere (>5) [1..10] == 5@eccstartup：(.:) = (.) . (.); countWhere = length .: filter; countWhere = (length .) . filter; countWhere (>5) [1..10] == 5 - Jon Purdy
8
这里有一个更简单的例子来说明同样的现象：
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”，所以我们知道id的类型中的“a”应该是“Bool -> Bool”，因此我们知道这个id的发生类型为：
id :: (Bool -> Bool) -> (Bool -> Bool)

或者，使用更少的括号：
id :: (Bool -> Bool) -> Bool -> Bool

因此，这里的 id 实际上需要两个参数。

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

8

这是一个很好的例子，我认为更容易理解一般情况，然后再考虑特殊情况。所以我们来思考一下函数子。我们知道，函数子提供了一种在结构上映射函数的方式--

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]]
< p >“fmap.fmap”的类型是什么？< /p > 
>>> :t fmap.fmap
  :: (Functor g, Functor f) => (a -> b) -> f (g a) -> f (g b)

我们可以看到它映射了两个 functor 层，正如我们所希望的。但是请记住 (->) r 是一个 functor（从 r 到函数类型的类型，你可能更喜欢将其读作 (r ->)），它的 functor 实例是：
instance Functor ((->) r) where
  fmap f g = f . g

对于一个函数来说，fmap 就是函数组合！当我们组合两个 fmap 时，我们会映射到函数函子的两个级别。最初我们有一个类型为 (->) s ((->) r a) 的东西，它等同于 s -> r -> a，最终我们得到的是类型为 s -> r -> b 的东西，所以 (.).(.) 的类型必须是

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

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

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

接下来自然而然地可以将思考扩展到更长的fmap链，例如：

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

此处的 map 操作作用于三个嵌套层级的函子上，等效于与一个接受三个参数的函数进行组合：

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

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

这段代码将值为True插入到一个空映射中，键名为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)

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

很酷！这些例子很有趣，也很有帮助！ - eccstartup
4

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

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

从 (.) (.) (.) 可以更清楚地看出，第一个 (.) 将第二个 (.) 和第三个 (.) 作为其参数。

еҘҪзҡ„пјҢжҲ‘жҳҺзҷҪдәҶгҖӮжҲ‘зҡ„и§ӮзӮ№жҳҜпјҢ第дёҖдёӘеҸӮж•°зҡ„зұ»еһӢжҳҜ(b -> c)пјҢиҖҢдёҚжҳҜ(.)зҡ„зұ»еһӢгҖӮ - Vlad the Impala
1
@VladtheImpala，(.)的类型是(y -> z) -> (x -> y) -> (x -> z)。如果你让b成为(y -> z)，并让c成为(x -> y) -> (x -> z)，你会发现这两种类型实际上是兼容的。 - amalloy
4

是的，这是由于柯里化引起的。在Haskell中，所有函数都只接受一个参数，因此你正在组合的是每个组合(.)的第一部分调用，它获取其第一个参数（组成的第一个函数）。

3
（请先阅读有关函数组合、$运算符和点迹风格的我的回答。）

想象一下，你有一个简单的函数：它将两个数字相加，然后取反结果。我们将其称为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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接