CODEWITHSUNDEEP
haskellfold
Clinton
Clinton

Reputation: 23135

Combining foldl and foldr

I've figured out myself that foldl (or foldl') is the best approach when you want to produce summarise a list into one result (i.e. sum), and foldr is the best approach when you want to produce another (perhaps even infinite) list (i.e. filter).

So I was considering was processing that combines these two. So I made the function sum_f. sum_f is fairly simple, all it does is add up the elements of a list, but if it finds an element such that f x is true, it gives the current result as output as the element of a list and starts summing from that point all over.

The code is here:

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

Now for example, lets sum all the positive integers grouped by any powers of two. This should output the following:

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

i.e.

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

We can do this like the following:

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

Now this above function (I believe) runs in constant space (like foldl'), even though the groups grow exponentially. Also, it works on infinite lists (like foldr).

I was wondering whether I could write the above using prelude functions without explicit recursion (i.e. only the recursion inside prelude functions). Or does combining the ideas of foldl and foldr here mean that the recursion here can't be done with standard prelude functions and needs to be explicit?

Upvotes: 1

Views: 327

Answers (1)

is7s
is7s

Reputation: 3480

What you want can be expressed using only a right fold as follows:

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

And it works on infinite lists:

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

Upvotes: 5

Related Questions