タグ

lispとY Combinatorに関するNobuhisaのブックマーク (6)

  • Y combinator. そして末尾再帰に取り付かれる - rayfillのプログラムネタ帳

    不動点演算子といってラムダ計算やらコンビネータ理論やらのものらしいです。 ちゃんと調べてないのでよくわかってません(笑) ただ、これを使うと無名関数を再帰することができる、ということです。 で自分で実装して考えてみる。 まずは再帰のお供、fact関数。 (defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1))))) 末尾再帰にもなっていませんがとりあえず実装。 ここから進めていきましょう。 この関数をlambda関数にした場合、何が使えなくて再帰できないのか? そう、関数名fact、というか関数自身です。 んじゃどうすればいける?と考えると・・・ないものは無いんで外部から差し込むしかないよなーということになります。 つまり自分自身を引数として受け取って(なんか話が矛盾してきた!(笑))それをfuncallすれば再帰できるはず、ということで定義した

    Y combinator. そして末尾再帰に取り付かれる - rayfillのプログラムネタ帳
    Nobuhisa
    Nobuhisa 2009/07/17
    Y Combinator と末尾再帰の最適化
  • combinator - Nobuhisa's diary

    コンビネータとは自由変数を含まないλ項のことをいいますが、Yコンビネータ以外あまり取り上げられていない気がするのですが、これも100年に1度の金融危機の影響かとか、WBC楽しみですねだとか、そういえば今年雪祭り行けなかったんですよとか、最近携帯変えましたとか色々あるのですが、自分の練習もかねて、そんなコンビネータ達と戯れたいと思います。 沢山ある! Y以外にも広く知られている(?)コンビネータはいっぱいあるようですが、その中からいくつか。 I ≡ λx.x K ≡ (λx.(λy.x)) //以下、簡単に λx y.x と書きます F ≡ λx y.y M ≡ λx.xx S ≡ λx y z.xz(yz) B ≡ λx y z.x(yz) C ≡ λx y z.xzy L ≡ λx y.x(yy) Y ≡ (λx.xx)(λx.xx) (SLL) (当てるアルファベットが違うのはたまに見

    combinator - Nobuhisa's diary
    Nobuhisa
    Nobuhisa 2009/02/16
    頑張ってOcamlのYを理解しなくては・・・!
  • 不動点オペレータについて

    不動点オペレータY 階乗関数は、 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) のように、再帰的に定義できる。 再帰的定義を行なう場合はdefineやletrecを使うけど、 代わりにletを使うと再帰的定義はできない。 defineやletrecをどうしても使いたくないなら、多少工夫がいる。 例えば、factの引数を増やすという方法がある。 (let ((fact (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1))))))) (fact fact 10)) ⇒ 3628800 (中略) 不動点オペレータYを使うと次のように書ける。 (let* ((Y (lambda (g) ((lambda (s) (g (lambda (x) ((s s) x))

  • fix と memo とそのおまけ。 - 嫌気性平均律

    不動点オペレータと関数のメモ化で大いに遊ぶのが流行っているみたいで(k.inaba さんの発端の記事、結城浩さんによるリンク集)、楽しそうなのでひっそり書いてみます。Common Lisp で、というか xyzzy でちょこちょこしてみます。 まずは普通に。 とりあえず不動点オペレータを教科書的に書いてみます。funcall が健全な精神に対して極めて有害そうであることがよく判ります。 ;;;figure.1 (defun %fib (f) #'(lambda (x) (if (<= x 1) 1 (+ (funcall f (- x 1)) (funcall f (- x 2)))))) (defun fix (f) (funcall #'(lambda (g) (funcall g g)) #'(lambda (h) #'(lambda (x) (funcall (funcall f

    fix と memo とそのおまけ。 - 嫌気性平均律
  • 不動点演算子ふたたび - sumiiの日記

    (追記:Yコンビネータって何に使うの?) Yコンビネータ(Curryの不動点演算子)を説明するのがプチブーム(死語)らしいので、ふたたび挑戦。 まず、ふつーに再帰関数factをSchemeで定義してみる。 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))この定義は、右辺にfact自身が出現するので、再帰的定義なのであった。ここから右辺にfactが出現しないようにするのが目標。とりあえず、factを関数の引数として外から受け取るようにしてみる。 (define make-fact (lambda (my-fact) (lambda (n) (if (= n 0) 1 (* n (my-fact (- n 1)))))))これは( (make-fact fact) 10)みたく使えるが、make-factを呼び出す際に

    不動点演算子ふたたび - sumiiの日記
  • Y Combinator

    In this file we derive the Y combinator, one of the fundamental results of recursive procedure theory. You already know that in some cases it is not necessary to give a procedure a name. For example, ((lambda (x) (+ x 1)) 6) adds 1 to 6 without naming the procedure that does it. But, what about a recursive procedure? For example, (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) whi

  • 1