ネタ記録庫/不動点コンビネータ

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

FIXME:説明追加&リンク追加

型なしλ計算 †

ラムダ式で書くと

λf.(λx.f(xx))(λx.f(xx))

ただしこれでは(xx)に型が付かない。

Haskell †

-- 不動点演算子 Y
y :: a -> a -> a
y f = f (y f)

-- yの使用例 再帰関数 fact を 高階関数 fac の不動点として定義する
fact = 
  let fac f = ?x -> 
      if x == 0 
        then 1 
        else x * f (x-1) 
  in y fac

Ocaml †

-- 不動点演算子
# let rec y f = f (lazy (y f))
 val y : ('a lazy_t -> 'a) -> 'a = <fun>
-- yの使用例
# let fac f = function
    0 -> 1
  | x -> x * (Lazy.force f) (x - 1)
# let fact = y fac
-- こっちが普通かな...?
# let y f x = f (y f) x

解説ページ &dagger;

英語 &dagger;

日本語 &dagger;


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2007-12-24 (月) 03:39:34 (4685d)