Haskell高阶函数和GHC评估器

Question

我正在学习FP，并且在玩GHCi之后有些困惑。

说我有2个简单的功能：

twice :: (a -> a) -> (a -> a)
twice f a = f (f a) -- Equation 1

double :: Int -> Int
double = \x -> x * 2

分解评估twice twice twice double 3（请注意3xtwice+ 1x double），我会得到：

{-
   twice twice twice double 3
== (twice twice twice double) 3
== (twice twice (twice double)) 3
== (twice (twice (double double 3))) 
== (twice ((double double) (double double 3))) 
== (((double double) (double double)) ((double double) (double double 3))) 
== 768
-}

• 这是正确的吗？
• 根据this，如果我将twice的定义更改为twice f a = f f a -- Equation 2，则我应该将具有左关联性的评估分解为：

{-
   twice (twice twice double) 3
== (twice twice double) (twice twice double) 3
== ((twice double)(twice double)) ((twice double)(twice double)) 3
== ((double double)(double double)) ((double double)(double double)) 3
== (double (double (double (double (double (double (double (double 3 ) ) ) ) ) ) )
== 768
-}

对吗？

• 但是，最奇怪的部分是GHC REPL给了我196608（2 ^ 16 * 3）的答案：

> twice twice twice double 3
196608

这让我很困惑。我在哪里犯错？谢谢。

Answer 1

正如评论所说，函数应用程序是关联的，所以：

twice twice twice double 3 == (((twice twice) twice) double) 3

which is not the same as:     twice (twice twice double 3)

根据您的注释的要求：请注意，twice返回其参数的相同类型。因此，twice twice的类型仅为((a -> a) -> (a -> a))

现在，让我们扩展整个表达式：

(((twice twice) twice) double) 3 ==> ((twice (twice twice)) double) 3
                                 ==> (((twice twice) ((twice twice) double)) 3
                                 ==> (twice (twice ((twice twice) double))) 3
                                 ==> (twice (twice (twice (twice double)))) 3

twice double ==> double^2
twice (twice double) ==> double^4
twice (twice (twice double)) ==> double^8
twice (twice (twice (twice double))) == double^16

和您发现的double^16 3 == 2^16 * 3。