关于功能组合和部分应用的直观思维方式

Question

这是我在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

这确实是一个关于联想性的问题。在球拍中(在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.

因此，唯一的区别是函数应用程序是左关联的。

如果您使用JS并添加更多的parens来强制右结合，您应该会看到您期望的"8“。

Answer 2

这不是最容易解释的事情，但我会尽我所能的。我将使用方案，因为这是我所熟悉的。

(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 with as参数double时，调用的数量就会增加到2^(调用量增加到double)。当你用一个已经加倍的函数调用double时，你会得到你期望的行为，而每次调用的数量实际上都是原来的两倍。

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