代码之家 › 专栏 › 技术社区 › nyarian

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

partial-application currying functional-programming haskell

nyarian · 技术社区 · 8 年前

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 ,因为所发生的只是这个函数调用的“乘法”,所以我们实际上得到 (2 ^ 16) * 2 (Num a) => a -> a .

但是调用 _16 _4 和生的(等于 twice 函数的签名,但它们嵌套在引擎盖下),但它并没有告诉我为什么结果会有如此大的差异。在提供了一个没有作为参数部分应用的函数之后,我无法获得程序的语义。有人能解释一下为什么这个数字这么大吗?

3 回复 | 直到 8 年前

David Young 8 年前

在看一本书 __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。下一个 两次 加倍到4 (*2) s、之后的那一个再加倍到8 (*2) 两次 在上面的表达式中是s,因此得到2^8=256 s、所以结果是 2 * (2^(2^8)) = 2 * (2^256) = 231584178474632390847141970017375815706539969331281128078915168015826259279872

chi 8 年前

对于教会数词,两个数词的应用 a b b^a . 所以, _4 _4 对应于 4^4=256 16 .

大致: _4 f 方法 f . f . f . f ,即“正在做” f f 四英寸。所以, _4 _4 f 意思是“相乘” f 4^4 .

> 2^256 * 2 :: Integer
231584178474632390847141970017375815706539969331281128078915168015826259279872

Will Ness Derri Leahy 7 年前

`twice` “平方” &头发sp;:

(^.) :: (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

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

twice “平方” &头发sp;:

`twice` “平方” &头发sp;: