函数组合和偏应用的直观思考方式

Question

这是我在 SICP 中找到的问题，翻译为 JavaScript。

let double = function(f) {
  return function(x) {
    return(f(f(x)))
  }
}

let succ = x => x + 1
let ans = double(double)(double)(succ)(0)
console.log(ans) // What's the output?

这是我的思考过程：

将 double 应用于 double 会产生一个函数，该函数是给定函数的四倍。

向这个四倍函数提供 double 会产生一个应用给定函数 8 次的函数。

因此，结果应该是8。但结果是16。

通过代入双函数并通过暴力求解，我得到了 16，但无法直观地理解为什么。我理解孤立的函数组合和部分应用程序，但不是在这种情况下。

这里发生了什么？

Answer 1

这不是最容易解释的事情，但我会尽力而为。我将使用 Scheme，因为这是我熟悉的。

(define (double f)
  (lambda (x)
    (f (f x))))

(define (succ x)
  (+ x 1))

(double double)
; evaluates to
(lambda (x)
  (double (double x)))
; so
((double double) succ)
; is the same as
(double (double succ))
; which is the same as
(double (lambda (x)
          (succ (succ x))))
; lets call that last lambda inc2
; the last statement then equals
(inc2 (inc2 x))
; so when we call 
(((double double) succ) 0)
; we get 4 calls to succ, and the result is 4

; now let's add another double
((double double) double)
; this evaluates to
((lambda (x)
   (double (double x)))
 double)
; or
(double (double double))
; or
(double (lambda (x)
          (double (double x))))
; lets call that last lambda quadruple
(double quadruple)
; or
(lambda (x)
  (quadruple (quadruple x)))

; 4x4 is 16 and so when we call
((((double double) double) succ) 0)
; we call succ 16 times

; this in contrast to
((double (double (double succ))) 0)
; which will in fact return 8

这归结为你调用 double 的方式。每次调用 double 作为参数 double 时，调用量增加到 2^（对 double 的调用量）。相反，当您在已经翻倍的函数上调用 double 时，您会得到预期的行为，而且调用量确实每次都翻倍。

很抱歉，如果这不是很清楚，我找不到直观的方式来解释。

Answer 2

这真的是一道关于结合律的题。在 Racket 中（在 JS 中工作相同），比较这些：

#lang racket

(define (double f) (λ (x) (f (f x))))

((double (double (double add1))) 0) ; => 8, as you hypothesized
((((double double) double) add1) 0) ; => 16, as you observed.

所以唯一的区别是函数应用是left-associative。

如果您使用 JS 并添加更多括号以强制 right-associativity，您应该会看到您期望的“8”。

Answer 3

TL;DR: 函数组合就像乘法。平方 4 次意味着将其提升到 16 次方。 double 应该被命名为 squared.

使用等式表示法非常容易：

double(f)(x) = f(f(x)) = (f . f)(x)               -- (f^2)(x) ... why? see below:

哪里

(f . g)(x) = f(g(x))

根据定义。然后，用上面等式的 right-hand 边代替它的 left-hand 边，甚至用 left-hand 边代替它的 right-hand 边，因为它适合我们，我们有

<b>double(double)</b>(double)(succ)(0) -- double(double) =
=
<b>(double.double)</b>(double)(succ)(0) -- = double^2
=
双(<b>双(双)</b>)(成功)(0) -- (双^2)(双) =
=
double(<b>(double.double)</b>)(succ)(0) -- = double(double^2)
=
(<b>(double.double)</b>.<b>(double.double)</b>)(succ)(0) -- = double^4!!

（尚未涉及 succ！）。从 f(x) = g(x) 导出 f = g 被称为 eta-contraction.

函数组合是关联的，

((f . g) . h)(x) = (f . g)(h(x)) = f(g(h(x)))
                 = f( (g . h)(x) )
                 = (f . (g . h))(x)

所以我们继续

((double . double) . (double . double))(succ)(0)
=
(double . double . double . double)(succ)(0)   -- = f . f . f . f = f^4
=
double(double(double(double(succ))))(0)    -- = (double^4)(succ)
=
double(double(double(succ^2)))(0)     -- = (double^3)(succ^2) , succ^2 = succ . succ
=
double(double(succ^4))(0)       -- = (double^2)(succ^4)
=
double(succ^8)(0)         -- = (double^1)(succ^8)
=
(succ^16)(0)         -- = (double^0)(succ^16) = identity(succ^16) = succ^16
=
16

所以这归结为不要混淆 (f . g) 和 f(g)。

此外，加倍乘法链意味着平方。

函数组合和偏应用的直观思考方式

Intuitive way of thinking about function composition and partial application

javascript

closures

scheme

sicp

function-composition