2

我有一个功能

// Will perform a given function twice
let twice f = (fun x -> f (f x))

然后我有类似的东西。

// Take x add 1
let f x = x+1

根据我两次调用的方式，它对左关联性的行为有所不同。

(twice (twice (twice (twice f)))) 0;; // Outputs 16
twice twice twice twice f 0;; // Outputs 65536

如果我再添加两次，我的程序会执行 StackOverflow，但到目前为止，它的行为似乎没有模式，这让我发疯。

twice设 k 为被调用的次数。

Un-curried 是 2^k 得到答案。

咖喱是非常奇怪的。假设 1：当调用次数小于 4 时，它看起来像 2^(2^(k-1))，但当 k 为 4 时，它的行为像 2^(2^k)

有人看到模式吗？或者你可以运行它超过 k = 4 来证明它吗？

4

2 回答 2

3

这是行为怪异的简单优先规则（提示为 65536=2^16）。在第二种情况下，您实际上是在创建对 f 的指数调用次数，而不是您预期的线性增加。

当您在第二种情况下扩展一层时，您会得到

twice twice twice (twice twice twice (f)) 0

随着你写的更多，术语的数量将成倍增长twice

于 2013-06-06T07:20:06.963 回答
1

事实上，这一切都与关联性有关。写的时候，

let x1 = twice twice twice twice f 0

它等于

let x11 = (((twice twice) twice) twice) f 0

这导致调用顺序呈指数增长：每个twice调用都应该调用f x两次。相反，它递归地调用自己，并且只有最内部的调用会调用f.

你可以看一下函数的原型：

let y1: ( _ -> _ -> int) = twice twice twice twice
// val y1: ((int -> int) -> int -> int)

使关联性正常工作的最少代码是：

// note we need to specify a type here
let y2: ( _ -> _ -> int) = twice >> twice >> twice >> twice
// the same with all arguments
let x2 = (twice >> twice >> twice >> twice) f 0

或者

let y3 = f |> twice |> twice |> twice |> twice
let x3 = (f |> twice |> twice |> twice |> twice) 0
于 2013-06-06T11:18:33.157 回答