build.sbt

name := "digits"

version := "0.1"

scalaVersion := "2.10.1"

libraryDependencies += "org.scalaz" %% "scalaz-core" % "6.0.4"

Digits.scala

import scalaz._
import scalaz.Scalaz._
import scala.collection.immutable._

object Digits extends App {
  def sequence[M[_]: Applicative, T[_], A](seq: T[M[A]])(implicit t: Traverse[T]): M[T[A]] =
    t.traverse(identity[M[A]], seq);

  def set[A](seq: Seq[A]): Set[A] = Set(seq : _*);
  //def sorted[A](seq: Seq[A]): SortedSet[A] = SortedSet(seq : _*);

  println( sequence(List(set(1 to 9), set(2 to 9))) )

  // ------------------------------------------------------------------

  type Choices = Set[Int]
  type DigitChoose[A] = StateT[Set,Choices,A]

  // 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);

  def choose: DigitChoose[Int] =
    stateT((s: Choices) => for(i <- s) yield (s - i, i));

  def choose(c: Choices): DigitChoose[Int] =
    stateT((s: Choices) => for(i <- s intersect c ) yield (s - i, i));
  def choose(cs: Seq[Int]): DigitChoose[Int]
    = choose(cs.toSet);

  {
    val choices = Seq(choose, choose(1 to 3), choose(1 to 2));
    println( sequenceDC(choices) ! Set(1 to 9 : _*) );
  }
}