La combinaison foldl et foldr

Question

J'ai pensé moi-même que foldl (ou foldl') est la meilleure approche quand vous voulez produire une liste résumer en un seul résultat (c.-à-sum), et foldr est la meilleure approche quand vous voulez produire une autre liste (peut-être même infinie) (c.-à-d. filter).

Donc, je considérais un traitement qui combine ces deux. J'ai donc fait la fonction sum_f. sum_f est assez simple, tout ce qu'il fait est d'additionner les éléments d'une liste, mais s'il trouve un élément tel que f x est vrai, il donne le résultat courant en sortie en tant qu'élément d'une liste et commence à sommer à partir de ce point .

Le code est ici:

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 

Maintenant, par exemple, permet de somme tous les nombres entiers positifs regroupés par des puissances de deux. Cela devrait génèrerait les éléments suivants:

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

-à-dire

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

Nous pouvons le faire comme ce qui suit:

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)..] 

maintenant cette fonction ci-dessus (je crois) fonctionne dans l'espace constant (comme foldl'), même si les groupes croissent de façon exponentielle. En outre, cela fonctionne sur les listes infinies (comme foldr).

Je me demandais si je pouvais écrire ce qui précède en utilisant les fonctions prélude sans récurrence explicite (c'est-à-dire seulement la récursion à l'intérieur des fonctions prélude). Ou est-ce que combiner les idées de foldl et de foldr signifie ici que la récursion ne peut pas être faite avec les fonctions de prélude standard et doit être explicite?

Answer 1

Qu'est-ce que vous voulez peut être exprimée en utilisant seulement un pli droit comme suit:

{-# 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] 

Et cela fonctionne sur les listes infinies:

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