多次调用applyTwice时无法理解结果
有很多基于 的问题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。
回答
让我们使用非正式的符号
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)))
等等。