結合foldl和foldr

我想通過foldl（或foldl'）是最好的方法，當你想產生一個結果列表（即sum）和foldr是最好的方法，當你想生產另一個（甚至可能是無限）列表（即filter）。結合foldl和foldr

所以我正在考慮處理，結合這兩個。所以我做了功能sum_f。 sum_f是相當簡單的，它所做的只是將列表中的元素相加，但如果它找到一個元素使得f x爲真，則它將當前結果作爲列表元素的輸出並且從該點開始總結。

的代碼是在這裏：

sum_f :: (Num a) => (a -> Bool) -> [a] -> [a] 
sum_f f = 
    let 
    sum_f_worker s (x:xs) = 
     let 
     rec_call z = sum_f_worker z xs 
     next_sum = s + x 
     in 
     next_sum `seq` if (f x) then next_sum : (rec_call 0) else rec_call next_sum 
    sum_f_worker _ [] = [] 
    in 
    sum_f_worker 0

現在的例子，讓我們和所有的任何兩個大國分組的正整數。這應該輸出如下：

[1, 2, 3+4, 5+6+7+8, 9+10+11+12+13+14+15+16, ...]

即

[1, 2, 7, 26, 100, ...]

我們可以做到這一點像下面這樣：

import Data.Bits 

main = 
    let 
    power_of_two x = (x .&. (x - 1)) == 0 -- .&. is bitwise and 
    in 
    print $ take 25 $ sum_f power_of_two [(1::Integer)..]

現在這上面的函數（我相信）在恆定的空間中運行（如foldl'），即使這些羣體呈指數增長。此外，它適用於無限列表（如foldr）。

我想知道我是否可以使用前奏功能而不用顯式遞歸來編寫上面的代碼（即只有前奏功能中的遞歸）。或者在這裏結合foldl和foldr的想法是否意味着這裏的遞歸不能用標準的前奏功能來完成，並且需要是明確的？

來源

2013-03-14 Clinton

的理解摺疊好的資源是文章[「A關於摺疊的普遍性和表現性的教程「]（http://www.cs.nott.ac.uk/~gmh/fold.pdf）由Graham Hutton提供。 – 2013-03-14 10:53:04

@jug：我意識到foldl不會在恆定的空間中運行，但如果您對嚴格性謹慎的話，foldl會這樣做。我已經編輯了這個問題來用fold取代foldl。 – Clinton 2013-03-14 16:45:49

有點破解：'map sum $ groupBy（\ _ y - > not（power_of_two（y-1）））[1 ..]' – luqui 2013-03-14 18:38:42

你想只使用權倍以下可以表示什麼：

{-# LANGUAGE BangPatterns #-} 

sum_f :: (Num a) => (a -> Bool) -> [a] -> [a] 
sum_f p xs = foldr g (const []) xs 0 
    where 
    g x f !a = if p x then x+a:f 0 else f (x+a) 

Prelude Data.Bits> sum_f (\x -> x .&. pred x == 0) [1..10] 
[1,2,7,26]

而且它適用於無限列表：

Prelude Data.Bits> take 10 . sum_f (\x -> x .&. pred x == 0) $ [1..] 
[1,2,7,26,100,392,1552,6176,24640,98432]

來源

2013-03-14 17:26:47 is7s

結合foldl和foldr

回答

相關問題