Hatena::Groupcoders

ラシウラ出張所 このページをアンテナに追加 RSSフィード

2007/05/11

[][] 関数不動点  関数の不動点 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  関数の不動点 - ラシウラ出張所  関数の不動点 - ラシウラ出張所 のブックマークコメント

OCaml:

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

let fixpoint = fun funDef ->
  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

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

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

Haskell:

fix f = f (fix f)

fact = fix $ \fn n -> if n < 1 then 1 else n * fn (n - 1)

main = do
    putStrLn $ show (fact 5)
    return ()

上のMLのようにhaskellで書くとghcコンパイルがとまらなくなりました。

data Wrap a = Wrap ((Wrap a) -> a)

-- cannot compile, compiler infinit loop
fix f = genfunc wrapped
    where
      unwrap (Wrap g) = g
      genfunc wrapped = f ((unwrap wrapped) wrapped)
      wrapped = Wrap genfunc

fact = fix (\fact -> (\n -> if n == 0 then 1 else n * (fact (n - 1))))
main = putStrLn $ show (fact 10)