Backtracking is a versatile approach for solving search problems by building solutions incrementally. If a partial solution cannot be extended, it is discarded and the process returns to a previous step to explore an alternative path. This method is generally more efficient than brute-force searching due to pruning: stopping exploration of a branch as soon as it violates a constraint, which eliminates entire sections of the search space.

Strictly speaking, fair backtracking is not required for all search problems. A fair strategy guarantees all branches make progress, preventing any single branch from starving the others. The List monad handles non-deterministic computation well, and within a finite search space it produces the same results as a fair stream. When the search space is infinite, or when one branch may produce unbounded results, fairness becomes essential to ensure completeness.

fairstream is a Scala implementation of fair backtracking based on the work of Oleg Kiselyov.

Consider Pythagorean triples: tuples $(i, j, k)$ such that $i^2+j^2=k^2$, with $(3, 4, 5)$ as the canonical first example. If we try to generate all such triples using nested infinite generators, a conventional stream composition based on sequential flatMap gets stuck exploring an infinite branch that contains no solution and never comes back up to try a larger value, so it may fail to produce any triples at all despite solutions existing.

The following example demonstrates how fs2.Stream’s depth-first approach can fail to find Pythagorean triples, even though the result set is non-empty:

val number: fs2.Stream[IO, Int] = fs2.Stream.iterate(1)(_ + 1)

val triples = for {
  i <- number
  j <- number
  k <- number
  if i * i + j * j == k * k
} yield (i, j, k)

triples.take(7).compile.toList

The for comprehension desugars into nested flatMap calls. Since number is infinite, the innermost generator tries $k = 1, 2, 3, \ldots$ forever for $i = 1, j = 1$ before it ever consider $j = 2$. No Pythagorean triple exists for $i = 1, j = 1$, so the stream never produces a result.

This is not a quirk of fs2. Any depth-first flatMap over infinite collections has this problem, including Scala’s standard library LazyList.

Fair interleaving with fairstream#

fairstream solves this by replacing sequential concatenation with fair disjuction (mplus), which interleaves branches so that every candidate is eventually reached.

At the time of writing, the library is published as snapshots:

resolvers += Resolver.sonatypeCentralSnapshots

libraryDependencies += "com.codiff" %% "fairstream" % "0.0-9f9db42-SNAPSHOT"

import com.codiff.fairstream.Fair
import com.codiff.fairstream.Fair._

lazy val number: Fair[Int] = mplus(unit(0), number.map(_ + 1))

val triples = for {
  i <- number
  _ <- guard(i > 0)
  j <- number
  _ <- guard(j > 0)
  k <- number
  _ <- guard(k > 0)
  _ <- guard(i * i + j * j == k * k)
} yield (i, j, k)

Fair.runM(None, Some(7), triples)

FairT: effectful fair backtracking#

Fair[A] is a pure computation. But what if your search branches need to perform effects, like reading from a database, calling an API, or logging? That’s where FairT[F[_], A] comes in.

FairT is a monad transformer that layers fair backtracking on top of any effect F. This means you can interleave non-deterministic search with IO, Task, or any other cats-effect compatible monad.

fs2 integration#

If you want to stay in the fs2 ecosystem, fairstream-fs2 provides a conversion from Fair and FairT to fs2.Stream:

libraryDependencies += "com.codiff" %% "fairstream-fs2" % "0.0-9f9db42-SNAPSHOT"

import com.codiff.fairstream.fs2.syntax._

triples.toFs2.take(7).compile.toList

This should let you compose fair backtracking with all the stream processing, concurrency, and resource management that fs2 provides. You define your search logic using Fair or FairT, then convert to fs2.Stream at the boundary where you need to integrate with the rest of your application.