遅延評価の良いところ

This entry was posted by 向井 淳 on Wednesday, 25 August, 2004
>花谷さんの日記で、 > >fix f = f (fix f)
fact = fix (\f x -> if x <= 0 then 1 else x * f (x - 1)) > >という記述があって、おかしいな、 OCaml で fix をやったときにはもっと複雑だった気が、と思い、ほとんど同じコードを書いてみたら、 fact の定義でスタックオーバフローになってしまった。評価が eager なので、 fix に関数を適用した段階で無限に展開されてしまうのがその理由。そういうわけで、この簡潔な定義は遅延評価でないと不可能。……やっぱ遅延評価はいいなぁ。 > >OCaml で fix を定義するには、たとえば再帰的な型を用いて次のようにする。 > >type ('a, 'b) x = Psi_inv of ( ('a, 'b) x -> 'a -> 'b);;
let psi (Psi_inv f) = f;;
let fix g =
let h y = g (fun x -> psi y y x) in
h(Psi_inv h);;
let fact = fix (fun f x -> if x <= 0 then 1 else x * f (x - 1));; > >なお、このコードは、長谷川真人氏の >北大での集中講義 >の資料をもとにしています。 > >一見、コードを読んでもさっぱりわからんと思いますが、ひとつひとつ展開していけば、ちゃんと階乗になるおとがわかります。この場合、関数適用を間に噛ませることで、展開が遅延されているわけですね。 > >x の型が 'a, 'b というように引数の型と返り値の型を持つのには、何か理由があった気がしましたが忘れました。 >
Category: Uncategorized
You can follow any responses to this entry via RSS.
Both comments and trackbacks are currently closed.

Comments are closed.