diff options
| -rw-r--r-- | README.md | 52 |
1 files changed, 52 insertions, 0 deletions
@@ -1,3 +1,55 @@ ## fairstream [Simple fair and terminating backtracking Monad Transformer](https://okmij.org/ftp/Computation/monads.html#fair-bt-stream) +[Backtracking, Interleaving, and Terminating Monad Transformers](https://okmij.org/ftp/Computation/LogicT.pdf) + +### 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: + +```scala +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: + +```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(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`: + +```scala +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 +``` |