Hatena::Grouperlang

weekend erlang programmer

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

{2010, 3, 24}

Y combinator cont'd 23:28 はてなブックマーク - Y combinator cont'd - weekend erlang programmer Y combinator cont'd - weekend erlang programmer のブックマークコメント

頑張って書いて動いた!と思ったら、指摘をいただいて問題アリアリなことに気付いたので let rec y f x = f (y f) x;;を意識して書き直してみた。Erlangで高階関数書くのめんどい。funのタイプが速くなったけどfunctionは相変わらずうまくタイプできない。

-module(yc).
-compile(export_all).
y(F)-> fun(X)-> (F( y(F)))(X) end.
do(N)->
    F = fun(Fact)-> fun (1)-> 1; (X)-> X* Fact(X-1) end end,
    (y(F))(N).

あれ、よくみたらyの定義が冗長じゃん、とおもって

y(F)-> F( y(F)).

って書いたら動かなかった、じゃない停止しなかった。これだとdo/1の奥の方でX-1を評価していく前に y(F) が永遠に再帰してしまって終わらない(のでボツ)。

なので、元のコードでtype/specちゃんと書くとこんな風になる:

-module(yc).
-compile(export_all).

-spec f( Fact::fun( (integer())-> integer() ) )-> fun((integer())-> integer()).
f(Fact)-> fun (1)-> 1;(X)-> X*Fact(X-1) end.

-spec y( F::fun( (fun((TypeA)-> TypeB)) -> fun((TypeA)-> TypeB) ))-> fun((TypeA)->TypeB).
y(F)-> fun(X)-> (F( y(F)))(X) end.

-spec do(integer())-> integer().
do(N)-> (y(fun f/1))(N).

y(fun f/1)ってのがどうにもErlangっぽくてイケてないよなぁ。念には念を入れて型の確認のためtyperにかけてみたらちゃんとパスした。

> $ typer yc.erl                                              [kuenishi@shuna.local:~]

%% File: "yc.erl"
%% --------------
-spec f(Fact::fun((integer()) -> integer())) -> fun((integer()) -> integer()).
-spec y(F::fun((fun((TypeA) -> TypeB)) -> fun((TypeA) -> TypeB))) -> fun((TypeA) -> TypeB).
-spec do(integer()) -> integer().

おかしいところは一応ないみたい。しかしパターンマッチのほとんどない状況で関数型言語使ってると、ワンライナーで書きたくなってついつい一行が長くなるのは悪いクセだな。

 |