1

对于 real-world-frege 项目，我从 real-world-haskell 进行了练习，任务是为列表创建一个长度函数，并将其与内部长度函数进行比较。

我提出的解决方案在https://github.com/Dierk/Real_World_Frege/blob/master/realworld/chapter3/I_Exercise_1.fr

它的牛肉是：

mylength :: [a] -> Int

mylength (_:xs)       = 1 + (mylength xs)
mylength []           = 0

-- optLength uses tail recursion and forces eager argument evaluation
optLength xs = privateLength xs 0 where
    privateLength (_:rest) !count = privateLength rest (count + 1)
    privateLength []       !count = count

main _ = do
    assert (mylength [])  (length [])  "empty"
    assert (mylength [0]) (length [0]) "one element"
--  assert (mylength [0..30_000]) (length [0..30_000]) "many elements lead to stack overflow"
    assert (optLength [0..1_000_000])  (length [0..1_000_000])  "optLength can do a little more"
    assert (optLength [0..10_000_000]) (length [0..10_000_000]) "this takes 40 seconds (20 s each)"
--  println (length [0..100_000_000]) -- never stops

对于 100 万个条目以下的列表，我的和内部长度函数都可以正常工作，在 10 M 时会变得非常慢，并且对于 100 M 似乎根本不会停止。

Frege 的内部长度函数（不是 Haskell 的）似乎有一个低于 1 亿的上限。是这样吗？

4

1 回答 1

1

这里有两个问题。

mylength没有尾递归，因此应该堆栈溢出。

这是证明长度函数本身没有限制的证明（也应该适用于您的optlength函数）：

在此处输入图像描述

（TimeoutException 是由于云服务的限制，而不是 Frege 的限制。）

但是，您正在传递length [0..100_000_000]给assert，看起来assert他们的论点也很懒惰。不幸的是，这会导致对列表开头的引用保持活动状态。反过来，这会导致整个列表在内存中实现，因此事情变得非常缓慢，可能是因为您的堆已达到极限，而 GC 试图为下一个参数寻找一些空闲空间。

这与问题中的问题相同：https ://github.com/Frege/frege/issues/65

去试试 -Xmx4g，我相信这在你闪亮的高级笔记本电脑上没有问题 :)

一般的解决方案是在调用之前强制结果assert：

let 
    n = length [0..100_000_000]
    m = optlength [0..100_000_000] 
in n `seq` m `seq` assert n m "should be equal"
于 2014-06-28T13:09:59.587 回答