haskell - 无法理解以未部分应用的函数作为参数提供的高阶函数调用的结果

Question

我有一个高阶函数声明来应用作为参数给出的函数两次:

twice :: (a -> a) -> a -> a
twice f x = f (f x)

困惑来自于这次 GHCi session :

*Main> let _4 = twice twice
*Main> let __4 = twice twice (*2)
*Main> let _16 = _4 _4
*Main> let __16 = _4 __4
*Main> _16 (*2) 2
231584178474632390847141970017375815706539969331281128078915168015826259279872
*Main> __16 2
131072

__16 很清楚，因为发生的只是这个函数调用的“乘法”，所以我们实际上会得到 (2 ^ 16) * 2 调用后。据我所知，发生这种情况是因为作为参数给出的函数已经部分应用，因此 __4 和 __16 的类型是 (Num a) => a -> a。

但是使用给定函数和整数参数调用 _16 的结果只会让我感到困惑。我可以理解 _4 和 _16 的类型是原始的(等于 twice 函数的签名，但嵌套在引擎盖下)，但它让我不知道为什么结果差异如此之大。在提供未部分应用为参数的函数后，我只是无法获取程序的语义。有人可以解释一下为什么这个数字这么大吗？

Answer 1

查看减少 __16 2一点:

__16 2 = _4 __4 2
       = (twice twice) (twice twice (*2)) 2
       = twice (twice (twice twice (*2)) 2
       = twice (twice (twice (twice (*2)) 2

相比

_16 (*2) 2 = _4 _4 (*2) 2
           = (twice twice) (twice twice) (*2) 2
           = twice (twice (twice twice)) (*2) 2

通知 __16版本，你只是直接将申请次数加倍(*2)与每个 twice 。如果你仔细观察，你会发现_16版本的括号略有不同。您首先将加倍操作本身加倍，然后将其应用到 (*2)和2 .

减少的前几步_16 (*2) 2可能看起来像这样，从上面开始

     twice (twice (twice twice)) (*2) 2
   = twice (twice (\x -> twice (twice x))) (*2) 2
   = twice (\z -> (\x -> twice (twice x)) ((\y -> twice (twice y)) z)) (*2) 2
   = twice (\z -> (\x -> twice (twice x)) (twice (twice z))) (*2) 2
   = twice (\z -> twice (twice (twice (twice z)))) (*2) 2
   = (\z -> twice (twice (twice (twice z)))) ((\w -> twice (twice (twice (twice w)))) (*2)) 2
   = ((\z -> twice (twice (twice (twice z)))) (twice (twice (twice (twice (*2)))))) 2
   = twice (twice (twice (twice (twice (twice (twice (twice (*2)))))))) 2
   = ...

最里面twice (*2)给你两个(*2) s。下一个twice将其加倍至 4 (*2) s，之后的那个再次加倍到 8 (*2)等。有八个twice s 在上面的表达式中，所以你最终得到 2^8 = 256 (*2) s，所以结果是2 * (2^(2^8)) = 2 * (2^256) = 231584178474632390847141970017375815706539969331281128078915168015826259279872 .