不動点と不動点コンビネータ

2011-12-06 プログラミング

ある関数 $f(x)$ について、 $x_0 = f (x_0)$ となる $x_0$ が存在するとき、 $x_0$ を $f$ の不動点といいます。
また、 $x_0$ に十分近い $x$ に対し、列 $x, f(x), f(f(x)), \ldots$ が $x_0$ に収束するとき、 $x_0$ は $f$ の吸引的不動点である、といいます。
(参考:Wikipedia)

吸引的不動点は、値が変化しなくなるまで関数適用を繰り返すだけなので、プログラムで簡単に書くことができます。
以下のfixは初期値xからfの吸引的不動点を求める関数です。
汎用性のため、一致検査関数はequalとして引数で取ります。

let rec fix equal f x =
  let x' = f x in
    if equal x x' then x
    else fix equal f x'

さて、こんなものを作って何が嬉しいかというと、「一致するまで繰り返す」ようなループを隠蔽することができます。
例えば、ニュートン法は以下のように書くことができます。
ただし、Float.aequal e x yは、xとyが誤差e以内で等しい、という関数とします。

let e = 1e-8
let deriv f x = (f (x +. e) -. f x) /. e
let newton f =
  let f' = deriv f in
  let newton_f x =
    x -. (f x /. f' x)
  in
    fix (Float.aequal e) newton_f

newton_fが「ある値から次のステップの値を得る関数」で、newtonはこの関数の(浮動小数点なので誤差を含む)不動点を求める、という関数になります。
素直にプログラムを書くとlet recが出てきてしまうのですが、アルゴリズムの意味を考えるとfixを使ったほうがより「らしい」プログラムになる気がします。

また、ある操作の反射推移閉包を求める場合などにも有用です。
例として、有向グラフを以下のように「始点と終点の組」の集合で表すとします。

module Path = Set.Make
  (struct
     type t = int * int
     let compare = compare
   end)
let path_of_list l =
  List.fold_right Path.add l Path.empty
let path = path_of_list
  [(1,2);
   (1,3);
   (2,4);
   (2,5);
   (3,5);
   (4,5);
   (5,3)]

この時、ある頂点から0回以上遷移して辿りつける頂点集合は、以下のnexts関数で得ることができます。
ちょっとユーティリティが多いのでごちゃごちゃしてますが……本体は少ないです。

module Int =
struct
  type t = int
  let compare (x:int) = compare x
end
module IntSet = Set.Make(Int)
let is_to_list is = List.rev (IntSet.fold (fun x l -> x::l) is [])
let is_equal x y = IntSet.compare x y = 
let (|>) x f = f x
let id x = x
(* グラフ関数ここから *)
let next_single path x =
  Path.fold (function
         (x',y) when x = x'
           -> IntSet.add y
           | _ -> id) path IntSet.empty
let next path xs =
  IntSet.fold (fun x ->
         next_single path x
           |> IntSet.union) xs xs
let nexts path x =
  fix is_equal (next path) (IntSet.singleton x)

next_singleが「頂点xから1回の遷移で辿りつける頂点の集合」、nextが「頂点集合xsから0回あるいは1回の遷移でたどりつける頂点の集合」で、nextsはnextの推移閉包です。
この場合、fixというよりはclosureみたいな名前にしたり、t_r_closureなどにして反射関係も隠蔽したほうが綺麗でしょうが、少なくともループで書くよりは綺麗なんじゃないか、と思います。
ちなみに、nextsの実行例は以下のようになります。

# path_to_list path;;
- : Path.elt list = [(1, 2); (1, 3); (2, 4); (2, 5); (3, 5); (4, 5); (5, 3)]
# next_single path 1 |> is_to_list;;
- : IntSet.elt list = [2; 3]
# nexts path 1 |> is_to_list;;
- : IntSet.elt list = [1; 2; 3; 4; 5]
# nexts path 2 |> is_to_list;;
- : IntSet.elt list = [2; 3; 4; 5]
# nexts path 3 |> is_to_list;;
- : IntSet.elt list = [3; 5]
# nexts path 4 |> is_to_list;;
- : IntSet.elt list = [3; 4; 5]
# nexts path 5 |> is_to_list;;
- : IntSet.elt list = [3; 5]

ただし、閉包を求めるにしてもクリーネ閉包などは集合が発散するので無理です。
fixが停止しなくなります。
ま、そもそも有限集合で表せないものなので当然なのですが。
クリーネ閉包を表現するなら、オートマトンを使うのがベターでしょう。

基本的に、「何らかの操作を変化しなくなるまで繰り返す」ような関数では、内部でloopを書くことになるので、意味合いとしてfixを使ったほうが綺麗になる気がします。

さて、fixを使って、gcdなんかも一応書くことができます。

let gcd =
  let one_step (n,m)=
    if n > m then (n - m,m)
    else (m,n)
  in
    fix equal one_step

が、この場合には戻り値が両方共gcdであるようなタプルになります。
しかも、より効率のよいmodを使ったバージョンでは最後に0除算が発生してしまいエラーになります。
これは、操作one_stepを、最終的にうまく変化しなくなるように定義しただけで、本質的には「片方が0になったら操作を終了する」ような関数にするべきだからですね。

この場合、不動点コンビネータを使ったほうがよさげです。
普通、不動点演算子といった場合はこちらを指しますね。

let rec fixf f x = f (fixf f) x
let gcdable gcd = function
    (x,) -> x
  | (x,y) -> gcd (y,x mod y)
let gcd = fixf gcdable

実行すると、以下のようにちゃんとgcdを計算することができます。

# gcd (18,12);;
- : int = 6

内部での計算列は以下のようになります。

 gcd (18,12)
= fixf gcdable (18,12)
= gcdable (fixf gcdable) (18,12)
= fixf gcdable (12,6)
= gcdable (fixf gcdable) (12,6)
= fixf gcdable (6,)
= gcdable (fixf gcdable) (6,)
= 6

再帰するときに呼ぶ関数を、引数として受け取っているわけですね。
また、Yコンビネータ $Y = \lambda f. (\lambda x. f (x x)) (\lambda x. f (x x))$ は、型付きラムダ計算であるOCamlでは直接実装できませんが、以下のように型を明示することで実現できるようです。
(参考：Wikipedia)

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x
let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a))

先ほどと同じく、gcdを計算してみます。

# let gcd = y gcdable;;
val gcd : int * int -> int = 
# gcd (12,18);;
- : int = 6

内部での計算列は途中まで書いてましたが、あまりに複雑なので省略。
端的に言うとWikipediaのYコンビネータの式に、Inとoutを挟み込んだ感じになります。

ま、正直な話不動点演算子は普通にlet recで書いたほうがわかりやすいです。
gcdableの第一引数gcdなんておもいっきり冗長な引数ですしね。

let rec gcd x y =
  if y =  then x
  else gcd y (x mod y)

というわけで、普通の再帰関数はlet recの方がわかりやすいけど、吸引的不動点とか閉包みたいな「ある操作を変化しなくなるまで繰り返す」的操作はfixとかで再帰を隠蔽したほうがわかりやすい気がする、という話でした。