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

Question

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

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

混淆来自这个 GHCi 会话：

*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 就很清楚了，因为发生的只是这个函数调用的 "multiplying"，所以我们实际上会在调用后得到 (2 ^ 16) * 2。据我所知，这是因为作为参数给出的函数已经部分应用，所以 __4 和 __16 的类型是 (Num a) => a -> a.

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

Answer 1

对于丘数，两个数的应用a b等同于指数b^a。所以，_4 _4 对应于 4^4=256，而不是 16.

粗略地说：_4 f 表示 f . f . f . f，即 "doing f four times, or " 将 f 乘以四。因此，_4 _4 f 表示 "multiplying f by four, four times"，因此4^4.

确实：

> 2^256 * 2 :: Integer
231584178474632390847141970017375815706539969331281128078915168015826259279872

Answer 2

正在考虑减少 __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 版本，您只是将每个 twice 应用 (*2) 的次数直接加倍。如果仔细观察，您会发现 _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)。下一个 twice 将其加倍至 4 (*2)s，之后的一个将其再次加倍至 8 (*2)s 等等。上面的表达式有8个twice，所以你最后得到2^8 = 256个(*2)，所以结果是2 * (2^(2^8)) = 2 * (2^256) = 231584178474632390847141970017375815706539969331281128078915168015826259279872.

Answer 3

`twice` 不是 "twice"，而是 "squared" :

(^.) :: (a -> a) -> Int -> (a -> a)
(f^.n) x = foldr ($) x [f | _ <- [1..n]]   

((^.m) . (^.n)) f x = ((f^.n)^.m) x     
                  = foldr ($) x [f^.n | _ <- [1..m]]
                  = (f^.(m * n)) x
                  = (^.(m * n)) f x      

twice = (^.2)      -- f^.2 = f . f      f squared

_4   = twice twice
_4 f = (^.2) (^.2) f = ((^.2) . (^.2)) f = (f^.2)^.2 = f^.4    
_4   = (^.4)

       (^.3) (^.3) f = ((^.3) . (^.3) . (^.3)) f =
                     = ((^.3) . (^.3)) (f^.3)
                     =  (^.3) ((f^.3)^.3)
                     =   ((f^.3)^.3)^.3 = f^.(3*3*3) = f^.(3^3) = f^27 

       (^.4) (^.3) f = (((f^.3)^.3)^.3)^.3 = f^.(3*3*3*3) = f^.(3^4) = f^81

一般来说，

       (^.m) (^.n) f = f^.(n^m)

函数组合是乘法，应用是（逆）幂。

因此我们有

_16 f x = _4 _4 f x = (^.4) (^.4) f x = (f^.(4^4)) x = (f^.256) x

_16 (*2) 2 = ((*2)^.256) 2 = (* (2^256)) 2 = 2^257

*Main> _16 (*2) 2
231584178474632390847141970017375815706539969331281128078915168015826259279872

*Main> 2^257
231584178474632390847141970017375815706539969331281128078915168015826259279872

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

Can't understand the result of the high-order function invocation provided with not partially applied function as an argument

haskell

functional-programming

currying

partial-application

`twice` 不是 "twice"，而是 "squared" :

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

Can't understand the result of the high-order function invocation provided with not partially applied function as an argument

haskell

functional-programming

currying

partial-application

twice 不是 "twice"，而是 "squared" :

`twice` 不是 "twice"，而是 "squared" :