缺乏認識無限列表和seq運營商

Question

下面的代碼保存爲一個給定的整數n的，從列表中的前n項，下降以下n項，保留接下來n等。它適用於任何有限列表。

爲了使其可用具有無窮列表，我使用的「序列」操作的遞歸步驟在與foldl」作爲例子之前，迫使蓄壓器的評價。

我測試通過跟蹤累加器的值，它似乎是，與有限列表期望它被有效地計算出來。

然而，當應用到無限的名單這是行不通的。主函數中的「take」只有在內部計算結束後纔會執行，當然，無限列表永遠不會發生。

請，有人可以告訴我在哪裏是我的錯？

main :: IO() 
main = print (take 2 (foo 2 [1..100])) 

foo :: Show a => Int -> [a] -> [a] 
foo l lst = inFoo keepOrNot 1 l lst [] 

inFoo :: Show a => (Bool -> Int -> [a] -> [a] -> [a]) -> Int -> Int -> [a] -> [a] -> [a] 
inFoo keepOrNot i l [] lstOut = lstOut 
inFoo keepOrNot i l lstIn lstOut = let lstOut2 = (keepOrNot (odd i) l lstIn lstOut) in 
         stOut2 `seq` (inFoo keepOrNot (i+1) l (drop l lstIn) lstOut2) 

keepOrNot :: Bool -> Int -> [a] -> [a] -> [a] 
keepOrNot b n lst1 lst2 = case b of 
    True -> lst2 ++ (take n lst1) 
    False -> lst2 

Answer 1

這裏是連接列表是如何實現的：

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

注意

• 右手錶結構被重用爲是（即使它尚未評估，因此懶洋洋地）
• 左手列表結構被重寫（複製）

這意味着，如果你使用++建立一個列表，你想要的蓄能器是在右手邊。 （對於有限列表，僅出於效率的原因 - 如果累加器在左側，它將被重複複製，效率低下;對於無限列表，調用者無法查看結果的第一個元素，直到它被複制的最後時間，也不會有最後的時間，因爲總是有別的東西來連接到蓄電池的權利。）

的True案件keepOrNot對++左側的累加器。您需要使用不同的數據結構。

在這種情況下通常的習慣用法是使用差異列表。您的累加器不使用[a]型號，請使用[a] -> [a]。您的累加器現在是將列出的列表作爲輸入提供的列表。這樣可以避免重複複製，並且可以延遲建立列表。

keepOrNot :: Bool -> Int -> [a] -> ([a] -> [a]) -> ([a] -> [a]) 
keepOrNot b n lst1 acc = case b of 
    True -> acc . (take n lst1 ++) 
    False -> acc 

累加器的初始值應該是id。當你想把它轉換成一個常規列表時，用[]（即acc []）來調用它。

---

seq是這裏的紅鯡魚。 seq不強制整個列表。 seq只決定它是否是[]或x : xs的形式。

---

您正在學習Haskell，是嗎？因此，修改代碼以使用差異列表累加器是一個很好的主意。可能無限列表的使用會將您刻錄到代碼的不同部分;我不知道。

但是有更好的方法來編寫foo。

foo c xs = map snd . filter fst . zipWith f [0..] $ xs 
    where f i x = (even (i `div` c), x) 

Answer 2

所以你要組列表到n元素組，並丟棄所有其他組。我們可以直接寫下來：

import Data.List (unfoldr) 

groups n xs = takeWhile (not.null) $ unfoldr (Just . splitAt n) xs 

foo c xs = concatMap head . groups 2 . groups c $ xs 

dave4420已經解釋什麼是你的代碼錯誤，但我想對你如何了那裏IMO發表評論。您的keepOrNot :: Bool -> Int -> [a] -> [a] -> [a]功能太太。它根據收到的Bool,任何Bool;但是你知道，你會給它一個交替的True和False值。使用函數進行編程就像將管道插入漏斗中 - 一個函數的輸出作爲下一個函數的輸入 - 漏斗在這裏太寬，所以觸點鬆動。

沿着這些線路代碼的最小重寫可能是

foo n lst = go lst 
    where 
    go lst = let (a,b) = splitAt n lst 
       (c,d) = splitAt n b 
      in 
       a ++ go d 

的接觸是「從緊」，沒有「信息泄露」在這裏。我們只是做了兩次的工作^（*）我們自己，並明確地「連接管道」，在這段代碼中，抓取一個結果（a）並刪除另一個（c）。

-
^（*）兩次，反映了兩個布爾值，True和False，以簡單的方式交替接連之一。因此，這會在代碼結構中凍結捕獲，而不是作爲可容納任意布爾值的參數懸停。

Answer 3

像dava4420說，你不應該使用(++)從左側積累。但也許你不應該積累！在Haskell中，懶惰使直接的「頭部構造」通常比你需要用到的尾部遞歸更有效。 Lisp的。例如：

foo :: Int -> [a] -> [a]  -- why would you give this a Show constraint? 
foo ℓ = foo' True 
    where foo' _ [] = [] 
     foo' keep lst 
      | keep  = firstℓ ++ foo' False other 
      | otherwise =   foo' True other 
     where (firstℓ, other) = splitAt ℓ lst