各言語による無名再帰処理の実行例まとめ
先に作成した拙作記事『Rubyのアロー演算子を用いたラムダ計算の基礎表現』の最後に記載した,関数処理本体に自己適用パターンを埋め込んだ無名再帰処理について,他のプログラミング言語でも実行してみた結果をあらためて記事にしました.実用性の薄い技術記事ですが,関数型プログラミングに関する教養程度に捉えていただけますと幸いです.
この記事の無名再帰処理は,40番目のフィボナッチ数 を求める定義としています.再帰処理として定義通りに実装すると関数呼び出しが指数的に増加して膨大な時間がかかるため,末尾再帰による事実上の繰り返し処理に変更しています.この処理を無名関数化し,ラムダ式
各言語による実行例
記述が長くなることから,字句解析できる程度に空白等を詰めた記述を行っています.
Python
>>> (lambda g:g(g))(lambda g:lambda a,b,n:a if n==0 else g(g)(b,a+b,n-1))(0,1,40)
102334155
Ruby
>> ->g{g[g]}[->g{->(a,b,n){n==0?a:g[g][b,a+b,n-1]}}][0,1,40]
=> 102334155
JavaScript (Node.js)
> (g=>g(g))(g=>(a,b,n)=>n==0?a:g(g)(b,a+b,n-1))(0,1,40)
102334155
Julia
julia> (g->g(g))(g->(a,b,n)->n==0 ? a : g(g)(b,a+b,n-1))(0,1,40)
102334155
Scheme
> (((lambda(g)(g g))(lambda(g)(lambda(a b n)(if(= n 0)a((g g)b(+ a b)(- n 1))))))0 1 40)
102334155
Common Lisp (Emacs Lisp)
Emacs Lispでは(setq lexical-binding t)
でレキシカルスコープ対応にして実行.
(funcall(funcall(lambda(g)(funcall g g))(lambda(g)(lambda(a b n)(if(= n 0)a(funcall(funcall g g)b (+ a b) (- n 1))))))0 1 40)
102334155
R言語
> (function(g){g(g)})(function(g){function(a,b,n){if(n==0)a else g(g)(b,a+b,n-1)}})(0,1,40)
[1] 102334155
Lua
> (function(g)return g(g)end)(function(g)return function(a,b,n)return n==0 and a or g(g)(b,a+b,n-1)end end)(0,1,40)
102334155
Clojure
user=> ((#(% %)#(fn[a b n](if(= n 0)a((% %)b(+ a b)(- n 1)))))0 1 40)
102334155
おまけ:LINE Botにしてみた
Google Apps Script(JavaScript)+LINE Message APIでお手軽実装.整数は符号付き64ビットなので,78番目まで正確な値が返ってきます.
ソースコードは次の通り.メインはuserMessage
として受け取った受信メッセージを処理するif
文です.
var ACCESS_TOKEN = '(アクセストークン)';
var REPLY_URL = 'https://api.line.me/v2/bot/message/reply';
function doPost(e) {
var replyToken = JSON.parse(e.postData.contents).events[0].replyToken;
var userMessage = JSON.parse(e.postData.contents).events[0].message.text;
var headers = {
'Content-Type': 'application/json; charset=UTF-8',
'Authorization': 'Bearer ' + ACCESS_TOKEN
};
if (userMessage.toLowerCase() == 'help') {
rMes = '0以上の整数値xを送信するとx番目のフィボナッチ数を返信します.';
} else {
if (isNaN(x = Number(userMessage)) || x < 0)
rMes = '0以上の整数値を送信して下さい.';
else
rMes = String((g=>g(g))(g=>(a,b,n)=>n==0?a:g(g)(b,a+b,n-1))(0,1,x))
}
var payload = JSON.stringify({
'replyToken' : replyToken,
'messages': [{
'type' : 'text',
'text' : rMes
}]
})
var options = {
'headers' : headers,
'method' : 'post',
'payload' : payload
};
UrlFetchApp.fetch(REPLY_URL, options);
}
備考
記事に関する補足
- Pythonの例がなんとか80文字以内に収まった…!(lambda使いまくってる時点でPEP8的にアウトっぽいけど)
更新履歴
- 2020-12-09:Clojureの例を追加
- 2020-11-20:LINE Botの例を追加
- 2020-11-19:初版公開(Python,Ruby,JavaScript,Julia,Scheme,Common Lisp,R,Lua)
Author And Source
この問題について(各言語による無名再帰処理の実行例まとめ), 我々は、より多くの情報をここで見つけました https://zenn.dev/ytaki0801/articles/bba832f1d32738f2199e著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol