Intuitive way of thinking about function composition and partial application

Question

This is a question I found in SICP, translated to 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?

This is my thought process:

Applying double to double results in a function that quadruples a given function.

Supplying double to this quadrupling function results in a function that applies a given function 8 times.

Therefore, the result should be 8. But the result is 16.

By substituting the double function and solving it by brute-force, I get 16 but am unable to intuitively grasp why. I understand function composition and partial applicatin in isolation, but not in this context.

What is happening here?

Answer 1

TL;DR: functional composition is like multiplication. squaring something 4 times means raising it to the 16 th power. double should have been named squared.

---

This is very easy with equational notation:

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

where

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

by definition. Then, substituting the above equation's right-hand side for its left-hand side, and even left-hand side for its right-hand side, as it suits us, we have

double(double)(double)(succ)(0)                   -- double(double) = 
=
(double . double)(double)(succ)(0)                --           = double^2
=
double(double(double))(succ)(0)                   -- (double^2)(double) =
=                                   
double((double . double))(succ)(0)                --           = double(double^2)
=
((double . double) . (double . double))(succ)(0)       --      = double^4 !!

(no succ is involved, yet!). Deriving f = g from f(x) = g(x) is known as eta-contraction.

Function composition is associative,

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

so we continue

((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

So this comes down to not mixing up (f . g) and f(g).

Also, that doubling the multiplication chain means squaring.