diff options
Diffstat (limited to 'public/post/fairstream')
| -rw-r--r-- | public/post/fairstream/index.html | 263 |
1 files changed, 263 insertions, 0 deletions
diff --git a/public/post/fairstream/index.html b/public/post/fairstream/index.html new file mode 100644 index 0000000..26887df --- /dev/null +++ b/public/post/fairstream/index.html @@ -0,0 +1,263 @@ +<!DOCTYPE html> +<html lang="en"> +<head> + + <title>Fairstream :: </title> + + <meta http-equiv="content-type" content="text/html; charset=utf-8"> +<meta name="viewport" content="width=device-width, initial-scale=1.0"> +<meta name="description" content="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. +" /> +<meta name="keywords" content="" /> + + <meta name="robots" content="noodp" /> + +<link rel="canonical" href="https://blog.gluegadget.com/post/fairstream/" /> + + + + + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/buttons.min.86f6b4c106b6c6eb690ae5203d36b442c1f66f718ff4e8164fa86cf6c61ad641.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/code.min.d529ea4b2fb8d34328d7d31afc5466d5f7bc2f0bc9abdd98b69385335d7baee4.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/fonts.min.5bb7ed13e1d00d8ff39ea84af26737007eb5051b157b86fc24487c94f3dc8bbe.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/footer.min.eb8dfc2c6a7eafa36cd3ba92d63e69e849e2200e0002a228d137f236b09ecd75.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/gist.min.a751e8b0abe1ba8bc53ced52a38b19d8950fe78ca29454ea8c2595cf26aad5c0.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/header.min.75c7eb0e2872d95ff48109c6647d0223a38db52e2561dd87966eb5fc7c6bdac6.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/main.min.36833afd348409fc6c3d09d0897c5833d9d5bf1ff31f5e60ea3ee42ce2b1268c.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/menu.min.3c17467ebeb3d38663dce68f71f519901124fa5cbb4519b2fb0667a21e9aca39.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/pagination.min.bbb986dbce00a5ce5aca0504b7925fc1c581992a4bf57f163e5d69cc1db7d836.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/post.min.e6dddd258e64c83e05cec0cd49c05216742d42fc8ecbfbe6b67083412b609bd3.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/syntax.min.a0773cce9310cb6d8ed23e50f005448facf29a53001b57e038828daa466b25c0.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/terminal.min.e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855.css"> + + + <link rel="stylesheet" href="https://blog.gluegadget.com/css/terms.min.b81791663c3790e738e571cdbf802312390d30e4b1d8dc9d814a5b5454d0ac11.css"> + + + + + + + +<link rel="shortcut icon" href="https://blog.gluegadget.com/favicon.png"> +<link rel="apple-touch-icon" href="https://blog.gluegadget.com/apple-touch-icon.png"> + + +<meta name="twitter:card" content="summary" /> + + + +<meta property="og:locale" content="en" /> +<meta property="og:type" content="article" /> +<meta property="og:title" content="Fairstream"> +<meta property="og:description" content="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. +" /> +<meta property="og:url" content="https://blog.gluegadget.com/post/fairstream/" /> +<meta property="og:site_name" content="" /> + + <meta property="og:image" content="https://blog.gluegadget.com/og-image.png"> + +<meta property="og:image:width" content="1200"> +<meta property="og:image:height" content="627"> + + + <meta property="article:published_time" content="2026-02-17 20:59:41 +0000 UTC" /> + + + + + + + + + +<script> +window.MathJax = { + tex: { + inlineMath: [['$', '$'], ['\\(', '\\)']], + displayMath: [['$$', '$$'], ['\\[', '\\]']], + processEscapes: true, + processEnvironments: true + }, + options: { + skipHtmlTags: ['script', 'noscript', 'style', 'textarea', 'pre'] + } +}; +</script> +<script id="MathJax-script" async src="/mathjax/tex-mml-chtml.js"></script> + + +</head> +<body> + + +<div class="container center"> + + <header class="header"> + <div class="header__inner"> + <div class="header__logo"> + <a href="https://blog.gluegadget.com/"> + <div class="logo"> + Terminal + </div> +</a> + + </div> + + + </div> + +</header> + + + <div class="content"> + +<article class="post"> + <h1 class="post-title"> + <a href="https://blog.gluegadget.com/post/fairstream/">Fairstream</a> + </h1> + <div class="post-meta"><time class="post-date">2026-02-17</time></div> + + + + + + + + <div class="post-content"><div> + <p><a href="https://en.wikipedia.org/wiki/Backtracking">Backtracking</a> 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.</p> +<p>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.</p> +<p><a href="https://github.com/codiff/fairstream"><code>fairstream</code></a> is a Scala implementation of fair backtracking based on the <a href="https://okmij.org/ftp/Computation/monads.html#fair-bt-stream">work</a> of Oleg Kiselyov.</p> +<h2 id="the-problem-with-depth-first-search">The problem with depth-first search<a href="#the-problem-with-depth-first-search" class="hanchor" ariaLabel="Anchor">#</a> </h2> +<p>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 <code>flatMap</code> 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.</p> +<p>The following example demonstrates how <a href="https://fs2.io/">fs2</a>.Stream’s depth-first approach can fail to find Pythagorean triples, even though the result set is non-empty:</p> +<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-scala" data-lang="scala"><span class="line"><span class="cl"><span class="k">val</span> <span class="n">number</span><span class="k">:</span> <span class="kt">fs2.Stream</span><span class="o">[</span><span class="kt">IO</span>, <span class="kt">Int</span><span class="o">]</span> <span class="k">=</span> <span class="n">fs2</span><span class="o">.</span><span class="nc">Stream</span><span class="o">.</span><span class="n">iterate</span><span class="o">(</span><span class="mi">1</span><span class="o">)(</span><span class="k">_</span> <span class="o">+</span> <span class="mi">1</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="k">val</span> <span class="n">triples</span> <span class="k">=</span> <span class="k">for</span> <span class="o">{</span> +</span></span><span class="line"><span class="cl"> <span class="n">i</span> <span class="k"><-</span> <span class="n">number</span> +</span></span><span class="line"><span class="cl"> <span class="n">j</span> <span class="k"><-</span> <span class="n">number</span> +</span></span><span class="line"><span class="cl"> <span class="n">k</span> <span class="k"><-</span> <span class="n">number</span> +</span></span><span class="line"><span class="cl"> <span class="k">if</span> <span class="n">i</span> <span class="o">*</span> <span class="n">i</span> <span class="o">+</span> <span class="n">j</span> <span class="o">*</span> <span class="n">j</span> <span class="o">==</span> <span class="n">k</span> <span class="o">*</span> <span class="n">k</span> +</span></span><span class="line"><span class="cl"><span class="o">}</span> <span class="k">yield</span> <span class="o">(</span><span class="n">i</span><span class="o">,</span> <span class="n">j</span><span class="o">,</span> <span class="n">k</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="n">triples</span><span class="o">.</span><span class="n">take</span><span class="o">(</span><span class="mi">7</span><span class="o">).</span><span class="n">compile</span><span class="o">.</span><span class="n">toList</span> +</span></span></code></pre></div><p>The <code>for</code> comprehension desugars into nested <code>flatMap</code> calls. Since <code>number</code> 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.</p> +<p>This is not a quirk of ofs2. Any depth-first <code>flatMap</code> over infinite collections has this problem, including Scala’s standard library <code>LazyList</code>.</p> +<h2 id="fair-interleaving-with-fairstream">Fair interleaving with <code>fairstream</code><a href="#fair-interleaving-with-fairstream" class="hanchor" ariaLabel="Anchor">#</a> </h2> +<p><code>fairstream</code> solves this by replacing sequential concatenation with fair disjuction (<code>mplus</code>), which interleaves branches so that every candidate is eventually reached.</p> +<p>At the time of writing, the library is published as snapshots:</p> +<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-scala" data-lang="scala"><span class="line"><span class="cl"><span class="n">resolvers</span> <span class="o">+=</span> <span class="nc">Resolver</span><span class="o">.</span><span class="n">sonatypeCentralSnapshots</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="n">libraryDependencies</span> <span class="o">+=</span> <span class="s">"com.codiff"</span> <span class="o">%%</span> <span class="s">"fairstream"</span> <span class="o">%</span> <span class="s">"0.0-9f9db42-SNAPSHOT"</span> +</span></span></code></pre></div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-scala" data-lang="scala"><span class="line"><span class="cl"><span class="k">import</span> <span class="nn">com.codiff.fairstream.Fair</span> +</span></span><span class="line"><span class="cl"><span class="k">import</span> <span class="nn">com.codiff.fairstream.Fair._</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="k">lazy</span> <span class="k">val</span> <span class="n">number</span><span class="k">:</span> <span class="kt">Fair</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span> <span class="k">=</span> <span class="n">mplus</span><span class="o">(</span><span class="n">unit</span><span class="o">(</span><span class="mi">0</span><span class="o">),</span> <span class="n">number</span><span class="o">.</span><span class="n">map</span><span class="o">(</span><span class="k">_</span> <span class="o">+</span> <span class="mi">1</span><span class="o">))</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="k">val</span> <span class="n">triples</span> <span class="k">=</span> <span class="k">for</span> <span class="o">{</span> +</span></span><span class="line"><span class="cl"> <span class="n">i</span> <span class="k"><-</span> <span class="n">number</span> +</span></span><span class="line"><span class="cl"> <span class="k">_</span> <span class="k"><-</span> <span class="n">guard</span><span class="o">(</span><span class="n">i</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"> <span class="n">j</span> <span class="k"><-</span> <span class="n">number</span> +</span></span><span class="line"><span class="cl"> <span class="k">_</span> <span class="k"><-</span> <span class="n">guard</span><span class="o">(</span><span class="n">j</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"> <span class="n">k</span> <span class="k"><-</span> <span class="n">number</span> +</span></span><span class="line"><span class="cl"> <span class="k">_</span> <span class="k"><-</span> <span class="n">guard</span><span class="o">(</span><span class="n">k</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"> <span class="k">_</span> <span class="k"><-</span> <span class="n">guard</span><span class="o">(</span><span class="n">i</span> <span class="o">*</span> <span class="n">i</span> <span class="o">+</span> <span class="n">j</span> <span class="o">*</span> <span class="n">j</span> <span class="o">==</span> <span class="n">k</span> <span class="o">*</span> <span class="n">k</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"><span class="o">}</span> <span class="k">yield</span> <span class="o">(</span><span class="n">i</span><span class="o">,</span> <span class="n">j</span><span class="o">,</span> <span class="n">k</span><span class="o">)</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="nc">Fair</span><span class="o">.</span><span class="n">runM</span><span class="o">(</span><span class="nc">None</span><span class="o">,</span> <span class="nc">Some</span><span class="o">(</span><span class="mi">7</span><span class="o">),</span> <span class="n">triples</span><span class="o">)</span> +</span></span></code></pre></div><h2 id="fairt-effectful-fair-backtracking"><code>FairT</code>: effectful fair backtracking<a href="#fairt-effectful-fair-backtracking" class="hanchor" ariaLabel="Anchor">#</a> </h2> +<p><code>Fair[A]</code> 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 <code>FairT[F[_], A]</code> comes in.</p> +<p><code>FairT</code> is a monad transformer that layers fair backtracking on top of any effect <code>F</code>. This means you can interleave non-deterministic search with <code>IO</code>, <code>Task</code>, or any other cats-effect compatible monad.</p> +<h2 id="fs2-integration">fs2 integration<a href="#fs2-integration" class="hanchor" ariaLabel="Anchor">#</a> </h2> +<p>If you want to stay in the fs2 ecosystem, <code>fairstream-fs2</code> provides a conversion from <code>Fair</code> and <code>FairT</code> to <code>fs2.Stream</code>:</p> +<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-scala" data-lang="scala"><span class="line"><span class="cl"><span class="n">libraryDependencies</span> <span class="o">+=</span> <span class="s">"com.codiff"</span> <span class="o">%%</span> <span class="s">"fairstream-fs2"</span> <span class="o">%</span> <span class="s">"0.0-9f9db42-SNAPSHOT"</span> +</span></span></code></pre></div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-scala" data-lang="scala"><span class="line"><span class="cl"><span class="k">import</span> <span class="nn">com.codiff.fairstream.fs2.syntax._</span> +</span></span><span class="line"><span class="cl"> +</span></span><span class="line"><span class="cl"><span class="n">triples</span><span class="o">.</span><span class="n">toFs2</span><span class="o">.</span><span class="n">take</span><span class="o">(</span><span class="mi">7</span><span class="o">).</span><span class="n">compile</span><span class="o">.</span><span class="n">toList</span> +</span></span></code></pre></div><p>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 <code>Fair</code> or <code>FairT</code>, then convert to <code>fs2.Stream</code> at the boundary where you need to integrate with the rest of your application.</p> + + </div></div> + + + +<div class="pagination"> + <div class="pagination__title"> + <span class="pagination__title-h"></span> + <hr /> + </div> + <div class="pagination__buttons"> + + + + <a href="https://blog.gluegadget.com/post/2017-08-22-thinkpad-e470/" class="button inline next"> + [<span class="button__text">ThinkPad E470</span>] > + </a> + + </div> +</div> + + + + + + + + +</article> + + </div> + + + <footer class="footer"> + <div class="footer__inner"> + + <div class="copyright"> + <span>© 2026 Powered by <a href="https://gohugo.io">Hugo</a></span> + + <span>:: <a href="https://github.com/panr/hugo-theme-terminal" target="_blank">Theme</a> made by <a href="https://github.com/panr" target="_blank">panr</a></span> + </div> + </div> +</footer> + + + + + + +<script type="text/javascript" src="/bundle.min.js"></script> + + + + + + +</div> + +</body> +</html> |