1 files changed, 86 insertions, 0 deletions
diff --git a/content/post/fairstream.md b/content/post/fairstream.md
new file mode 100644
index 0000000..d4bba6c
--- /dev/null
+++ b/content/post/fairstream.md
@@ -0,0 +1,86 @@
+---
+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 ofs2. 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.