---
title: "Fairstream"
date: 2026-02-17T20:59:41Z
---

[Backtracking](https://en.wikipedia.org/wiki/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`](https://github.com/codiff/fairstream) is a Scala implementation of fair backtracking based on the [work](https://okmij.org/ftp/Computation/monads.html#fair-bt-stream) of Oleg Kiselyov.

## The problem with depth-first search

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](https://fs2.io/).Stream's depth-first approach can fail to find Pythagorean triples, even though the result set is non-empty:

```scala
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:

```scala
resolvers += Resolver.sonatypeCentralSnapshots

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

```scala
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`:

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

```scala
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.