1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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 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.
|
