型付きのタスク同士の依存関係を解決するソルバは書けるのかその1

こういう話題:

今日 @yigarashi_9 と会話してて、「相互に依存し合ったタスクの集合からグワッとDAGを生成してトポロジカルソートして一つずつ解決していくみたいなパターンあるよね」みたいな話をしたけど、なんか名前あったっけみたいなモヤモヤが、ずっと続いてる
— windymelt (@windymelt) 2022年6月14日

ところで、タスクの入出力を型で守って、依存関係をタスクの合成として表現していくと面白いのではないか。コンパイル時に依存関係は確定していて、動くことが保証されている、みたいな。要するに型付きのMakeみたいなのは書けないのか。

というわけで、書けるかやってみる。

import cats._
import cats.implicits._

素朴に考えると、タスクをDAGに変換し、トポロジカルソートを行って依存関係を解消して、全ての出力を得たい。そして、タスクの入出力は型により守りたい。

まずタスクについて考えていこう。

タスクは複数の入力と複数の出力、そしてそれを処理する関数を持っている。とりあえずIntで考える。

type Task0 = Function1[Int, Int]

// 1足すタスクを考えてみよう:
val incTask: Task0 = (n: Int) => n + 1
// incTask: Task0 = <function1>
incTask(1)
// res0: Int = 2

// ここではまず入出力をIntで固定したが、Intとは限らないのでパラメータ化する:
type Task01[I, O] = Function1[I, O]

// Intを文字列にするタスクを作ることができる:
val toStringTask: Task01[Int, String] = (n: Int) => n.toString
// toStringTask: Task01[Int, String] = <function1>
toStringTask(42)
// res1: String = "42"

パラメータを複数持てるようにShapelessのHListを導入する。

// パラメータは複数持つことができるので、パラメータをHListで管理する:
import shapeless.HList
type Task02[O] = Function1[HList, O]

// 2つのIntを足すタスクを作ることができる:
import shapeless.{HNil, ::}
val plusIntTask: Task02[Int] = { case (n: Int) :: (m: Int) :: HNil => n + m }
// plusIntTask: Task02[Int] = <function1>
plusIntTask(10 :: 20 :: HNil)
// res2: Int = 30

// 異なるshapeのHListを渡すことはできない:
// plusIntTask(10 :: HNil)

// がしかしこれは実行時エラーになってしまうので、コンパイル時に検出できるようにする。
// これはTask01を使うだけでよい:
val plusIntTask2: Task01[Int :: Int :: HNil, Int] = { case n :: m :: HNil =>
  n + m
}
// plusIntTask2: Task01[Int :: Int :: HNil, Int] = <function1>
plusIntTask2(10 :: 20 :: HNil)
// res3: Int = 30

// 今回はコンパイルエラーとして阻止できる:
// plusIntTask2(HNil)

// 同様にして、出力も複数にできる:
val swapIntTask: Task01[Int :: Int :: HNil, Int :: Int :: HNil] = {
  case n :: m :: HNil => m :: n :: HNil
}
// swapIntTask: Task01[Int :: Int :: HNil, Int :: Int :: HNil] = <function1>
swapIntTask(10 :: 20 :: HNil)
// res4: Int :: Int :: HNil = 20 :: 10 :: HNil

これだと自由にTask01を作れてしまうので、型の制約をつける。

// Taskの入出力はHListに限定したいので、Traitで制約する:
trait Task03[I <: HList, O <: HList] {
  type Repr = Function1[I, O]
}
val swapIntTask2: Task03[Int :: Int :: HNil, Int :: Int :: HNil]#Repr = {
  case n :: m :: HNil => m :: n :: HNil
}
// swapIntTask2: (Int :: Int :: HNil) => Int :: Int :: HNil = <function1>

// これで、HListではない入出力は禁止された:
// val foo: Task03[Int, Int]#Repr = (n: Int) => n * 2

// コンパニオンオブジェクトを使って書きやすくしておこう:
object Task03 {
  def apply[I <: HList, O <: HList](f: Function1[I, O]): Task03[I, O]#Repr = f
}

val multTask = Task03[Int :: Int :: HNil, Int :: HNil] { case n :: m :: HNil =>
  n * m :: HNil
}
// multTask: (Int :: Int :: HNil) => Int :: HNil = <function1>
multTask(10 :: 20 :: HNil)
// res5: Int :: HNil = 200 :: HNil

// もちろん、型による防御が有効だ:
// Task03[Int, Int] ((n: Int) => n + 1)

さて、入出力に依存関係があるということは、それぞれの入出力に名前を与えて、同じ名前の入力と出力とをくっつけるという方式で依存関係を表現できる。

// それぞれの入出力に名前を与えて、依存関係を追いかけられるようにしたい。
import shapeless.syntax.singleton._
import shapeless.labelled.FieldType
val combineFizzBuzz = Task03[FieldType["fizz", String] :: FieldType[
  "buzz",
  String
] :: HNil, FieldType["fizzbuzz", String] :: HNil] { case n :: m :: HNil =>
  "fizzbuzz" ->> s"${n}${m}" :: HNil
}
// combineFizzBuzz: (FieldType["fizz", String] :: FieldType["buzz", String] :: HNil) => FieldType["fizzbuzz", String] :: HNil = <function1>
combineFizzBuzz("fizz" ->> "fizz" :: "buzz" ->> "buzz" :: HNil)
// res6: FieldType["fizzbuzz", String] :: HNil = "fizzbuzz" :: HNil

// これにより、名前で防御される:
// combineFizzBuzz("foo" ->> "foo" :: "bar" ->> "bar" :: HNil)

面白いのが、もう合成できるという点。

// すると、タスク同士を合成できるようになる:
val produceFizzAndBuzz = Task03[HNil, FieldType["fizz", String] :: FieldType[
  "buzz",
  String
] :: HNil](_ => "fizz" ->> "Fizz" :: "buzz" ->> "Buzz" :: HNil)
// produceFizzAndBuzz: HNil => FieldType["fizz", String] :: FieldType["buzz", String] :: HNil = <function1>
produceFizzAndBuzz(HNil)
// res7: FieldType["fizz", String] :: FieldType["buzz", String] :: HNil = "Fizz" :: "Buzz" :: HNil

val composedFizzBuzz = produceFizzAndBuzz >>> combineFizzBuzz
// composedFizzBuzz: HNil => FieldType["fizzbuzz", String] :: HNil = scala.Function1$$Lambda$9611/79488238@5e16f009
composedFizzBuzz(HNil)
// res8: FieldType["fizzbuzz", String] :: HNil = "FizzBuzz" :: HNil

これは面白い。

問題は、タスクが複雑に絡みあっていることだ。自動的に型を組合わせて、適切な入力を接続してほしい。タスク同士をどんどん合成していくうちに自動的に入出力が接続されて、最終的には未接続の入力だけが残っている、という状態になっていてほしい。

まずはFunctorから考えていこう。その前に、Task03をめでたくTaskとして昇格させておく:

object Task {
  trait Task[I <: HList, O <: HList] {
    type Repr = Function1[I, O]
  }
  def apply[I <: HList, O <: HList](f: Function1[I, O]): Task[I, O]#Repr = f
}

Functorのインスタンスを定義する必要はない。なぜなら、Function1は自動的にFunctorになっているからだ。

def f1[A] = implicitly[Functor[Function1[A, *]]]
f1[Int :: HNil]
// res9: Functor[[β$0$](Int :: HNil) => β$0$] = cats.instances.Function1Instances$$anon$7@355511cc

// だからfmapもできる:
val composedFizzBuzz2 = produceFizzAndBuzz fmap combineFizzBuzz
// composedFizzBuzz2: HNil => FieldType["fizzbuzz", String] :: HNil = scala.Function1$$Lambda$9611/79488238@7ed56f25

// じゃあSemigroupになってる？
// produceFizzAndBuzz |+| combineFizzBuzz
// これはダメだ。

// Task同士を合成できるように、Semigroupを実装しよう。
// Semigroup.instance[Task.Task[A, B]] { case x -> y =>    
// }
// と思ったけど、Taskの型同士は同じではないから、簡単にcombineすることはできなそう。