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

Question

有很多问题基于 applyTwice，但 none 与我的问题相关。我知道 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 for 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)))

等等。

Answer 2

以不可见类型参数的形式隐藏在幕后的复杂性很多。如果我们用 -XTypeApplications 写出这些参数会发生什么？我已经缩短了一些名字。

以下twice实例化在twice @Int，类型为二阶

one :: Int
one = twice (+ 1) 0
      ^^^^^
      | 
      twice @Int
        :: (Int -> Int) 
        -> (Int -> Int)

当您将 twice（order-3）应用于 twice（order-2）时，类型签名变得更加复杂。

two :: Int
two = twice twice (+ 1) 0
      ^^^^^ ^^^^^
      |     |
      |     twice @Int
      |       :: (Int -> Int)
      |       -> (Int -> Int)
      |
      twice @(Int->Int)
        :: ((Int->Int) -> (Int->Int))
        -> ((Int->Int) -> (Int->Int))

以此类推，当你有 twice twice twice 时，它们分别是 order-4、order-3 和 order-2：

three :: Int
three = twice twice twice (+ 1) 0
        ^^^^^ ^^^^^ ^^^^^
        |     |     | 
        |     |     twice @Int
        |     |       :: (Int -> Int)
        |     |       -> (Int -> Int)
        |     |
        |     twice @(Int->Int)
        |       :: ((Int->Int) -> (Int->Int))
        |       -> ((Int->Int) -> (Int->Int))
        |
        twice @((Int->Int)->(Int->Int))
          :: (((Int->Int)->(Int->Int)) -> ((Int->Int)->(Int->Int)))
          -> (((Int->Int)->(Int->Int)) -> ((Int->Int)->(Int->Int)))

你给出的最后一个例子变成了这个怪物，分别是 order-6、order-5、order-4、order-3、order-2...

{-# Language TypeApplications #-}

five :: Int
five = twice @((((Int->Int)->(Int->Int))->((Int->Int)->(Int->Int)))->(((Int->Int)->(Int->Int))->((Int->Int)->(Int->Int))))
         (twice @(((Int->Int)->(Int->Int))->((Int->Int)->(Int->Int))))
         (twice @((Int->Int)->(Int->Int)))
         (twice @(Int->Int))
         (twice @Int)
         (+ 1) 0

所以这是第一个的类型twice!!

twice @((((Int->Int)->(Int->Int))->((Int->Int)->(Int->Int)))->(((Int->Int)->(Int->Int))->((Int->Int)->(Int->Int))))
  :: (((((Int -> Int) -> Int -> Int) -> (Int -> Int) -> Int -> Int)
       -> ((Int -> Int) -> Int -> Int) -> (Int -> Int) -> Int -> Int)
      -> (((Int -> Int) -> Int -> Int) -> (Int -> Int) -> Int -> Int)
      -> ((Int -> Int) -> Int -> Int)
      -> (Int -> Int)
      -> Int
      -> Int)
     -> ((((Int -> Int) -> Int -> Int) -> (Int -> Int) -> Int -> Int)
         -> ((Int -> Int) -> Int -> Int) -> (Int -> Int) -> Int -> Int)
     -> (((Int -> Int) -> Int -> Int) -> (Int -> Int) -> Int -> Int)
     -> ((Int -> Int) -> Int -> Int)
     -> (Int -> Int)
     -> Int
     -> Int

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

Can't understand result when calling applyTwice multiple times

haskell

functional-programming

currying

higher-order-functions