爲什麼不是這個功能懶洋洋地消費？

我有兩個功能類似於filter和takeWhile。爲什麼不是這個功能懶洋洋地消費？

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a] 
filterAcc p xs = go xs [] 
    where go [] acc  = acc 
      go (x:xs) acc 
      | p (x:acc) = go xs (x:acc) 
      | otherwise = go xs acc 

takeWhileAcc p xs = go xs [] 
    where go [] acc  = acc 
      go (x:xs) acc 
      | p (x:acc) = go xs (x:acc) 
      | otherwise = acc

它們都採取謂詞和列表，以及它們之處在於，採取的謂詞的累積結果作爲輸入的常規filter和takeWhile不同。

我的問題是，雖然filter even [1..]將立即開始產生輸出（懶洋洋地），filterAcc (any even) [1..]掛起。我的懷疑是助手功能go正在阻止這些功能懶惰地行事。

我該如何讓這些功能懶惰地操作？

來源

2012-11-21 cdk

請注意，如果將累加器作爲參數傳遞給「go」（如果它產生遲鈍），則完全沒有意義 - 並且會適得其反。累加器用於遞增計算的結果，不能遞增遞送。如果您可以遞增遞送結果，那麼保留對已交付部分的引用的唯一理由是，如果需要對剩餘部分進行[高效]計算。 –

@DanielFischer：讓我感到可能有更好的方法來實現這些功能。我問了#haskell，但沒有得到答案。你能提出一個更好的方法嗎？我認爲這在國家單體中可能是可能的，但我還不習慣使用國家單體。 – cdk

哦，對不起，沒有正確閱讀（在第一杯茶前）。你實際上需要測試的累積結果，所以最後一句的最後部分適用。 –

問題是，go的情況總是以自己的尾巴呼叫結束。當它到達列表的末尾時，它只會返回一些有用的東西，當然這絕不會出現在無限列表中。

相反，當你去，你應該返回元素：

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a] 
filterAcc p xs = go xs [] 
    where go [] acc  = [] 
      go (x:xs) acc 
      | p (x:acc) = x : go xs (x:acc) 
      | otherwise = go xs acc 

takeWhileAcc p xs = go xs [] 
    where go [] acc  = [] 
      go (x:xs) acc 
      | p (x:acc) = x : go xs (x:acc) 
      | otherwise = []

來源

2012-11-21 04:24:04 hammar

就是這樣，謝謝！ – cdk

懶列表消費通常是由foldr實現。

您的累加器需要從左到右的信息流。這通常通過使用foldl來實現，但這意味着嚴格的列表消耗。

的解決方案是使用scanl：

--- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) 
--- scanl  :: (a -> b -> a)  -> a -> [b] -> [a] 

takeWhileAcc p []  = [] 
takeWhileAcc p (x:xs) = map snd $ takeWhile (p.fst) 
           $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs 

filterAcc p []  = [] 
filterAcc p (x:xs) = map snd $ filter (p.fst) 
           $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

另一種可能性是使用until，或mapAccumL。後者將是一個自然的適合，除了它不收集累計值，而是傳遞最後的累加器值。

來源

2012-11-21 14:32:34

爲什麼不是這個功能懶洋洋地消費？

回答

相關問題