combining folds over a sequence

I've got a lazy sequence, and I want to run several for-loops over it (e.g. over a list of numbers, count all the composite numbers, and get the sum of all the primes).

• I would rather not combine the code into a single loop, because it makes it harder to change one in isolation without risking breaking the other.
• I would rather not run them in sequence, because the list is expensive to produce and is too big to be stored in memory all at once.

I think I remember from my Haskell days that for-loops are equivalent to folds, so I figured there may be a way to convert my several for-loops into folds, and then batch them into a single fold that can be run over the data in a single iteration, yielding a tuple of the results.

I don't know if this already has a name, so I don't know where to look for further reading or existing libraries.

I don't know if it has a name other than (left) fold. Since you mentioned Haskell, it defines a left fold like this:

ghci> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

where the function (b -> a -> b) is the 'folder' function and b the initial value.

So, assuming that you want to count the composites and sum the primes, as the OP gives as an example, you might define two separate folder functions that you can vary independently of each other:

countComposite :: (Integral a, Num b) => b -> a -> b
countComposite acc x = if isComposite x then acc + 1 else acc

sumPrimes :: Integral a => a -> a -> a
sumPrimes acc x = if isPrime x then acc + x else acc

Here assuming the existence of suitable isPrime and isComposite functions.

You can now easily combine them into a function that accumulates a tuple of values:

ghci> foldl (\(a1, a2) x -> (countComposite a1 x, sumPrimes a2 x)) (0, 0) [1..30]
(20,129)

This expression initializes the fold with the tuple (0, 0). The 'folder' function is now the lambda expression that pattern-matches the tuple values into two accumulator values a1 and a2 and then produces a new tuple by calling each of the individual 'folder' functions with each their accumulator and x.

Possible generalization

If you want to generalize, we may notice that sumPrimes is clearly a binary operation (a function taking exactly two values of the same type and producing a single value of that type).

countComposite could also be a binary operation, if a ~ b.

Thus, it might be relevant to investigate if both are monoids. I do realize that these particular functions are only placeholder functions, so I don't want to go into a detailed examination of whether or not these two particular functions give rise to monoids.

If, however, all your individual accumulator functions are monoidal, then they do compose, and tuples (or product types) are the way they compose.

And again, monoids accumulate. In Haskell, this is a specialization of a general fold simply called fold. (That particular implementation, however, is based on a right fold, so I'm not sure that it'll work in the OP scenario. Even after 7-8 years with Haskell, I sometimes have a hard time wrapping my head around the way that its laziness works out in practice. In any case, the idea of accumulating a monoid from the left can still be applied, as the linked fold documentation also explains.)

If you want a more object-oriented view, monoids are Composites, so you also define accumulator functions as a polymorphic object and then combine them into a Composite accumulator.

Rust's macros seem powerful enough that they may be able to convert the source code for a for-loop into some data structure representing a fold.

Then given some representation of a fold, maybe something like this:

trait Fold {
  type Input;
  type Output;

  fn run<I: Iterator<Self::Input>>(self, input: I) -> Self::Output {
    for x in input {
      self.step(x);
    }
    self.complete()
  }

  fn step(&mut self, x: Self::Input);
  fn complete(self) -> Self::Output;
}

I figure you could combine arbitrary folds in order to perform them all in a single pass, something like this:

fn batch
  <T:Copy, A:Fold<Input = T>, B:Fold<Input = T>>
  (a: A, b: B)
  -> impl Fold<Input = T, Output = (A::Output, B::Output)>
{
  Batch{a,b}
}

struct Batch<A, B>{a: A, b: B}

impl<T, A, B> Fold for Batch<A, B> 
  where
    T: Copy,
    A: Fold<Input = T>,
    B: Fold<Input = T>,
{
  type Input = T;
  type Output = (A::Output, B::Output);

  fn step(&mut self, x: Self::Input) {
    self.a.step();
    self.b.step();
  }
  fn complete(self) -> Self::Output {
    (
      self.a.complete(),
      self.b.complete()
    )
  }
}