無限列表，懶惰評價和長度

Haskell noob here：我仍然試圖理解語言的機制，所以如果我的問題很愚蠢，原諒我，並指向我可以學習的一些鏈接（我已經在這裏搜索了一些類似的話題，但我仍然無法得到這個結果）。無限列表，懶惰評價和長度

我想出了這個功能：

chunks :: Int -> [a] -> [[a]] 
chunks n xs 
    | length xs <= n = [xs] 
    | otherwise = let (ch, rest) = splitAt n xs in ch:chunks n rest

使

ghci> chunks 4 "abracadabra" 
["abra","cada","bra"] 
ghci> 
ghci> chunks 3 [1..6] 
[[1,2,3],[4,5,6]]

我很滿意這一點，那麼我想：「有懶的評價我甚至可以在無限使用此功能！序列！」。所以我試了take 4 $ chunks 3 [1..]。我希望這個懶惰的哈斯克爾魔法產生了[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]，相反，它似乎像這個時候懶惰不能幫助我：它不能達到計算的終點（它是否一直走到最後的[1..]？）

我認爲問題出在「長度xs」部分：ghci似乎也卡在簡單的length [1..]上。所以我問：實際上迭代整個列表的長度是否會給出響應？如果是這樣，我想每次嘗試執行一些與懶惰評估一起工作的東西時，都會避免長度，所以還有一些選擇？（例如，我怎樣才能提高我的例子與無限列表合作？）

來源

2016-03-12 giuliocatte

當然，回答自己的問題的方法是追蹤'length'的實現（請參閱資源的haskell標籤信息部分），或者甚至更好地嘗試自己定義它並說服自己它可能只能行爲單程。 – jberryman

如果你覺得冒險，試着按照[Peano數字]（https://wiki.haskell.org/Peano_numbers）而不是'Int'重新實現'splitAt'和'length'，看看你能不能讓你的''chunks'在無限列表上表現得很好 – jberryman

你可能想看看['genericLength']（https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html# v：genericLength）和惰性['Natural']（http://hackage.haskell.org/package/numbers-3000.2.0.1/docs/Data-Number-Natural.html）類型 - 只需將'Int'更改爲'chunks'類型中的'Natural'並將'length'改爲'genericLength'將使您的示例正常工作。 –

是實際迭代整個列表的長度以給出響應的長度？

是的。

我猜長度是要避免每次我嘗試實施一些與懶惰的評價

不僅如此運作良好時，它也給你不好的運行時間時，懶惰是不是一個因素（在O（1）檢查通常足夠的情況下爲O（n），所以你應該避免大部分時間。

我該如何改進我的例子以使用無限列表？

你並不需要檢查列表的長度是否小於n，你只需要檢查它是否是零。而且你可以用簡單的模式匹配來完成。

例如像f xs | length xs >= 2 = ...，這是O（n），可以用f (x1 : x2 : xs) = ...被替換，這是O（1）。

來源

2016-03-12 14:39:46 sepp2k

的長度實際上遍歷整個列表給予迴應？

是的，絕對。

長度是要避免每次我嘗試實施一些與懶惰的評價

是運作良好，絕對時間。

所以有一些替代？

是：解決問題無需參考length。沒有解決問題的一般方法，所以你需要制定出每個具體的案例。

我怎樣才能提高我的例子與無限列表

你是一個鐵路工人的工作。一輛巨大的火車，如果汽車從你站立的地方開始，並在地平線上延伸。如果有的話，你不知道它在哪裏結束。你的工作是把它分成三輛小汽車。你如何繼續？

來源

2016-03-12 14:36:22

另一個竅門，你可以做（這是我見過的Data.Text，但很奇怪是不是在爲前奏一般列表）是通過返回一個Ordering而非Bool儘快使length短路。

compareLength :: [a] -> Int -> Ordering 
compareLength [] n = compare 0 n 
compareLength _ 0 = GT 
compareLength (x : xs) n = compareLength xs (n - 1)

然後你可以在chunks中使用它。

chunks :: Int -> [a] -> [[a]] 
chunks n xs = case compareLength xs n of 
        LT -> [xs] 
        _ -> let (ch, rest) = splitAt n xs in ch:chunks n rest

這工作正常。

*Main> take 4 $ chunks 3 [1..] 
[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

對於這種特殊情況，其他實現可能更習慣性，但希望這是一個很好的技巧。

來源

2016-03-12 20:00:08 badcook

無限列表，懶惰評價和長度

回答

相關問題