この記事は何

最近 Koka と Algebraic Effects and Handlers で遊んでいる。

今日は非決定的計算を表す作用で探索アルゴリズムを書いて遊んだので、忘れないうちに書いたものを記事に残しておく。

非決定的計算の定義

まずは、この記事の主人公となる、非決定的計算を表現する作用を定義する。

この non-deterministic 作用は、私の好きな Haskell でいうと Alternative のようなものだ。

// 非決定的計算
effect non-deterministic
  // Nothing や Nil などの失敗を表現する。Alternative の empty に対応する。
  // empty :: Alternative f => f a
  final ctl fail() : a

  // True の場合の継続と False の場合の継続に場合分けをする。
  // if flip() then a() else b() のように使う。
  // (<|>) :: Alternative f => f a -> f a -> f a
  ctl flip() : bool

// non-deterministic が長いので、別名をつける。
// ndet は別の定義が標準ライブラリに存在するが、
// この記事では以後 ndet の定義はこちらを参照する。
alias ndet = non-deterministic

// 非決定的計算を伴うアクションの型
// non-deterministic action の略のつもり
alias ndet-act<e, a> = () -> <ndet | e> a

// 発散する可能性のある、非決定的計算を伴うアクションの型
// non-deterministic divergent action の略のつもり
alias ndet-dact<e, a> = () -> <ndet, div | e> a

この記事では、これを使っていくつかの探索アルゴリズムを書くことで、これが確かに非決定的計算を表現していることを確認する。

アクションの実行

ndet を文脈に持つ値を返す関数を、この記事では (ndet の) アクションと呼ぶ。
すなわち、ここではアクションとは非決定的な計算のことだ。

まずは、非決定的計算を実行して list や maybe に落とし込むハンドラを紹介する。

一つ目は、非決定的計算が取りうるすべての結果を返す関数だ。
flip() は、継続を True で再開した場合と False で再開した場合とで2パターン実行する。
fail() が呼び出された時点で、その継続は破棄される。

これは概ね Alternative のリストに対する実装だ。

fun run-to-list(action : ndet-act<e, a>) : e list<a>
  with
    return(x)  [x]
    final ctl fail() []
    ctl flip() resume(True) ++ resume(False)
  action()

二つ目は、まずは True で以後の継続を実行し、そこで fail() が実行された場合は False で以後の継続を実行しなおす関数だ。
最後まで実行された継続が見つかったら Just に包んで返す。

これは概ね Alternative の Maybe に対する実装だ。

fun run-to-maybe(act : ndet-act<e, a>) : e maybe<a>
  with
    return(a)  Just(a)
    final ctl  fail() Nothing
    ctl flip() resume(True).or { resume(False) }
  act()

// ヘルパー
fun or(ma : maybe<a>, other : () -> e maybe<a>) : e maybe<a>
  match ma
    Just(a) -> Just(a)
    Nothing -> other()

アクション (探索)

プリミティブなアクション

最も基本的なアクションは、具体的なデータ型、典型的には list<a> を、上で定義した一般化された非決定計算に「持ち上げる」アクションだ。
このアクションはリストの要素を先頭から順に返す。探索という見方をすれば、これは線形探索だ。

fun lift(list : list<a>) : ndet a
  match list
    Nil         -> fail()
    Cons(x, xs) -> if flip() then x else lift(xs)

これの他には、少しつまらない例だが、maybe を持ち上げたり、任意の値をただ非決定的な文脈に持ち込むアクションを考えることができる。

fun lift(maybe : maybe<a>) : ndet a
  match maybe
    Nothing -> fail()
    Just(a) -> a

fun lift-trivial(a : a) : ndet a
  a

線形探索

最も単純な探索といえば、線形探索だろう。

リストの持ち上げは線形探索でもあるといったから、それを確かめてみよう。
名前だけ分かりやすくする。

fun linear-search(l : list<a>) : ndet a
  lift(l)

例えば、リストの中から条件を満たす値を探すような関数は、次のようにして書くことができる。

fun find-if(l : list<a>, pred : a -> bool) : maybe<a>
  run-to-maybe
    val a = linear-search(l)
    if pred(a) then a else fail()

a には戻り値となる可能性のある値、つまりリストの要素が順に入る。
この a が条件を満たせばそれを限定継続の戻り値とし、そうでなければその継続は破棄している。

注目するべきは linear-search 関数の外で検索条件を指定している点だ。
このような書き方をしていても pred(a) を満たす要素が発見された時点で探索は打ち切られている。

guard アクション

先の例に出てきた、「条件を満たさない場合は fail()」というコードは頻出するので、guard 関数を導入する。
これは Haskell プログラマには慣れ親しんだものだ。

fun guard(b : bool) : ndet ()
  if b then () else fail()

これを使えば、先の関数は下のように書き換えられる。

fun find-if(l : list<a>, pred : a -> bool) : maybe<a>
  run-to-maybe
    val a = linear-search(l)
    guard(pred(a))
    a

深さ優先探索

探索といえば、深さ優先探索だろう。

非決定的計算を利用した深さ優先探索は、きわめて簡潔かつ一般的なものだ。

fun dfs(a : a, f : a -> e list<a>) : <ndet, div | e> a
  if flip()
  then a
  else {
    val list = mask<div> { mask<ndet> { a.f() } }
    dfs(list.lift(), f)
  }

ここで定義した関数 dfs は、あるノード a とそのノードを発展させる関数 f をパラメータとして受け取る。

例えば、二分木に対して深さ優先探索を適用する場合は、あるノードと子ノードを列挙する関数をパラメータとして渡せばよいことになる。

// 二分木の定義
type binary-tree<a>
  Node
    value : a
    left  : binary-tree<a>
    right : binary-tree<a>
  Empty

// 子ノードを列挙する関数
fun children(btree : binary-tree<a>) : list<binary-tree<a>>
  match btree
    Empty         -> []
    Node(_, l, r) -> [l, r]

使い心地は次のような感じだ。

// 深さ優先探索で Empty を除いて列挙する
// => [Node<"Hello">,Node<"Hallo">,Node<"Ciao">,Node<"Bonjour">,Node<"Hola">]
fun list-nodes-dfs() : div list<binary-tree<string>>
  val btree = Node(
    "Hello",
    Node("Hallo",
      Empty,
      Node("Ciao", Empty, Empty)
    ),
    Node("Bonjour",
      Empty,
      Node("Hola", Empty, Empty)
    )
  )
  run-to-list
    val a = dfs(btree, children)
    guard(a.is-node()) // Node を選択する (Empty を除外する)
    a

dfs を非決定的な文脈の中で呼び出すと、結果に含まれる可能性がある値が、深さ優先探索で当たった順に返ってくる。
最終的な結果に含めたくない Empty は guard を用いて弾いている。

幅優先探索

幅優先探索も、きわめて直感的な実装だ。
同じ全探索なので、深さ優先探索と型や使い方は全く同じだ。

// bfs' は子ノードのみを返すので、ルートノードだけは予め返しておく
fun bfs(a : a, f : a -> e list<a>) : <ndet, div | e> a
  if flip() then a else bfs'(a, f)

// bfs のヘルパー。子ノードを順に追加するやつ。a の直接の子ノードを返し終わったら再帰呼び出しを行う
fun bfs'(a : a, f : a -> e list<a>) : <ndet, div | e> a
  val list = mask<ndet> { mask<div> { a.f() } }
  if flip() then list.lift() else bfs'(list.lift(), f)

DFSと同じように使うことができる。
DFSの結果とは順序が変わり、きちんと幅優先探索の順序で返されている。

// => [Node<"Hello">,Node<"Hallo">,Node<"Bonjour">,Node<"Ciao">,Node<"Hola">]
fun list-nodes-bfs() : div list<binary-tree<string>>
  val btree = Node(
    "Hello",
    Node("Hallo",
      Empty,
      Node("Ciao", Empty, Empty)
    ),
    Node("Bonjour",
      Empty,
      Node("Hola", Empty, Empty)
    )
  )
  run-to-list
    val a = bfs(btree, children)
    guard(a.is-node)
    a

特定の値を探す

幅優先探索で特定の値を探してみよう。

次の例は value="Bonjour" であるようなノードを探すコードだ。

// => Just(Node{value="Bonjour",left=Empty,right=Node{value="Hola",left=Empty,right=Empty}})
fun find-node-bfs() : div maybe<binary-tree<string>>
  val btree = Node(
    "Hello",
    Node("Hallo",
      Empty,
      Node("Ciao", Empty, Empty)
    ),
    Node("Bonjour",
      Empty,
      Node("Hola", Empty, Empty)
    )
  )
  run-to-maybe
    val a = bfs(btree, children)
    match a
      Empty         -> fail()
      Node(v, _, _) ->
        guard(v == "Bonjour")
        a

同じ bfs 関数を使って、ノードの列挙とノードの検索を行っている。
これは抽象化した非決定計算の力といえるだろう。

おわりに

非決定的計算を抽象化した作用を使って、基本的な探索アルゴリズムを書いた。