haskell - 多次调用 applyTwice 时无法理解结果

Question

有很多问题基于applyTwice ，但与我的问题无关。我了解 applyTwice函数定义如下:

applyTwice :: (a -> a) -> a -> a
applyTwice f a = f (f a)

应用一个函数两次。所以如果我有一个增量函数:

increment x = x + 1

做

applyTwice increment 0

我得到 2。但我不明白这些结果:

applyTwice applyTwice applyTwice increment 0 -- gives 16
applyTwice applyTwice applyTwice applyTwice increment 0 -- gives 65536
applyTwice applyTwice applyTwice applyTwice applyTwice increment 0 -- stack overflow

我也知道

twice = applyTwice applyTwice increment
applyTwice twice 0 -- gives 8

我根本无法理解这些结果，如果有人能解释一下，我会很高兴的。如果这是基本的东西，我很抱歉，因为我刚刚学习 Haskell。

Answer 1

让我们使用非正式的符号

iter n f = f . f . f . ....  -- n times

您的 applyTwice那么就是 iter 2 .
从定义中，我们立即得到:

(iter n . iter m) f 
= iter n (iter m f)
= (f.f. ...) . ... . (f.f. ...)   -- n times (m times f)
= iter (n*m) f

因此，eta 承包，

iter n . iter m = iter (n*m)    -- [law 1]

我们还有

iter n (iter m) 
=  -- definition
iter m . iter m . .... . iter m    -- n times
= -- law 1
iter (m*m* ... *m)                 -- n times
= -- power
iter (m^n)                         -- [law 2]

然后我们有，写 t对于 applyTwice :

t = iter 2

t t 
= -- previous equation
iter 2 (iter 2)
= -- law 2
iter (2^2)

t t t
= -- left associativity of application
(t t) t
= -- previous equation
iter (2^2) (iter 2)
= -- law 2
iter (2^(2^2))

t t t t
= -- left associativity of application
(t t t) t
= -- previous equation
iter (2^(2^2)) (iter 2)
= -- law 2
iter (2^(2^(2^2)))

等等。