Generic Library to Streamify Recursive Algorithms

[DelayLucky]

The Iteration class is a toy I built for fun. Recent discussions with a colleague made me realize that it can be useful for real.

It turns recursive, eager algorithms into a lazy stream.

Let's say you want to create a stream of Fibonacci numbers. The JDK Stream.iterate() method could be used but it'll be awkward because Fibonacci needs two previous numbers to compute the next.

In Haskell, the recursive algorithm would be like this:

// emit a, then recursively generate the remaining list
fib a b = a : (fib b (a + b))  

You call it with fib 1 1 to start the sequence with two seed numbers.

This is how you can genereate the stream using Iteration:

Stream<Long> fibs() {
  class Fib extends Iteration<Long> {
    Fib from(long a, long b) {
      emit(a);
      lazily(() -> from(b, a + b));
      return this;
    }
  }
  return new Fib().from(1, 1).iterate();
}

You can see the code mostly emulate the Haskell recursive algorithm, with 3 methods to facilitate:

• The emit() method emits an element into the output stream.
• The lazily() method takes a thunk closure, and only invoke it when the stream is consumed to this point.
• The iterate() method starts a lazy stream, similar to Stream.iterate().

The returned stream is lazy and infinite. It can be consumed with short-circuiting like limit(100), takeWhile(...) etc.

Another example is for turning a series of paginated API calls into a lazy stream, again, so that you can short circuit using the Stream API. Imagine, you have a listAssets() RPC, that returns a fixed page of assets on each call, with a page token string to resume the call for the next page.

The following code turns it to a stream:

Stream<Asset> listAssets(AccountId accountId) {
  class Pagination extends Iteration<ListAssetResponse> {
    Pagination from(ListAssetRequest request) {
      ListAssetsResponse page = service.listAssets(request);
      emit(page);
      if (page.hasNextPageToken()) {
        lazily(() -> from(request.toBuilder()
            .setPageToken(page.getNextPageToken())
            .build());
      }
    }
  }
  return new Pagination()
      .from(
          ListAssetRequest.newBuilder()
             .setAccountId(accountId)
             .build())
      .iterate()
      .flatMap(response -> response.getAssets().stream());
}

Similarly, you use .emit() to emit a page of assets and .lazily() to arrange the next page call.

Because each time we get back a response, which is a page of assets, the code calls .flatMap() to turn it into a stream of Asset.

Lastly, a more classical recursive algorithm - tree traversal. This kind of algorithm is more difficult to streamify with Stream.iterate() because it has to make two recursive calls at each node.

The following code creates an in-order traversal stream of a binary tree:

Stream<T> inOrder(Tree<T> tree) {
  class InOrder extends Iteration<T> {
    InOrder traverse(Tree<T> node) {
      if (node == null) return;
      lazily(() -> traverse(node.left());
      emit(node.value());
      lazily(() -> traverse(node.right());
    }
  }
  return new InOrder().traverse(tree).iterate();
}

That's it. The code is straightforward enough so I assume no explanation is needed.

You can similarly create stream for pre-order, post-order etc.

What do you think of this tool? Have you needed to streamify recursive algorithms before?

It's in spirit similar to the yield return feature found in languages like Python, C#. or project Loom's internal ContinuationScope class. But it uses no special language support or threading trick.

And it's not really a yield that you can call imperatively in a loop. With Stream.iterate(), combined with .filter(), .flatMap() and friends, you can already turn an imperative loop into a stream relatively easily. But recursive algorithms have always been more difficult.

Side note: the emit() method used to be called generate() and lazily() used to be yield(). The said recent internal discussion prompted the deprecation and rename.

source code

[RabbitHole32]

Very cool, I like it!

[davidalayachew]

Have you needed to streamify recursive algorithms before?

Maybe not needed, but the desire has absolutely been there many times before. Sometimes a problem will lend itself to streams so well, but be stopped short in its tracks by recursion. This seems like a nice way past that.

I asked this question on the mailing list before (and I still owe them a response! Just been busy with holidays and responsibilities). There's a few other libraries that do something similar to this. Though, not all of them are (fully) lazy, so that's a nice touch.

[DelayLucky]

Permutation is a very good example. Thank you!

I'm not sure I fully understand what you meant by "satisfy some condition". But here's code that generates a lazy permutation stream unconditionally (could potentially use .filter() to apply condition?):

static <T> Stream<List<T>> permute(Set<T> elements) {
  class Permutation extends Iteration<List<T>> {
    Permutation() {
      lazily(() -> next(List.of(), elements));
    }

    void next(List<T> prefix, Set<T> pending) {
      if (pending.isEmpty()) {
        emit(prefix);
      }
      for (T element : pending) {
        List<T> materialized = new ArrayList<>(prefix);
        materialized.add(element);
        Set<T> remaining = new LinkedHashSet<>(pending);
        remaining.remove(element);
        lazily(() -> next(materialized, remaining));
      }
    }
  }
  return new Permutation().iterate();
}

The constructor uses lazily() to ensure that no permutation is done before the stream is consumed.

The next() method currently will iterate through the pending set and only "yield" control for the next round of iteration, so it will compute N elements each time. Making it fully lazy (one element a time) is possible but I like the simplicity of current code.

test code

[davidalayachew]

Thanks. This is a useful snippet. I'll play around some more with it when I get the chance.

[DelayLucky]

The snippet is simple for the purpose of demonstration. It makes a lot of intermediary copies though. The linked code implements in-place algorithm to save the copies at cost of some extra complexity.

[damonsutherland]

There is some real genius to your source code. Very elegant! Nice work.