fairstream

Simple fair and terminating backtracking Monad Transformer

Backtracking, Interleaving, and Terminating Monad Transformers

Motivation

The problem with depth-first search flatMap of fs2.Stream and standard library's collection is that when you nest infinite streams, it gets stuck exploring the first branch forever:

val number = fs2.Stream.iterate(1)(_ + 1) // 1, 2, 3, ...

val triples = for {
  i <- number
  j <- number // stuck here: tries j=1,2,3,... for i=1 forever
  k <- number
  if i * i + j * j == k * k
} yield (i, j, k)

triples.take(1).toList // never terminates

Fair uses fair disjunction (mplus) instead of simple concatenation. It interleaves branches so that every candidate is eventually reached:

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(5), triples)
// List((3,4,5), (4,3,5), (6,8,10), (8,6,10), (5,12,13))

The fairstream-fs2 allows converting Fair/FairT to fs2.Stream:

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

// Fair[A] => fs2.Stream[Pure, A]
val stream = triples.toFs2.take(10).toList

// FairT[IO, A] => fs2.Stream[IO, A]
val ioStream = compatible.toFs2.take(5).compile.toList