Func を使った数独
これは Scalaz Advent Calendar 2012 5日目の記事です。
12月の間中、日本の技術系ギークは日替わりでテーマに沿った記事を公開し、彼の国では「Advent Calendar」と呼ばれているらしい。去年の Scala Advent Calendar 2011 で僕は Eric Torreborre さんが The Essence of Iterator Pattern をカバーした記事を翻訳した。これは日本人の関数型プログラミング記事好きを知った上である程度狙ったものだった。もう1つの利己的な動機は、記事を一語一語訳す過程において概念のいくつかは僕の頭にも染みこんでくれるんじゃないかという期待だった。振り返ってみると、両方の目的とも作戦成功だったと言える。Jeremy Gibbons さん、Bruno Oliveira さんそして Eric 両方の仕事のクオリティのお陰だ。これらの染み込んだ知識が今年に書いた独習 Scalaz シリーズの隠し味だったんじゃないかと思っている。
独習 Scalaz 12日目でふれたとおり、Scalaz 7 の型クラスインスタンスには既に product と compose が含まれており、また Traverse も定義されている。論文にある word count の例題 まである。僕が気づいたのは、値レベルでの合成が無いことだ。この論文の興味深い点の1つに「applicative functor の合成」があり、これはモジュール化プログラミング的なものを可能とする。
Gibbons と Oliveira の言う「applicative functor」は実は型クラスのインスタンスだけではなく、applicative 関数の合成も指している。これは論文からの以下の抜粋をみれば明らかだ:
data (m ⊠ n) a = Prod { pfst :: m a, psnd :: n a }
(⊗) :: (Functor m, Functor n) ⇒ (a → m b) → (a → n b) → (a → (m ⊠ n) b)
(f ⊗ g) x = Prod(f x)(gx)
代数データ型の ⊠ は型レベルの積だが、中置関数の ⊗ は 2つの applicative 関数の値レベルの積で、a → (m ⊠ n) という型の applicative 関数を返す。言い換えると、プログラマは applicative functor を返す関数を構築するだけよくて、型レベルでの合成は自動的に行われる。
Func
Func は、値レベルでの applicative 関数の合成を提供しようと僕が試みたものだ。
scala> import scalaz._, Scalaz._, typelevel._
import scalaz._
import Scalaz._
import typelevel._
scala> val f = AppFuncU { (x: Int) => x + 1 }
f: scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,scalaz.Applicative,Int,Int] = scalaz.typelevel.FuncFunctions$$anon$12@3143369a
scala> val g = AppFuncU { (x: Int) => List(x, 5) }
g: scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,List[Int]]{type M[X] = List[X]; type A = Int}#M,scalaz.Applicative,Int,Int] = scalaz.typelevel.FuncFunctions$$anon$12@3106a3a2
scala> (f @&&& g) traverse List(1, 2, 3)
res0: scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,List[Int]]{type M[X] = List[X]; type A = Int}#M,scalaz.typelevel.TCNil]]#Product[List[Int]] = GenericCons(9,GenericCons(List(List(1, 2, 3), List(1, 2, 5), List(1, 5, 3), List(1, 5, 5), List(5, 2, 3), List(5, 2, 5), List(5, 5, 3), List(5, 5, 5)),GenericNil()))
Kleisli 同様に、Func は A => F[B] 関数を表す:
trait Func[F[_], TC[F[_]] <: Functor[F], A, B] { self =>
def runA(a: A): F[B]
implicit def TC: KTypeClass[TC]
implicit def F: TC[F]
}
runA メソッドはこの関数を実行し、普通の関数の apply メソッドに相当する。
Func はまた別の Func を返す productA メソッド (シンボルを使ったエイリアスは @&&&) を実装する。Func の元の実装は AppFunc と呼ばれていて applicative functor に特化したものだった。Lars Hupel さん (@larsr_h) の提案で型クラスに対して多相的であるようにリファクタされ Func となった。
scalaz-typelevel モジュール
コアモジュール内の個々の型クラスで実装されている product と compose メソッドはシグネチャを共有しないため、互いに独立している。例えば、Functor 下の product は Functor[({type λ[α] = (F[α], G[α])})#λ] を返すが、Applicative 下の product は Applicative[({type λ[α] = (F[α], G[α])})#λ] を返す。
scalaz-typelevel モジュールは型レベルのデータ構造 (あと readme によると型安全な printf) を提供する。僕が狙っているのは KTypeClass で、これは Functor や Applicative のような、カインドが * -> * の型クラスの型クラスだ。その主な機能は product と compose メソッドだ:
trait KTypeClass[C[_[_]]] {
def product[F[_], T <: TCList](FHead: C[F], FTail: C[T#Product]): C[TCCons[F, T]#Product]
def compose[F[_], T <: TCList](FOuter: C[F], FInner: C[T#Composed]): C[TCCons[F, T]#Composed]
}
積のエンコードに Tuple2 を使う代わりに、KTypeClass は HList を使って積をエンコードする。これもまた scalaz-typelevel モジュールに含まれている。全ての要素の中から1つの型しか保存することができない List に対して、HList は全ての要素の型を保存する。
scala> List(1, "string").head
res1: Any = 1
scala> (1 :: "string" :: HNil).head
res2: scalaz.Id.Id[Int] = 1
Int と String を許容するために、最初の List は List[Any] まで広げられたのに対して、HList は型をそのまま保存した。
HListFunc
EIP をならって、僕の Func の実装は @&&& を使った 2つの関数の積しかサポートしていなかった。もし誰かが @&&& を連鎖したならば、HList の中に入れ子で HList が入ったものが返された。Lars は HList をそのまま伸ばせるようにするべきだと提案した。
数週間後に僕が思いついたのが HList を返す関数のラッパー HListFunc で、これは Func を継承する:
trait HListFunc[T <: TCList, TC[X[_]] <: Functor[X], A, B] extends Func[T#Product, TC, A, B] { self =>
def ::[G[_]](g: Func[G, TC, A, B]) = g consA self
private[scalaz] def Product: KTypeClass.WrappedProduct[TC, T]
final def F = Product.instance
}
HListFunc の作成には2通りの方法がある。1つは、AppFunc などの特化された Func オブジェクトの HNil メソッドを呼ぶことだ:
scala> AppFunc.HNil
res7: scalaz.typelevel.HListFunc[scalaz.typelevel.TCNil,scalaz.Applicative,Nothing,Nothing] = scalaz.typelevel.FuncFunctions$$anon$6@1e525ac8
scala> AppFunc.HNil[Int, Int]
res8: scalaz.typelevel.HListFunc[scalaz.typelevel.TCNil,scalaz.Applicative,Int,Int] = scalaz.typelevel.FuncFunctions$$anon$6@6e8d1f6a
scala> res8.runA(0)
res9: scalaz.typelevel.TCNil#Product[Int] = GenericNil()
HListFunc を作る第2の方法は既存の HListFunc に対して :: 演算子を使うことだ:
scala> AppFuncU { (x: Int) => x + 1 } :: AppFunc.HNil
res15: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,scalaz.typelevel.TCNil],scalaz.Applicative,Int,Int] = scalaz.typelevel.Func$$anon$4@34f262c3
Func 再び
HListFunc を使うことで prodctA (別名 @&&&) メソッドは以下のように実装できる:
/** compose `A => F[B]` and `A => G[B]` into `A => F[B] :: G[B] :: HNil` */
def productA[G[_]](g: Func[G, TC, A, B]) = consA(g consA hnilfunc[TC, A, B])
Func はまた composeA (シンボルを使ったエイリアスは <<<@) とその逆の andThenA (シンボルを使ったエイリアスは @>>>) も実装する:
scala> AppFuncU { (x: Int) => (x + 1).some } @>>> AppFuncU { (x: Int) => x + "!" }
res32: scalaz.typelevel.Func[[α]scalaz.Unapply[scalaz.Applicative,Option[Int]]{type M[X] = Option[X]; type A = Int}#M[scalaz.Unapply[scalaz.Applicative,String]{type M[X] = String; type A = String}#M[α]],scalaz.Applicative,Int,String] = scalaz.typelevel.Func$$anon$7@4fcb8010
scala> res32.runA(10)
res33: scalaz.Unapply[scalaz.Applicative,Option[Int]]{type M[X] = Option[X]; type A = Int}#M[scalaz.Unapply[scalaz.Applicative,String]{type M[X] = String; type A = String}#M[String]] = Some(11!)
数独
Func を使った applicative 合成を実際に使って説明する具体例として最初に思いついたのが数独の解法だ。ツールの長所と短所を洗い出すのに丁度いい複雑さだと思う。だからと言って、これが数独を解く最適な方法だと主張するつもりはない。
問題の読み込み
以下がオンラインで見つけた簡単な数独ファイルフォーマットの例だ:
#C comment
2..1.5..3
.54...71.
.1.2.3.8.
6.28.73.4
.........
1.53.98.6
.2.7.1.6.
.81...24.
7..4.2..1
# で始まる行はヘッダで、残りの行が問題を表す。問題を単純化するために、まずは 4x4 の数独から始める:
#C comment
.13.
...4
...1
.24.
まずそれぞれのマスを以下に定義されるセルとして表す:
case class Cell(pos: (Int, Int), value: Option[Int])
ファイルを Vector[Cell] にパースするのは簡単だ。
object Reader {
import scalaz._
import Scalaz._
def read(path: String): Vector[Cell] = read(new File(path))
def read(file: File): Vector[Cell] = {
val source = scala.io.Source.fromFile(file, "UTF-8")
val lines = Vector(source.getLines.toSeq filterNot { x => x.isEmpty || (x startsWith "#") }: _*)
lines.zipWithIndex flatMap { case (line, idx) =>
val cs = Vector(line.toSeq: _*)
(1 |-> lines.size) map { x =>
Cell((x, idx + 1), cs(x - 1).toString.parseInt.toOption)
}
}
}
}
REPL から確認することができる:
scala> import com.eed3si9n.sudoku._
import com.eed3si9n.sudoku._
scala> Reader.read("data/1.sdk")
res0: Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((1,1),None), Cell((2,1),Some(1)), Cell((3,1),Some(3)), Cell((4,1),None), Cell((1,2),None), Cell((2,2),None), Cell((3,2),None), Cell((4,2),Some(4)), Cell((1,3),None), Cell((2,3),None), Cell((3,3),None), Cell((4,3),Some(1)), Cell((1,4),None), Cell((2,4),Some(2)), Cell((3,4),Some(4)), Cell((4,4),None))
仕事の分割
ある特定のセル、例えば (4, 1)、に注目してどうやって数独を解くか考えてみよう。僕ならば、まず列を行をチェックして候補を消していって、次に 4つのセルから成るグループもチェックしてさらに候補を消してく。この戦略は簡単な問題になら使えそうだ。
上の戦略を別の見方をすると消去法ということだ。まず Vector(1, 2, 3, 4) から始めて、行、列、グループに対応した小さなマシンがチェックを行なって徐々に候補を消していく。これらの小さなマシンは State モナドとして実装できる。まず下準備:
scala> import scalaz._, Scalaz._, typelevel._
import scalaz._
import Scalaz._
import typelevel._
scala> import com.eed3si9n.sudoku._
import com.eed3si9n.sudoku._
scala> val game = Reader.read("data/1.sdk")
game: Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((1,1),None), Cell((2,1),Some(1)), ...
次に横向きのマシン:
scala> def horizontalMachine(pos: (Int, Int)) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_ <- put(if (pos._2 == cell.pos._2 && cell.value.isDefined) xs filter {_ != cell.value.get}
else xs)
} yield()
}
horizontalMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,Cell,Unit]
scala> horizontalMachine((4, 1)) traverse game
res1: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[Unit]] = scalaz.StateT$$anon$7@33d5157f
scala> res1 exec Vector(1, 2, 3, 4)
res2: scalaz.Id.Id[Vector[Int]] = Vector(2, 4)
2 と 4 以外は第1行にあるため、結果は妥当みたいだ。縦向きのマシンにも拡張する:
scala> def verticalMachine(pos: (Int, Int)) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_ <- put(if (pos._1 == cell.pos._1 && cell.value.isDefined) xs filter {_ != cell.value.get}
else xs)
} yield()
}
verticalMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]
scala> verticalMachine((4, 1)) traverse game
res5: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[Unit]] = scalaz.StateT$$anon$7@70a81b43
scala> res5 exec Vector(1, 2, 3, 4)
res6: scalaz.Id.Id[Vector[Int]] = Vector(2, 3)
for 内包表記の部分は以下のようにリファクタできる:
scala> def buildMachine(predicate: Cell => Boolean) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_ <- put(if (predicate(cell)) xs filter {_ != cell.value.get}
else xs)
} yield()
}
buildMachine: (predicate: com.eed3si9n.sudoku.Cell => Boolean)scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]
scala> def verticallMachine(pos: (Int, Int)) =
buildMachine { cell: Cell => pos._1 == cell.pos._1 && cell.value.isDefined }
verticallMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]
buildMachine を使って groupMachine も以下のように定義できる:
scala> def groupMachine(pos: (Int, Int), n: Int) =
buildMachine { cell: Cell =>
((pos._1 - 1) / n == (cell.pos._1 - 1) / n) &&
((pos._2 - 1) / n == (cell.pos._2 - 1) / n) &&
cell.value.isDefined
}
groupMachine: (pos: (Int, Int), n: Int)scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]
scala> groupMachine((4, 1)) traverse game
res7: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[Unit]] = scalaz.StateT$$anon$7@79f39896
scala> res7 exec Vector(1, 2, 3, 4)
res8: scalaz.Id.Id[Vector[Int]] = Vector(1, 2)
次に、3つのマシン全てを並列 (parallel) に実行したいとする。以下のように HListFunc を構築できる:
scala> def threeMachines(pos: (Int, Int), n: Int) =
horizontalMachine(pos) :: verticalMachine(pos) :: groupMachine(pos, n) :: AppFunc.HNil
threeMachines: ...
ここでの問題はこれが HList を返す Func を返すことだ。3つの要素とも同じ型なので List が欲しい。
hlist の均質化
HList を何かに畳み込む場合は、以下のように HFold のサブタイプを定義する:
scala> class Homogenize[T] extends HFold[Id, List[T]] {
type Init = List[T]
def init = Nil
type Apply[E, A <: List[T]] = List[T]
def apply[E, A <: List[T]](elem: E, acc: A) =
(elem match {
case x: T => x
}) :: acc
}
defined class Homogenize
これを使って HListFunc を State モナドのリストを返す Func に変換することができる:
scala> def homogenize[M[_]: Applicative, T <: TCList, B](g: HListFunc[TCCons[M, T], Applicative, Cell, B]) =
new Func[({type λ[α] = List[M[α]]})#λ, Applicative, Cell, B] {
def runA(c: Cell): List[M[B]] = {
val xs = g.runA(c)
xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
}
def F = (Applicative[List] <<: Applicative[M] <<: TC.idCompose).instance
def TC = g.TC
}
homogenize: [M[_], T <: scalaz.typelevel.TCList, B](g: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[M,T],scalaz.Applicative,com.eed3si9n.sudoku.Cell,B])(implicit evidence$1: scalaz.Applicative[M])scalaz.typelevel.Func[[α]List[M[α]],scalaz.Applicative,com.eed3si9n.sudoku.Cell,B]
さらにもう一歩進めて、State モナドのリストをリストの State モナドに変換することもできる:
scala> def sequence[M[_]: Applicative, T <: TCList, B](g: HListFunc[TCCons[M, T], Applicative, Cell, B]) =
new Func[M, Applicative, Cell, List[B]] {
def runA(c: Cell): M[List[B]] = {
val xs = g.runA(c)
val list: List[M[B]] = xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
list.sequence
}
def F = Applicative[M]
def TC = g.TC
}
sequence: [M[_], T <: scalaz.typelevel.TCList, B](g: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[M,T],scalaz.Applicative,com.eed3si9n.sudoku.Cell,B])(implicit evidence$1: scalaz.Applicative[M])scalaz.typelevel.Func[M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,List[B]]
上記は State モナドを連鎖する。 (4, 1) で試してみよう:
scala> sequence(threeMachines((4, 1), 2)) traverse game
res10: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[Vector[List[Unit]]] = scalaz.StateT$$anon$7@3fc1c1a6
scala> res10 exec Vector(1, 2, 3, 4)
res11: scalaz.Id.Id[Vector[Int]] = Vector(2)
これを cellMachine を呼ぶことにする:
object Solver {
def solve(game: Vector[Cell]) {
}
def cellMachine(pos: (Int, Int), n: Int) =
sequence(horizontalMachine(pos) :: verticalMachine(pos) :: groupMachine(pos, n) :: AppFunc.HNil)
...
}
全てのセルに対して実行する
ここまでの成果を見るために全ての空のセルに対して cellMachine を実行してみる:
object Solver {
...
def runOnce(game: Vector[Cell]) {
val css = game map { cell: Cell =>
val cs = cell.value map { v =>
Vector(v)
} getOrElse {
(cellMachine(cell.pos, 2) traverse game) exec Vector(1, 2, 3, 4)
}
if (cell.pos._1 == 1) println()
print(cs.toString + " ")
cs
}
}
}
もう一度 game を書いておく:
#C comment
.13.
...4
...1
.24.
runOnce を実行する:
scala> Solver.runOnce(game)
Vector(2, 4) Vector(1) Vector(3) Vector(2)
Vector(2, 3) Vector(3) Vector(1, 2) Vector(4)
Vector(3, 4) Vector(3, 4) Vector(2) Vector(1)
Vector(1, 3) Vector(2) Vector(4) Vector(3)
この情報を使って、新たな Vector[Cell] を返すことができる。まず Cell の定義を拡張して候補を保存できるようにする:
scala> case class Cell(pos: (Int, Int),
value: Option[Int],
cs: Vector[Int] = Vector())
defined class Cell
ベクトルを渡してまわる代わりに Game クラスも作ってしまおう:
case class Game(cells: Vector[Cell]) {
import scalaz._
import Scalaz._
val n: Int = math.pow(cells.size, 0.5).round.toInt
val sqrtn: Int = math.pow(n, 0.5).round.toInt
val allValues = Vector((1 |-> n): _*)
def apply(pos: (Int, Int)) = (cells.find {_.pos == pos}).get
override def toString: String = {
(allValues flatMap { y =>
allValues flatMap { x =>
val cell = apply((x, y))
(cell.value map { x =>
cell.value.toString
} getOrElse {cell.cs.toString}) +
(if (x == n) "\n"
else " ")
}
}).mkString
}
}
以下が更新された runOnce だ:
def runOnce(game: Game): Game = {
val (nonEmptyCells, emptyCells) = game.cells partition {_.value.isDefined}
val solveCells = emptyCells map { cell =>
val candidates = (cellMachine(cell.pos, game.n) traverse game.cells) exec game.allValues
if (candidates.size == 1) cell.copy(value = candidates(0).some, cs = Vector())
else cell.copy(value = none, cs = candidates)
}
game.copy(cells = nonEmptyCells ++ solveCells)
}
runOnce を連続的に呼び出すことで、いくつかの問題は解けるようになった:
scala> Solver.runOnce(game)
res0: com.eed3si9n.sudoku.Game =
Vector(2, 4) Some(1) Some(3) Some(2)
Vector(2, 3) Some(3) Vector(1, 2) Some(4)
Vector(3, 4) Vector(3, 4) Some(2) Some(1)
Vector(1, 3) Some(2) Some(4) Some(3)
scala> Solver.runOnce(res0)
res1: com.eed3si9n.sudoku.Game =
Some(4) Some(1) Some(3) Some(2)
Some(2) Some(3) Some(1) Some(4)
Vector(3, 4) Some(4) Some(2) Some(1)
Some(1) Some(2) Some(4) Some(3)
scala> Solver.runOnce(res1)
res2: com.eed3si9n.sudoku.Game =
Some(4) Some(1) Some(3) Some(2)
Some(2) Some(3) Some(1) Some(4)
Some(3) Some(4) Some(2) Some(1)
Some(1) Some(2) Some(4) Some(3)
全てのセルを並列に
何度もセルを走査するかわりに、マシンを並列に合成できるか試してみたい。
scala> val (nonEmptyCells, emptyCells) = game.cells partition {_.value.isDefined}
nonEmptyCells: ...
emptyCells: ...
scala> emptyCells.foldLeft[HListFunc[TCList, Applicative, Cell, List[Vector[Int]]]](AppFunc.HNil[Cell, List[Vector[Int]]]) { (acc, cell) => Solver.cellMachine(cell.pos, game.sqrtn) :: acc }
<console>:22: error: type mismatch;
found : scalaz.typelevel.HListFunc[scalaz.typelevel.TCNil,scalaz.Applicative,com.eed3si9n.sudoku.Cell,List[Vector[Int]]]
required: scalaz.typelevel.HListFunc[scalaz.typelevel.TCList,scalaz.Applicative,com.eed3si9n.sudoku.Cell,List[Vector[Int]]]
Note: scalaz.typelevel.TCNil <: scalaz.typelevel.TCList, but trait HListFunc is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
emptyCells.foldLeft[HListFunc[TCList, Applicative, Cell, List[Vector[Int]]]](AppFunc.HNil[Cell, List[Vector[Int]]]) { (acc, cell) => Solver.cellMachine(cell.pos, game.sqrtn) :: acc }
^
TCNil が TCList より狭く、また HListFunc の型パラメータ T が不変であるため foldLeft は使うことができない。HListFunc には HList のような一般トレイトが無いため、HList を手作業で構築する羽目になった:
scala> def foldCells(xs: Vector[Cell], game: Game): Vector[Cell] = {
def f(cell: Cell) = Solver.cellMachine(cell.pos, game.sqrtn)
def homogenize[M[_], B, T <: HList](xs: HCons[M[B], T]): List[M[B]] =
xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
val hnil = AppFunc.HNil[Cell, List[Unit]]
val css = if (xs.isEmpty) Nil
else if (xs.size === 1) homogenize((f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else if (xs.size === 2) homogenize((f(xs(1)) :: f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else if (xs.size === 3) homogenize((f(xs(2)) :: f(xs(1)) :: f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else if (xs.size === 4) homogenize((f(xs(3)) :: f(xs(2)) :: f(xs(1)) :: f(xs(0)) :: hnil) traverse game.cells) map {_ exec game.allValues}
else sys.error("invalid")
(xs zip css.reverse) map { case (cell, cs) =>
cell.copy(cs = cs)
}
}
foldCells: (xs: Vector[com.eed3si9n.sudoku.Cell], game: com.eed3si9n.sudoku.Game)Vector[com.eed3si9n.sudoku.Cell]
scala> val cellsWithCs = Vector((emptyCells grouped 4).toSeq: _*) flatMap { g => foldCells(g, game) }
cellsWithCs: scala.collection.immutable.Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((1,1),None,Vector(2, 4)), Cell((4,1),None,Vector(2)), Cell((1,2),None,Vector(2, 3)), Cell((2,2),None,Vector(3)), Cell((3,2),None,Vector(1, 2)), Cell((1,3),None,Vector(3, 4)), Cell((2,3),None,Vector(3, 4)), Cell((3,3),None,Vector(2)), Cell((1,4),None,Vector(1, 3)), Cell((4,4),None,Vector(3)))
上記のコードは空のセルを 4つずつ走査する。
反復解法器
問題が解けるまで runOnce を呼び出すことで解法を作る。
case class Game(cells: Vector[Cell]) {
...
def isSolved: Boolean = cells forall {_.value.isDefined}
}
以下が解法だ:
def solve(game: Game) {
def doLoop(g: Game) {
println(g.toString)
if (g.isSolved) println("solved")
else {
val g2 = runOnce(g)
if (g == g2) sys.error("solver is stuck")
else doLoop(g2)
}
}
doLoop(game)
}
簡単な問題ならこれでも解けることは既にみた:
scala> Solver.solve(game)
....
Some(4) Some(1) Some(3) Some(2)
Some(2) Some(3) Some(1) Some(4)
Some(3) Some(4) Some(2) Some(1)
Some(1) Some(2) Some(4) Some(3)
solved
普通の数独はもう少し思考が必要なものだ。例えば、以下を 3.sdk として保存する:
#C comment
47..6..59
...2.7...
6.......8
..5.8.9..
.1.7.6.8.
..8.4.2..
8.......2
...6.3...
92..5..16
sbt を使ってこれを game として REPL に読み込む:
initialCommands in console := """import scalaz._, Scalaz._, typelevel._
|import com.eed3si9n.sudoku._
|val game = com.eed3si9n.sudoku.Reader.read("data/3.sdk")""".stripMargin
以下が出力だ:
scala> Solver.solve(game)
Some(4) Some(7) Vector() Vector() Some(6) Vector() Vector() Some(5) Some(9)
Vector() Vector() Vector() Some(2) Vector() Some(7) Vector() Vector() Vector()
Some(6) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(8)
Vector() Vector() Some(5) Vector() Some(8) Vector() Some(9) Vector() Vector()
Vector() Some(1) Vector() Some(7) Vector() Some(6) Vector() Some(8) Vector()
Vector() Vector() Some(8) Vector() Some(4) Vector() Some(2) Vector() Vector()
Some(8) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(2)
Vector() Vector() Vector() Some(6) Vector() Some(3) Vector() Vector() Vector()
Some(9) Some(2) Vector() Vector() Some(5) Vector() Vector() Some(1) Some(6)
Some(4) Some(7) Vector(1, 2, 3) Vector(1, 3, 8) Some(6) Vector(1, 8) Vector(1, 3) Some(5) Some(9)
Vector(1, 3, 5) Vector(3, 5, 8, 9) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Vector(1, 3, 4, 6) Vector(3, 4, 6) Vector(1, 3, 4)
Some(6) Vector(3, 5, 9) Vector(1, 2, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Vector(1, 3, 4, 7) Vector(2, 3, 4, 7) Some(8)
Vector(2, 3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Vector(1, 2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Vector(2, 3) Some(1) Vector(2, 3, 4, 9) Some(7) Vector(2, 3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5, 6) Vector(1, 3, 4, 6, 7) Vector(1, 4, 9) Vector(1, 7, 9) Vector(1, 4, 9) Vector(3, 4, 5, 7) Vector(3, 4, 7, 9) Some(2)
Vector(1, 5, 7) Vector(4, 5) Vector(1, 4, 7) Some(6) Vector(1, 2, 7, 9) Some(3) Vector(4, 5, 7, 8) Vector(4, 7, 9) Vector(4, 5, 7)
Some(9) Some(2) Vector(3, 4, 7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4, 7, 8) Some(1) Some(6)
java.lang.RuntimeException: solver is stuck
at scala.sys.package$.error(package.scala:27)
....
ユニークな候補
現在の実装は候補が単一の候補である場合のみ選択される。しかし、たとえセルに対して複数の候補があったとしてもその中の候補のうちの1つがグループや行内の他の候補には無いユニークなものであった場合は、当選とみなされるべきだ。
scala> def buildEvalMachine(predicate: Cell => Boolean) = AppFuncU { cell: Cell =>
for {
xs <- get[Vector[Int]]
_ <- put(if (predicate(cell)) xs diff cell.cs
else xs)
} yield ()
}
buildEvalMachine: (predicate: com.eed3si9n.sudoku.Cell => Boolean)scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]
scala> def horizEvalMachine(pos: (Int, Int)) =
buildEvalMachine { cell: Cell => (cell.pos != pos) && (pos._2 == cell.pos._2) }
horizEvalMachine: (pos: (Int, Int))scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.Applicative,com.eed3si9n.sudoku.Cell,Unit]
scala> val cellsWithCs = Vector((emptyCells grouped 4).toSeq: _*) flatMap { g => foldCells(g, game) }
cellsWithCs: scala.collection.immutable.Vector[com.eed3si9n.sudoku.Cell] = Vector(Cell((3,1),None,Vector(1, 2, 3)), ...
scala> horizEvalMachine((3, 1)) traverse cellsWithCs
res8: scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[scala.collection.immutable.Vector[Unit]] = scalaz.StateT$$anon$7@5b06ad02
scala> res8 exec Vector(1, 2, 3)
res9: scalaz.Id.Id[Vector[Int]] = Vector(2)
これは良い例だ。(3, 1) の位置にあるセルは 3つの候補があったが、この論法を使って 2 に絞りこまれた。3つのマシン全てを並列して実行することができるはずだ。
def evalMachine(pos: (Int, Int), n: Int) =
horizEvalMachine(pos) :: vertEvalMachine(pos) :: groupEvalMachine(pos, n) :: AppFunc.HNil
この二次評価の仕組みを取り入れて候補を絞る:
def runOnce(game: Game): Game = {
val (nonEmptyCells, emptyCells) = game.cells partition {_.value.isDefined}
def homogenize[M[_], B, T <: HList](xs: HCons[M[B], T]): List[M[B]] =
xs.fold[Id, List[M[B]], Homogenize[M[B]]](new Homogenize)
def foldCells(xs: Vector[Cell], game: Game): Vector[Cell] = ...
val cellsWithCs = Vector((emptyCells grouped 4).toSeq: _*) flatMap { g => foldCells(g, game) }
val cellsWithCs2: Vector[Cell] = cellsWithCs map { x =>
val css = homogenize(evalMachine(x.pos, game.sqrtn) traverse cellsWithCs) map {_ exec x.cs}
x.copy(cs = (css find {_.size == 1}) | x.cs)
}
val solveCells = cellsWithCs2 map { cell =>
if (cell.cs.size == 1) cell.copy(value = cell.cs(0).some, cs = Vector())
else cell
}
game.copy(cells = nonEmptyCells ++ solveCells)
}
以下が前につまずいた問題を使った解法の出力だ:
scala> Solver.solve(game)
Some(4) Some(7) Vector() Vector() Some(6) Vector() Vector() Some(5) Some(9)
Vector() Vector() Vector() Some(2) Vector() Some(7) Vector() Vector() Vector()
Some(6) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(8)
Vector() Vector() Some(5) Vector() Some(8) Vector() Some(9) Vector() Vector()
Vector() Some(1) Vector() Some(7) Vector() Some(6) Vector() Some(8) Vector()
Vector() Vector() Some(8) Vector() Some(4) Vector() Some(2) Vector() Vector()
Some(8) Vector() Vector() Vector() Vector() Vector() Vector() Vector() Some(2)
Vector() Vector() Vector() Some(6) Vector() Some(3) Vector() Vector() Vector()
Some(9) Some(2) Vector() Vector() Some(5) Vector() Vector() Some(1) Some(6)
Some(4) Some(7) Some(2) Vector(1, 3, 8) Some(6) Vector(1, 8) Vector(1, 3) Some(5) Some(9)
Vector(1, 3, 5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4, 6) Vector(1, 3, 4)
Some(6) Vector(3, 5, 9) Vector(1, 2, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Vector(1, 3, 4, 7) Some(2) Some(8)
Vector(2, 3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Vector(2, 3) Some(1) Vector(2, 3, 4, 9) Some(7) Vector(2, 3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5, 6) Some(6) Vector(1, 4, 9) Vector(1, 7, 9) Vector(1, 4, 9) Vector(3, 4, 5, 7) Vector(3, 4, 7, 9) Some(2)
Vector(1, 5, 7) Vector(4, 5) Vector(1, 4, 7) Some(6) Some(2) Some(3) Some(8) Vector(4, 7, 9) Vector(4, 5, 7)
Some(9) Some(2) Vector(3, 4, 7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4, 7, 8) Some(1) Some(6)
Some(4) Some(7) Some(2) Vector(1, 3, 8) Some(6) Vector(1, 8) Vector(1, 3) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4) Vector(1, 3, 4)
Some(6) Vector(3, 5, 9) Vector(1, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Some(2) Some(1) Vector(3, 4, 9) Some(7) Vector(3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Vector(3, 4, 5, 7) Vector(3, 4, 7, 9) Some(2)
Vector(1, 5, 7) Vector(4, 5) Vector(1, 4, 7) Some(6) Some(2) Some(3) Some(8) Some(9) Vector(4, 5, 7)
Some(9) Some(2) Vector(3, 4, 7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4, 7) Some(1) Some(6)
Some(4) Some(7) Some(2) Vector(1, 3, 8) Some(6) Vector(1, 8) Some(1) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4) Vector(1, 3, 4)
Some(6) Vector(3, 9) Vector(1, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4, 7)
Some(2) Some(1) Vector(3, 4, 9) Some(7) Vector(3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5, 7)
Some(8) Vector(3, 4, 5) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Vector(3, 4, 5) Vector(3, 4) Some(2)
Some(1) Vector(4, 5) Vector(1, 4, 7) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Vector(4, 8) Some(5) Vector(4, 8) Vector(3, 4) Some(1) Some(6)
Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 3, 9) Some(7) Some(6) Vector(3, 4) Vector(3, 4)
Some(6) Vector(3, 9) Vector(1, 3, 9) Vector(1, 3, 4, 5, 9) Vector(1, 3, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Vector(3, 4, 6) Some(5) Vector(1, 3) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4)
Some(2) Some(1) Vector(3, 4, 9) Some(7) Vector(3, 9) Some(6) Vector(3, 4, 5) Some(8) Vector(3, 4, 5)
Vector(3, 7) Vector(3, 6, 9) Some(8) Vector(1, 3, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5)
Some(8) Some(3) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Some(5) Vector(3, 4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Vector(4, 8) Some(5) Vector(4, 8) Some(3) Some(1) Some(6)
Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Vector(1, 3, 9) Some(2) Vector(1, 9) Some(7) Some(6) Vector(3, 4) Vector(3, 4)
Some(6) Some(9) Some(3) Vector(1, 4, 5, 9) Vector(1, 9) Vector(1, 4, 5, 9) Some(7) Some(2) Some(8)
Vector(3, 7) Some(4) Some(5) Some(1) Some(8) Some(2) Some(9) Vector(3, 4, 6, 7) Vector(1, 3, 4)
Some(2) Some(1) Vector(3, 9) Some(7) Some(3) Some(6) Some(4) Some(8) Some(5)
Vector(3, 7) Vector(6, 9) Some(8) Vector(1, 5, 9) Some(4) Vector(1, 5, 9) Some(2) Vector(3, 6, 7) Vector(1, 3, 5)
Some(8) Some(3) Some(6) Vector(1, 4, 9) Some(7) Vector(1, 4, 9) Some(5) Some(4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Some(8) Some(5) Some(4) Some(3) Some(1) Some(6)
Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Some(1) Some(2) Some(9) Some(7) Some(6) Some(3) Some(4)
Some(6) Some(9) Some(3) Some(4) Some(1) Vector(1, 5) Some(7) Some(2) Some(8)
Vector(3, 7) Some(4) Some(5) Some(1) Some(8) Some(2) Some(9) Some(6) Some(3)
Some(2) Some(1) Some(9) Some(7) Some(3) Some(6) Some(4) Some(8) Some(5)
Vector(3, 7) Some(6) Some(8) Vector(5, 9) Some(4) Vector(5, 9) Some(2) Vector(3, 6, 7) Some(1)
Some(8) Some(3) Some(6) Some(9) Some(7) Some(1) Some(5) Some(4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Some(8) Some(5) Some(4) Some(3) Some(1) Some(6)
Some(4) Some(7) Some(2) Some(3) Some(6) Some(8) Some(1) Some(5) Some(9)
Some(5) Some(8) Some(1) Some(2) Some(9) Some(7) Some(6) Some(3) Some(4)
Some(6) Some(9) Some(3) Some(4) Some(1) Some(5) Some(7) Some(2) Some(8)
Some(7) Some(4) Some(5) Some(1) Some(8) Some(2) Some(9) Some(6) Some(3)
Some(2) Some(1) Some(9) Some(7) Some(3) Some(6) Some(4) Some(8) Some(5)
Some(3) Some(6) Some(8) Some(5) Some(4) Some(9) Some(2) Some(7) Some(1)
Some(8) Some(3) Some(6) Some(9) Some(7) Some(1) Some(5) Some(4) Some(2)
Some(1) Some(5) Some(4) Some(6) Some(2) Some(3) Some(8) Some(9) Some(7)
Some(9) Some(2) Some(7) Some(8) Some(5) Some(4) Some(3) Some(1) Some(6)
solved
これでより難しい数独の問題も解けるようになった。
aplicative 合成
Gibbons と Oliveira を引用すると:
モナドは長い間プログラムのいくつかの側面をモジュール化するのに都合が良い抽象体だと考えられてきた。しかし、モナドの合成は難しいことが分かっており、それが便利さを制限している。モナド変換子は解の1つだが、これはプログラムがあらかじめモナド変換子を念頭に置いて書かれることを必要とする。applicative functor にはより豊富な合成演算子の代数系があり、多くの場合モナド変換子を置き換えることができる。
現在 Scalaz 7.0.0-M4 にて使うことのできる Func はそれらの合成演算子を導入する。@&&& と :: 演算子は並列に applicative 関数を合成し (積ともいう)、@>>> 演算子は applicative 関数を逐次的に合成する。これらの合成は applicative 関数を返し、それはまた別の合成の一部となることができる。
全ての Monad は applicative だ。また、あらゆる Monoid も monoidal applicative として取り扱うことができる。(Naperian データ構造を zip することでも applicative が得られるらしいが、見たことが無い) 複数のモナドのインスタンスを取り扱う場合、それぞれのコンテキストを覚えておくのが難しくなってくる。applicative 合成は、特に強力な traverse メソッドを併せて使うことでこれを推理するのに便利な道具として使える。例えば、以下のコードは 3つの applicative 関数を並列に合成して 1つの HListFunc を返す。
def evalMachine(pos: (Int, Int), n: Int) =
horizEvalMachine(pos) :: vertEvalMachine(pos) :: groupEvalMachine(pos, n) :: AppFunc.HNil
次に、evalMachine((3, 1), game.sqrtn) traverse cellsWithCs を呼び出すことで cellsWithCs を1回走査しただけで State モナドの HList を得ることができる:
scala> Solver.evalMachine((3, 1), game.sqrtn) traverse cellsWithCs
res1: scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M,scalaz.typelevel.TCNil]]]#Product[scala.collection.immutable.Vector[Unit]] = GenericCons(scalaz.StateT$$anon$7@273cf345,GenericCons(scalaz.StateT$$anon$7@12874b23,GenericCons(scalaz.StateT$$anon$7@7055f055,GenericNil())))
それはあたかもそれぞれの評価マシンが独立して cellsWithCs を走査したかのようだ。3つの要素全てが同じ型を含むため、これは普通のリストへと変換することができる:
scala> homogenize(res1)
res2: List[scalaz.Unapply[scalaz.Applicative,scalaz.StateT[scalaz.Id.Id,Vector[Int],Unit]]{type M[X] = scalaz.StateT[scalaz.Id.Id,Vector[Int],X]; type A = Unit}#M[scala.collection.immutable.Vector[Unit]]] = List(scalaz.StateT$$anon$7@273cf345, scalaz.StateT$$anon$7@12874b23, scalaz.StateT$$anon$7@7055f055)
あとは、State モナドを別々に評価してもいいし、sequence を呼んでモナドのリストをリストのモナドに変換してもいい。大切なのは個々のマシンがいかにモジュール化されているかということだ。それぞれが独立して実行されることが期待されているため、いくつかの簡単なタスクに専念することができる。
今後の課題
現行の実装では、リストのような別のソースから HListFunc を生成することができなかった。これは HListFunc のそれぞれが中に格納している要素によって型が変わってしまうためだ。HList はこの問題に対して HList という共通トレイトを提供して回避している。HListFunc は Func を直接継承せずに暗黙に変換できるようにすればいいのかもしれない。
あともう1つみておく価値があるのは関数の非同期処理だ。ここまでみてきた並列合成はあくまで意味論的な並列であって、実際の処理は逐次的に実行される。抽象的な Future みたいなものと組み合わせることで、他のコアに負荷を分散できるかもしれない。