StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What you're looking for is called <em>monadic sequencing</em>. When you use <code>for</code> comprehension such as</p> <pre><code>for(x <- Set(...) y <- Set(...)) yield (x, y) </code></pre> <p>you can view it as having a pair of monadic computations <code>(Set(...), Set(...))</code> and converting it into a monad holding a pair of results <code>Set((...,...), (...,...), ...)</code>.</p> <p>This can be generalized to sequences of arbitrary lengths. The <em>scalaz</em> library defines trait <code>Traversable</code>, which represents sequences for which we can define such an operation. It's <code>traverse</code> operation is more general and we can use it to define monadic sequencing:</p> <pre><code>import scalaz._ import scalaz.Scalaz._ import scala.collection.immutable._ def sequence[M[_]: Applicative, T[_], A](seq: T[M[A]]) (implicit t: Traverse[T]): M[T[A]] = t.traverse(identity[M[A]], seq); </code></pre> <p>In our case, <code>M</code> will be <code>Set</code> and <code>T</code> will be <code>Seq</code>. So given a sequence of choices (represented as sets) of type <code>Seq[Set[Int]]</code>, <code>sequence</code> will get us <code>Set[Seq[Int]]</code> which is the set of all possible combinations picked from the choices:</p> <pre><code>// a helper function def set[A](seq: Seq[A]): Set[A] = Set(seq : _*); // prints all sequences where the first number is from 1 to 9 // and the second number from 2 to 9: println( sequence(List(set(1 to 9), set(2 to 9))) ) </code></pre> <hr> <p>You can then filter the sequences where some number occurs more than once.</p> <p>If you want to include this kind of filtering in the process, it will get more complicated. You need to keep some state during the monadic computation, which will hold what numbers remain available. Let's define</p> <pre><code>type Choices = Set[Int] type DigitChoose[A] = StateT[Set,Choices,A] </code></pre> <p>So <code>DigitChoose</code> is a monad which has non-deterministic results (every operation produces a set of possible outcomes, like before), but also keeps a state of type <code>Choices</code>, which tells us what numbers are still available.</p> <p>Next, we define some helper functions to help the compiler a bit (the general types are too much for it :)).</p> <pre><code>// See http://stackoverflow.com/q/7782589/1333025 why we need this: implicit val applicativeDC: Applicative[DigitChoose] = implicitly[Monad[DigitChoose]] def sequenceDC[A](seq: Seq[DigitChoose[A]]): DigitChoose[Seq[A]] = sequence(seq); </code></pre> <p>so now we have monadic sequencing defined over <code>DigitChoose</code> for sequences.</p> <p>Using <code>DigitChoose</code> we can define operations that pick a digit from one of available ones and update the state (remove the chosen digit from the set):</p> <pre><code>// Pick any of the available digits: def choose: DigitChoose[Int] = stateT((s: Choices) => for(i <- s) yield (s - i, i)); </code></pre> <p>and some restricted variants that restrict the choice of digits:</p> <pre><code>// Pick an available digit that is also in the given set of choices: def choose(c: Choices): DigitChoose[Int] = stateT((s: Choices) => for(i <- s intersect c ) yield (s - i, i)); // Pick an available digit that is also in the given set of choices: def choose(cs: Seq[Int]): DigitChoose[Int] = choose(cs.toSet); </code></pre> <p>Finally, we do things like:</p> <pre><code>// First digit is unrestricted // Second digit is from 1 to 3 // Third digit is from 1 to 2 // ... and no digits will be the same! val choices = Seq(choose, choose(1 to 3), choose(1 to 2)); // Sequence the choices, given that we start with digits 1 to 9 println( sequenceDC(choices) ! Set(1 to 9 : _*) ); </code></pre> <p>The <a href="https://gist.github.com/ppetr/5907228" rel="nofollow">complete code is available on gist</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload