haskell - OCaml 和 F# 中的堆栈溢出，但在 Haskell 中没有

Question

我一直在比较有趣的不同语言在执行以下程序时的速度:
对于 i 从 1 到 1000000 求和乘积 i*(sqrt i)

我的一个实现(不是唯一一个)是构建一个列表 [1..1000000]，然后使用特定函数折叠。

该程序在 Haskell 中运行良好且快速(即使使用 foldl 而不是 foldl')，但在 OCaml 和 F# 中堆栈溢出。

这是 Haskell 代码:

test = foldl (\ a b -> a + b * (sqrt b)) 0

create 0 = []
create n = n:(create (n-1))

main = print (test (create 1000000))

这是 OCaml 之一:

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;;

let rec create = function
    | 0 -> []
    | n -> n::(create (n-1)) ;;

print_float (test (create 1000000));;

为什么 OCaml/F# 实现堆栈溢出？

Answer 1

create 的 Haskell 代码懒惰地评估列表，即 foldl 需要元素.不需要一次全部列出整个列表。

相比之下，F# 和 OCaml 评估 create严格列出，即代码尝试在将其传递给 fold_left 之前一次性生成整个列表.

F# 中的一种可能性是使用 seq create 中的表达式功能:这以与 Haskell 相同的方式懒惰地生成列表。 (我不确定 OCaml 是否具有等效功能。)