昔書いたocaml版（let recをつかわない）不動点関数導出

fix自体は以前書いたことがあって、そこでデコレーションや入れ替えができるという手法はメモ化が初めてじゃなかったり。で、その時かいたコードを発見した。

内部で名前を使わない場合と使う場合とで、なぜletとlet recを区別するのか、という点で疑問があって、recを「まったく」つかわないで再帰関数を実現する方法を考えたことがありました。結局recで名前を使わないようにするのと、不動点関数を求める関数が同じものだったという決着になったという感じでした（この動機もfixとはかけ離れてますけど）。

コードselfDef.ml:

let defFact = fun fact n -> if n = 0 then 1 else n * fact (n - 1)
let dummy = fun n -> -1

let result = defFact (defFact (defFact (defFact dummy))) 3

open Printf;;
printf "%d\n" result


type wrapGenDef = Wrap of (wrapGenDef -> (int -> int))

let unwrap = function Wrap(func) -> func

let fixpoint = fun funDef ->
  let genFunc = fun wrapped -> funDef (fun n -> (unwrap wrapped) wrapped n) in
  let wrapped = Wrap(genFunc) in
   genFunc wrapped

let factorial = fixpoint (fun fact n -> if n = 0 then 1 else n * fact (n - 1))

open Printf;;
printf "%d\n" (factorial 5)

上のdefFactは再帰構造を実現するときの構想コードで、トレースイメージみたいなものの最初の奴で関係ないものすね。unwrapだけが外にあるのもやっつけ的にやった感じ。あとfixpointというのは後からつけた名前だと思う。当初はrecFuncだったような。。。

このfix関数が複雑になったのは、普通の式が即時評価なのと厳密に型が決まってないとだめだったから。即時性のために型構築子で一旦関数をつつんで(wrapped)それを渡していて、型システムのためにその型構築子も複雑になった（wrapGenDef）。さらに、単純にwrappedをユーザー関数に渡すとユーザー関数がunwrapしないといけないのとさらにwrappedをそれにわたさないのといけないので、それをやってしまう関数に作り変えている(genFunc)。

このgenFuncの定義のところでなんかやっちゃえるようにすればdecoratorっぽくなる。のかな。でも、この時点でfixpointを出す目的からは外れてるかも。

いろいろな関数に対応にするには単純にwrapGenDefを多相化すればいいだけみたい。

多相化したfixpoint(wrap,unwrapも対比させて内部に閉じ込めてみる):

type ('a, 'b) wrapGenDef = Wrap of (('a, 'b) wrapGenDef -> ('a -> 'b))

let fixpoint = fun funDef ->
  let wrap = fun func -> Wrap(func) in
  let unwrap = function Wrap(func) -> func in
  let genFunc = fun wrapped -> funDef (fun n -> (unwrap wrapped) wrapped n) in
  let wrapped = wrap genFunc in
    genFunc wrapped
(*
val fixpont : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
*)

いまさらだが無限ストリームと似た形になってるんだなあと思った。

サンプル

let findN = fixpoint (fun findn n s -> match s with [] -> false | x :: xs -> if x == n then true else findn n xs)

printf "%b\n" (findN 121 [12;312;423;1;232;12]);;