Hatena::Grouperlang

weekend erlang programmer

ここの更新は止まってしまいました。面倒なので全部kuenishiの日記に書くことにしました。
 | 

{2010, 4, 5}

Y combinator memo 23:37 はてなブックマーク - Y combinator memo - weekend erlang programmer Y combinator memo - weekend erlang programmer のブックマークコメント

ファイルを削除するので…ま、どれも失敗の記録です。こんな風に試行錯誤したログ。

Y = \f.(\x.f(x x))(\x.f(x x))
Y g = (\x.g(x x))(\x. g(x x))
    = g(\x.g(x x) \x.g(x x))
     -> \g.g(\x.g(x x) )(\x.g(x x))???

Fa= fun(Fact)-> fun(1)->1; (N)-> N * Fact(N-1) end end.
Y = fun(F)-> (fun(X)->F( X(X) ) end)(fun(X)->F(X(X)) end) end.
Y(Fa) --> (fun(X)->Fa(X(X)) end)(fun(X)->Fa(X(X)) end )
      --> Fa( (fun(X)->Fa(X(X))end)(fun(X)->Fa(X(X)) end) )
      --> Fa( Fa( (fun(X)->Fa(X(X))end)(fun(X)->Fa(X(X)) end) ) )

Y = fun(F)-> (fun(X)->F(X(X)) end)(fun(X)->F(X(X))) end)  end
		     
fun(G)-> G(( fun(X)->F(X(X)) end)( fun(X)->F(X(X)) end)) end
<( fun(X)->F(X(X)) end)( fun(X)->F(X(X)) end)>
(Y(Fa))(10) --> (<(fun(X)->Fa(X(X))end)(fun(X)->Fa(X(X)) end)>(G))(10)

(Y(Fa))(10) --> (Fa( (fun(X)->Fa(X(X))end)(fun(X)->Fa(X(X)) end) ))(10)
            --> 10 * ( Fa( (fun(X)->Fa(X(X))end)(fun(X)->Fa(X(X)) end) ) )(9)

      --> 10 * (fun(X)->Fa(X(X))end)(fun(X)->Fa(X(X)) end)
      --> 10 * (Y(Fa))(9).
      --> 10 * Fa( (fun....)

Y = fun(F)-> (fun(X)-> F(X (X)) end)(fun(X)->F(X(X))) end.
Y = fun(F)-> fun(N)-> (fun(X)-> (F(X (X)))(N) end)(fun(X)->F(X(X)) end ) end end.

Y = fun(F,N)-> (fun(X,M)->F(X(X,M),M) end)(fun(X,M)->F(X(X,M),M) end, N) end.				    
Fa = fun(_,1)->1; (Fact,N)->N*Fact(Fact,N-1) end.

Y = fun(F)-> fun(N)-> (fun(X)->F( fun(M)->X(X) end ) end)(fun(X)->F(fun(M)-> X(X) end) end) end end.

Fa = fun(_,1)->1; (Fact,N)->N*Fact(Fact,N-1) end.

Fa = fun(_, 1)->1; (Fact,N)-> N*Fact(Fact,N-1) end.
Y = fun(F, N)-> (fun(X,M)-> F( X(X), M) end)( fun(X,M)-> F(X(X),M) end, N) end
Y(Fa, 10) --> (fun(X)-> Fa( X(X), 10) end)( fun(X)-> Fa(X(X), 10) end).
	  --> Fa( (fun(X)-> Fa((X),10) end)(fun(X)->Fa((X),10) end), 10)
          --> 10 * ((fun(X)-> Fa((X),10) end)(fun(X)->Fa((X),10) end)(9) 
			 
Fa = fun(1)-> fun(_)-> 1 end; (N)-> fun(Fact)-> N * Fact(N-1) end end.
Y = fun(N)-> fun(F)-> (fun(X)->(F(N))(X(X)) end)(fun(X)->(F(N))(X(X)) end) end end.

(Y(10))(Fa) --> ( fun(F)-> (fun(X)-> (F(10))(X(X)) end)(fun(X)-> (F(10))(X(X)) end) end )
            --> ( fun(X)-> (Fa(10))(X(X)) end)(fun(X)-> (Fa(10))(X(X)) end)

Fa = fun(Fact)-> fun(1)->1; (N)-> N * Fact(N-1) end end.
Y = fun(F)->fun(N)-> ((fun(X)-> fun(M)-> (F(X(X)))(M) end end)(fun(X)-> fun(M)-> (F(X(X)))(M) end end))(N) end end

OCamlだとちょっとずるだけどこう:

let fib f n = if n=1 then 1 else n * f(n-1);;
let rec y f x = f (y f) x;;
 |