Haskell 高阶函数和关联性

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+1xdouble)，我会的。

{-
   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
-}

• 这样对吗？
• 根据 这个如果我的定义是 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 如你所见。

Answer 2

假设 n 是自然数，而 g n 定义如下，非正式地。

g n = \f x -> f (f (f (.... (f x))))  -- n times f on x

在你的情况下， twice f x = g 2 f x.

那么，我们可以证明

g n (g m) f x = g (m^n) f x

确实如此。

g n (g m) f x =
(g m (g m (g m (g m .... (g m f))))) x =  -- n times (g m) on f

所以，它是把"m-多次重复 f"函数，然后重复该 m 次，形成另一个函数，然后重复该 m-次，... 每一步都会将 f 由 m所以我们得到 m^n.

回到你的案子上

twice twice twice double 3 =
g 2 (g 2) (g 2) double 3 =
g (2^2) (g 2) double 3 =
g (2^(2^2)) double 3 =
double (double (double .... 3)) -- 2^(2^2) = 2^4 = 16 times

所以，我们正在得到 3 倍增 16 次，获得 3 * 2^16 = 196608.