Frege中列表的長度函數是否有上限？

對於現實世界中的項目，我從現實世界中的haskell做了練習，其中的任務是爲列表創建一個長度函數，並將其與內部長度函數進行比較。Frege中列表的長度函數是否有上限？

我提出的解決方案是根據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

我的兩個和在1萬個條目列出了內部長度功能做工精細，得到了10 M和速度很慢似乎根本沒有停止100米。

弗雷格的內部長度函數（不是哈斯克爾的）似乎有一個上限低於1億。是這樣嗎？

來源

2014-06-26 Dierk

請插入相關代碼內嵌所以這個問題可以不讀其他網站的理解 - 它的罰款，以保持鏈接，背景，但問題應該是獨立的。 –

你真正的問題是什麼？你在問爲什麼你的大名單慢？ – bheklilr

你的'myLength'構建了一個未評估的thunk鏈，而'optLength'則強制評估這些thunk。嘗試使用嚴格的'foldl'。 – cdk

這裏有兩個問題。

mylength遭受的不是尾遞歸，因此應該堆棧溢出。

這裏是證明存在本身不限制長度功能（也應該保持你的optlength功能）：

enter image description here

（該TimeoutException異常是由於從雲服務，而不是限制從弗雷格）

但，要傳遞給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-28 13:09:59 Ingo

非常棒的答案 - 一如既往:-)非常感謝。 – Dierk

Frege中列表的長度函數是否有上限？

回答

相關問題