title: Abstract over repeated flatMap
body: <p>I am trying to generalize repeated, nested <code>flatMap</code> but not sure if one exists.</p>
  <p>The following code will produce all combinations of <em>n choose 3</em>, <a href="https://i.stack.imgur.com/dpMs1.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/dpMs1.gif" alt="n choose 3" /></a>:</p>
  <pre class="lang-scala prettyprint-override"><code>def choose3flatMap(n: Int, r: Int = 3) =
    (0 to n - r)
      .flatMap(i =&gt; (i + 1 to n - (r - 1))
        .flatMap(j =&gt; (j + 1 to n - (r - 2))
          .map(k =&gt; Seq(i, j, k))))
  </code></pre>
  <p>Repeating the flatMap operation, we can get all combinations of <em>n choose 5</em>, <a href="https://i.stack.imgur.com/cummL.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/cummL.gif" alt="n choose 5" /></a> :</p>
  <pre class="lang-scala prettyprint-override"><code>def choose5flatMap(n: Int, r: Int = 5) =
    (0 to n - r)
      .flatMap(i =&gt; (i + 1 to n - (r - 1))
        .flatMap(j =&gt; (j + 1 to n - (r - 2))
          .flatMap(k =&gt; (k + 1 to n - (r - 3))
            .flatMap(l =&gt; (l + 1 to n - (r - 4))
              .map(m =&gt; Seq(i, j, k, l, m)))))
  </code></pre>
  <p>Clearly there is a pattern here.  I would like to utilize this similarity to get a general solution for <em>n choose r</em>, <a href="https://i.stack.imgur.com/eJMJZ.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/eJMJZ.gif" alt="n choose r" /></a>.  Is there a simple way to accomplish this.  Perhaps a higher order function of some sort?</p>
  <h3>What I have tried:</h3>
  <p>Scala lets me rewrite the <code>map</code>/<code>flatMap</code> with a for expression.  This reads cleaner, but the number of choices in still hard-coded.</p>
  <pre class="lang-scala prettyprint-override"><code>def choose3Loop(n: Int, r: Int = 3) =
    for {
      i &lt;- 0 to n - r
      j &lt;- i + 1 to n - (r - 1)
      k &lt;- j + 1 to n - (r - 2)
    } yield Seq(i, j, k)
  </code></pre>
  <p>I can write a recursive solution directly using <code>flatMap</code> or utilizing the sugar of a <code>for</code> expression:</p>
  <pre class="lang-scala prettyprint-override"><code>def combinationsRecursive(n: Int, r: Int, i: Int = 0): Seq[Seq[Int]] =
    if (r == 1) (i until n).map(Seq(_))
    else {
      (i to n - r).flatMap(
        i =&gt; combinationsRecursive(n, r - 1, i + 1).map(j =&gt; i +: j))
    }
  
  def combinationsRecursiveLoop(n: Int, r: Int, i: Int = 0): Seq[Seq[Int]] =
    if (r == 1) (i until n).map(Seq(_))
    else
      for {
        i &lt;- i to n - r
        j &lt;- combinationsRecursiveLoop(n, r - 1, i + 1)
      } yield i +: j
  </code></pre>
  <p>While these are solutions to the general problem, I wonder if there is a higher-level abstraction I am missing here that may be applicable to other problems as well.  I recognize that for this particular application, I could do <code>(0 to n).combinations(r)</code> to use a library-provided implementation of computing combinations.</p>
  <p>While the above code is Scala, in this case I am interested the functional programming aspect of it and not the language capabilities.  If there is a solution but one that is not supported by Scala I am interested in that.</p>
  <p><strong>Edit:</strong>  He is a sample caller and the resulting output by request:</p>
  <blockquote>
  <p>scala&gt; combinationsRecursiveLoop(5, 3)</p>
  <p>res0: Seq[Seq[Int]] = Vector(List(0, 1, 2), List(0, 1, 3), List(0, 1, 4), List(0, 2, 3), List(0, 2, 4), List(0, 3, 4), List(1, 2, 3), List(1, 2, 4), List(1, 3, 4), List(2, 3, 4))</p>
  <p>scala&gt; combinationsRecursiveLoop(5, 3).map(&quot;(&quot;+_.mkString(&quot;, &quot;)+&quot;)&quot;).mkString(&quot; &quot;)</p>
  <p>res1: String = (0, 1, 2) (0, 1, 3) (0, 1, 4) (0, 2, 3) (0, 2, 4) (0, 3, 4) (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)</p>
  </blockquote>
  <p>It just provides all <em>r</em>-element subsets of the set of integers starting at zero containing <em>n</em> elements.  <a href="https://en.wikipedia.org/wiki/Combination" rel="noreferrer">More information on combinations can be found on Wikipedia</a>.</p>