最近、いかに代入や副作用を減らしてFizz Buzz問題を解くかとか遊んでた。
結論としては3項演算子を使うことは第一の条件として再帰とmapする方法があるのかなと。
今回検証した言語はJavaScript(js)、VB.Net(VB)、Python3、CommonLisp(CL)、Clojure、HSPの6言語(⇒R、C++、Dを追加し9言語)。
HSPは言語仕様的に不利の塊だけどどこまでできるのか知りたかった。
追記: R言語に無名再帰用の構文があると知り追加しました。
また、Pythonについて@shiracamusさんよりコメントに無名再帰の実装例を頂きました。
こちらについてはギミックが理解でき次第(理解力が足りていない…)記事に適用したいと思います。
追記2: C++とD言語を追加しました。
追記1のアプローチもぼんやり見えたのでHSPを除く動的型付け言語に限り実装しました(静的型付け言語はラムダの型が必要なため断念… 再帰関数の型はどのように表現するべきなのでしょうか?)。
C#も考えたけどVBを移植するだけになるので放置。
※動的型付け言語はjs、Python、CL、Clojure、Rのみ。
追記3: 何を思ったかBATを追加しました。
もちろん副作用を無くすなんてHSP以上に不可能なので再帰っぽい実装だけ試みました。
ちなみにmap実装はありません。
無名再帰・再帰
おそらく、自然に無名再帰が書くことができるのはJavaScriptとClojureのみ(Rも追加)。
その他は代入が必要だったり普通に再帰するしかない。
(※なんちゃらコンビネータについては一切使用しない。)
標準出力内で表現しきるというだけならさらにVBとCLが加わるかな。
特にClojureは言語レベルで無名再帰をサポートしているので非常に強かった。
(print "> ")(flush)
(println
(loop[i 1,x (Long/parseLong (read-line)),s ""]
(if(= i (inc x))
s
(recur (inc i) x (str s
(if(=(mod i 3)(mod i 5)0)
"Fizz Buzz"
(if(=(mod i 3)0)
"Fizz"
(if(=(mod i 5)0)
"Buzz"
i)))
"\n")))))
正に完璧。
jsは非推奨でない方法だとfunction式に名前を付けてやる方法が一般的。
"use strict";
const rl=require("readline").createInterface(process.stdin,process.stdout);
const g=(function*(){
rl.setPrompt("> ");
rl.prompt();
console.log(
(function xfun(i,x,s){
return i===x+1 ?
s
: xfun(0|i+1,x,s+(
i%3===0 && i%5===0 ?
"Fizz Buzz"
: i%3===0 ?
"Fizz"
: i%5===0 ?
"Buzz"
:
i
)+"\n"
);
})(1,yield rl.once("line",v=>g.next(0|v)),"")
);
process.exit();
})();
g.next();
js特有の言語仕様はこういうところが強い。
ところでfunctionの書き方が似ているLuaとかじゃ同じことは出来ないのだろうか。
ちなみに非推奨とされる方法も。
//"use strict";
const rl=require("readline").createInterface(process.stdin,process.stdout);
const g=(function*(){
rl.setPrompt("> ");
rl.prompt();
console.log(
(function(i,x,s){
return i===x+1 ?
s
: arguments.callee(0|i+1,x,s+(
i%3===0 && i%5===0 ?
"Fizz Buzz"
: i%3===0 ?
"Fizz"
: i%5===0 ?
"Buzz"
:
i
)+"\n"
);
})(1,yield rl.once("line",v=>g.next(0|v)),"")
);
process.exit();
})();
g.next();
非推奨なので"use strict"の使用は禁止される。
ちなみにVBはリフレクションという方法を用いた無名再帰が使用できる。
Option Strict On
Imports System.Console
Imports System.Reflection.MethodBase
Public Module Program
Sub Main()
Write("> ")
WriteLine(
CType(
Function(i,x,s) _
If(i=x+1,
s,
CStr(GetCurrentMethod().Invoke(Nothing,{i+1,x,s &
If(i Mod 3=0 And i Mod 5=0,
"Fizz Buzz",
If(i Mod 3=0,
"Fizz",
If(i Mod 5=0,
"Buzz",
CStr(i)
))) _
& vbLf
}))
) _
,Func(Of Integer,Integer,String,String)
)(1,CInt(ReadLine),"")
)
End Sub
End Module
ただし、.Net4.5までに限る。.Net4.6や.Net Coreの環境で実行しようものなら非静的メソッドがなんちゃらとか言われ怒られてしまう。
現実的な範囲だとラムダ式の中にさらにラムダ式を入れてしまえば標準出力の中に全てまとめてしまうことができた。
Option Strict On
Imports System.Console
Module Program
Sub Main(args As String())
Write("> ")
WriteLine(
CType(Function(i0,x0,s0)
Dim xfun As Func(Of Integer,Integer,String,String)=Function(i,x,s) _
If(i=x+1,
s,
xfun(i+1,x,s &
If(i Mod 3=0 And i Mod 5=0,
"Fizz Buzz",
If(i Mod 3=0,
"Fizz",
If(i Mod 5=0,
"Buzz",
CStr(i)
))) & vbLf
)
)
Return xfun(i0,x0,s0)
End Function,
Func(Of Integer,Integer,String,String)
)(1,CInt(ReadLine),"")
)
End Sub
End Module
少し見苦しいけど、jsとやっていることは大体同じ風味となる。
同じようなアプローチであればCLでも同様に実装できた。
(princ "> ")(finish-output)
(format t "~A~%"
((lambda(i x s)
(labels((xfun(i x s)
(if(= i (1+ x))
s
(xfun (1+ i) x (concatenate 'string s
(if(=(mod i 3)(mod i 5)0)
"Fizz Buzz"
(if(=(mod i 3)0)
"Fizz"
(if(=(mod i 5)0)
"Buzz"
(write-to-string i))))
(format nil "~%"))))))
(xfun i x s))
) 1 (parse-integer(read-line)) ""))
labels関数と似た構文にfletという構文もあるけどこれは定義時点で自分が存在しない判定となっているらしく再帰を行うことは出来なかった。
これは通常のletにラムダ式を詰め込もうとしても同様だった。
次にPython。
xfun=lambda i,x,s: s \
if i==x+1 else \
xfun(i+1,x,s+(
"Fizz Buzz"
if i%3==0 and i%5==0 else
"Fizz"
if i%3==0 else
"Buzz"
if i%5==0 else
str(i)
)+"\n"
)
print(xfun(1,int(input("> ")),""))
Pythonはラムダ式の貧弱さゆえに同様な書き方は不可能。
変なことやってい無いからというのもあるけど、見た目の軽さは凄い。
ちなみにPythonの3項演算子は構文に癖があるので理解には結構苦労した記憶。
(コメントにPythonの無名再帰による実装例を頂きました)
最後はHSP。
#cmpopt varinit 1
#packopt name "H2"
#runtime "hsp3cl"
#uselib "msvcrt"
#func printf "printf" str
printf("> ")
#module Program
#defcfunc xfun int i,int x,str s
if i=x+1 :return s
#define fbx(%1,%2) \
if %2\3=0 & %2\5=0 :\
%1="Fizz Buzz" :\
else:if %2\3=0 :\
%1="Fizz" :\
else:if %2\5=0 :\
%1="Buzz" :\
else :\
%1=%2
fbx fb,i
return xfun(i+1,x,s+fb+"\n")
#global
sdim rl
input rl,,1
mes xfun(1,int(rl),"")
3項演算子もラムダ式も無いしどうあがいても不可能。
標準入力すら参照渡しだしね…
無駄にdefineしてる。
※追記:
R言語版。
cat("> ")
cat(
(function(i,x,s){
ifelse(i==x+1,
s,
Recall(i+1,x,paste(s,
ifelse(i%%3==0 && i%%5==0,
"Fizz Buzz",
ifelse(i%%3==0,
"Fizz",
ifelse(i%%5==0,
"Buzz",
i
)))
,"\n",sep=""))
)
})(1,as.integer(readLines(file("stdin"), n = 1L)),"")
,"\n")
Recall関数による完全なる無名再帰。
言語レベルで実装しているのはやはり珍しい。
※追記2:
VBと同様のアプローチでC++とDを実装。
まずはC++。
#include <iostream>
#include <string>
#include <functional>
using namespace std;
int main(){
cout<<"> "<<flush;
cout<<
[](int i,int x,string s){
function<string(int,int,string)> xfun=[&](int i,int x,string s){
return i==x+1 ?
s
: xfun(i+1,x,s+(
i%3==0 && i%5==0 ?
"Fizz Buzz"
: i%3==0 ?
"Fizz"
: i%5==0 ?
"Buzz"
:
to_string(i)
)+"\n"
);
};
return xfun(i,x,s);
}(1,[](int rl=0){cin>>rl;return rl;}(),string())
<<endl;
return 0;
}
次はD。
import std.stdio;
import std.string;
import std.conv;
void main(){
write("> ");
stdout.flush();
writeln(
(delegate(i,x,s){
string delegate(int,int,string) xfun;
xfun=(i,x,s)=>
i==x+1 ?
s
: xfun(i+1,x,s~(
i%3==0 && i%5==0 ?
"Fizz Buzz"
: i%3==0 ?
"Fizz"
: i%5==0 ?
"Buzz"
:
to!string(i)
)~"\n"
);
return xfun(i,x,s);
})(1,to!int(chomp(readln())),"")
);
}
名前を付けても単体ラムダ式での再帰は出来なかったので小細工。まさか、C++以上に苦労することになろうとは。
※追記3:
BAT言語。
どうあがいてもどうにもならないので再帰だけ何とかしようかと試みました。
@echo off
setlocal enabledelayedexpansion
goto main
:xfun
set/a fz=%1%%3, bz=%1%%5
if %2 lss %1 (
set xfunReturn=!s!
exit/b
) else (
if "%fz%:%bz%"=="0:0" (
set s=!s!Fizz Buzz
) else if %fz% equ 0 (
set s=!s!Fizz
) else if %bz% equ 0 (
set s=!s!Buzz
) else (
set s=!s!%1
)
set s=!s!^
)
set/a i=%1+1
call :xfun %i% %2
exit/b
:main
set/p x="> "
call :xfun 1 %x%
echo !xfunReturn!
遅延環境変数の罠。
正直再帰でも何でもないです。
関数に返り値も無ければ、遅延環境変数を引数として受け渡しすることもできない。
結局、ただ変数sを書き変え続ける実装になりました。
無名再帰(変則)
次はコメントの@shiracamusさん案による無名再帰実装。
実装内容についてはコメント欄参照のこと。
JavaScript
"use strict";
const rl=require("readline").createInterface(process.stdin,process.stdout);
const g=(function*(rl){
rl.setPrompt("> ");
rl.prompt();
console.log(
(
(xfun,i,x,s)=>xfun(xfun,i,x,s)
)(
(xfun,i,x,s)=>
i===x+1 ?
s
: xfun(xfun,0|i+1,x,s+(
i%3===0 && i%5===0 ?
"Fizz Buzz"
: i%3===0 ?
"Fizz"
: i%5===0 ?
"Buzz"
:
i
)+"\n"
),
1,yield rl.once("line",v=>g.next(0|v)),""
)
);
process.exit();
})();
g.next();
Python
print(
(
lambda xfun,i,x,s:xfun(xfun,i,x,s)
)(
lambda xfun,i,x,s: s \
if i==x+1 else \
xfun(xfun,i+1,x,s+(
"Fizz Buzz"
if i%3==0 and i%5==0 else
"Fizz"
if i%3==0 else
"Buzz"
if i%5==0 else
str(i)
)+"\n"
),
1,int(input("> ")),""
)
)
CommonLisp
(princ "> ")(finish-output)
(format t "~A~%"
(funcall
(lambda(xfun i x s) (funcall xfun xfun i x s))
(lambda(xfun i x s)
(if(= i (1+ x))
s
(funcall xfun xfun (1+ i) x (concatenate 'string s
(if(=(mod i 3)(mod i 5)0)
"Fizz Buzz"
(if(=(mod i 3)0)
"Fizz"
(if(=(mod i 5)0)
"Buzz"
(write-to-string i)
)))
(format nil "~%")
))
)
)
1 (parse-integer(read-line)) ""
)
)
Clojure
(print "> ")(flush)
(println
(
(fn[xfun i x s] (xfun xfun i x s))
(fn[xfun i x s]
(if(= i (inc x))
s
(xfun xfun (inc i) x (str s
(if(=(mod i 3)(mod i 5)0)
"Fizz Buzz"
(if(=(mod i 3)0)
"Fizz"
(if(=(mod i 5)0)
"Buzz"
i
)))
"\n"
))
)
)
1 (Long/parseLong (read-line)) ""
)
)
静的型付け言語は関数の型名が要求されるので再帰的な関数の型の表現に断念し、実装が上手くいかなかった。何か良い案はないだろうか…
map関数
HSP以外の全ての言語で自然な実装が可能だった。
どれも順当すぎる位順当なのでさらっと。
まずはjs。
"use strict";
const rl=require("readline").createInterface(process.stdin,process.stdout);
const g=(function*(){
rl.setPrompt("> ");
rl.prompt();
console.log(
[...Array(yield rl.once("line",v=>g.next(0|v))).keys()]
.map(i=>0|i+1).map(i=>(
i%3===0 && i%5===0 ?
"Fizz Buzz"
: i%3===0 ?
"Fizz"
: i%5===0 ?
"Buzz"
:
i
)
)
.join("\n")
);
process.exit();
})();
g.next();
標準でrange関数が実装されていないのでそこだけ気になる感じ。
mapにmapを重ねてる。
次はVB。
Option Strict On
Imports System.Collections.Generic
Imports System.Console
Module Program
Sub Main(args As String())
Write("> ")
WriteLine(
String.Join(vbLf,
Enumerable.Range(1,CInt(ReadLine)) _
.Select(
Function(i) _
If(i Mod 3=0 And i Mod 5=0,
"Fizz Buzz",
If(i Mod 3=0,
"Fizz",
If(i Mod 5=0,
"Buzz",
CStr(i)
)))
)
)
)
End Sub
End Module
Rangeの書きにくさ。
Enumerableという単語は覚えにくいので毎回ググったりする。
次はPython
print("> ",end="")
print(
"\n".join(
map(
lambda i: \
"Fizz Buzz"
if i%3==0 and i%5==0 else
"Fizz"
if i%3==0 else
"Buzz"
if i%5==0 else
str(i)
,range(1,int(input())+1)
)
)
)
言うことなしなシンプルさ。
PythonはJoinのデリミタの位置だけいつも戸惑う。
次はCL。
(princ "> ")(finish-output)
(format t "~{~A~^~%~}~%"
(mapcar
#'(lambda(i)
(if(=(mod i 3)(mod i 5)0)
"Fizz Buzz"
(if(=(mod i 3)0)
"Fizz"
(if(=(mod i 5)0)
"Buzz"
i))))
(loop for i from 1 to (parse-integer(read-line)) collect i)))
range関数はないのでloop for分で実装。
覚えにくい部分はあるけどformat文の優秀さは凄いと思う(何故か改行コードは~%)。
SBCLだと改行無しで標準出力されないのでそれだけ注意。
次はClojure。
(use '[clojure.string :only (join)])
(print "> ")(flush)
(println
(join
"\n"
(map
(fn[i]
(if(=(mod i 3)(mod i 5)0)
"Fizz Buzz"
(if(=(mod i 3)0)
"Fizz"
(if(=(mod i 5)0)
"Buzz"
i))))
(range 1 (dec(Long/parseLong (read-line)))))))
CLと大体一緒。
range関数は標準で実装されている。
そういえば、Clojureのformat関数はあまり使ったことないなぁ…
最後はHSP
#cmpopt varinit 1
#packopt name "H2"
#runtime "hsp3cl"
#uselib "msvcrt"
#func printf "printf" str
printf("> ")
sdim rl
input rl,,1
sdim fb,,int(rl)
foreach fb: fb(cnt)=str(cnt+1): loop
#module Program
#defcfunc fbx int i
#define returnFb \
if i\3=0 & i\5=0 :\
return "Fizz Buzz" :\
else:if i\3=0 :\
return "Fizz" :\
else:if i\5=0 :\
return "Buzz" :\
else :\
return str(i)
returnFb
#global
foreach fb: fb(cnt)=fbx(int(fb(cnt))): loop
sdim fbj
foreach fb: fbj+=fb(cnt)+"\n": loop
mes fbj
再代入の嵐。mapすべきところは全部foreachに置き換わるし当然。
あまりに見にくいので見にくい所だけ関数やマクロに閉じ込めてみる。
#cmpopt varinit 1
#packopt name "H2"
#runtime "hsp3cl"
#uselib "msvcrt"
#func printf "printf" str
printf("> ")
#module Program
#defcfunc readline
sdim rl
input rl,,1
return rl
#deffunc local range int min,int max,array arr
foreach arr: arr(cnt)=str(min+cnt): loop
return
#define global range(%1=0,%2,%3) %trange \
%i=int(%2) :\
%i=int(%1) :\
sdim %3,,%p1-%p0 :\
range@Program %o,%o,%3
#define global map(%1,%2) \
foreach %1 :\
%1(cnt)=%2(%1(cnt)) :\
loop
#define global join(%1,%2,%3) \
sdim %3 :\
foreach %1 :\
if cnt!=0{%3+=%2} :\
%3+=%1(cnt) :\
loop
#defcfunc local fbx int i
#define returnFb \
if i\3=0 & i\5=0 :\
return "Fizz Buzz" :\
else:if i\3=0 :\
return "Fizz" :\
else:if i\5=0 :\
return "Buzz" :\
else :\
return str(i)
returnFb
#define global ctype fbx(%1) fbx@Program(int(%1))
#global
range 1,int(readline())+1,fb
map fb,fbx
join fb,"\n",fbj
mes fbj
メインルーチンは大分すっきりしたけど、再代入まみれなのはどうしようもなし。
せめて配列リターンできればなぁ…といったところ。
言語機能が貧弱な分、自由度高めのdefineで怪しい動きさせるのは結構楽しい。
締めの言葉があるわけでもないので以上。
※追記:
R言語版。
cat("> ")
cat(
(function(i,arr,s){
ifelse(i>length(arr),
s,
Recall(i+1,arr,paste(s,arr[i],sep=(ifelse(i!=0,"\n",""))))
)
})
(0,Map(function(i){
ifelse(i%%3==0 && i%%5==0,
"Fizz Buzz",
ifelse(i%%3==0,
"Fizz",
ifelse(i%%5==0,
"Buzz",
i
)))
},1:as.integer(readLines(file("stdin"), n = 1L))),"")
,"\n")
無名再帰はあるけどString.Join的な関数はない様子。
せっかくだし、無名再帰でJoinっぽいことをやってみた。
※追記2:
C++とD言語追加。
Dは順当な結果となった。
import std.stdio;
import std.string;
import std.conv;
import std.range;
import std.algorithm;
void main(){
write("> ");
stdout.flush();
writeln(
iota(1,to!int(chomp(readln()))+1)
.map!(i=>
i%3==0 && i%5==0 ?
"Fizz Buzz"
: i%3==0 ?
"Fizz"
: i%5==0 ?
"Buzz"
:
to!string(i)
).join("\n")
);
}
C++。
#include <iostream>
#include <string>
#include <vector>
#include <numeric> //iota
#include <algorithm> //transform
#include <sstream> //ostringstream
#include <iterator> //ostream_iterator
using namespace std;
int main(){
cout<<"> "<<flush;
cout<<[](){
return [](vector<string> vcts,const char* deli,auto os){
copy(vcts.begin(),vcts.end(),ostream_iterator<string>(os,deli));
return [](string s,auto deli){
return s.substr(0,s.size()-strlen(deli));
}(os.str(),deli);
}(
[](vector<int> vcti){
return [](vector<int> vcti,vector<string> vcts){
transform(vcti.begin(),vcti.end(),vcts.begin(),
[](int i){
return i%3==0 && i%5==0 ?
"Fizz Buzz"
: i%3==0 ?
"Fizz"
: i%5==0 ?
"Buzz"
:
to_string(i);
}
);
return vcts;
}(vcti,vector<string>(vcti.size()));
}(
[](vector<int> vcti){
iota(vcti.begin(),vcti.end(),1);
return vcti;
}(vector<int>([](int rl=0){cin>>rl;return rl;}()))
),
"\n",ostringstream()
);
}()<<endl;
return 0;
}
C++はrange、map、joinといった主要関数が不足しているため茨の道だった。
iota、transform、copyとと代替となる関数は一応あるものの全て破壊型という悪夢。
ラムダで包みまくって副作用が無い様に見せかけようとしたけど、結局副作用起こしてる。
可読性も最悪の部類だし凄まじい。
C++その2。
#include <iostream>
#include <string>
#include <vector>
#include <functional>
using namespace std;
int main(){
cout<<"> "<<flush;
cout<<[](){
function<vector<int>(vector<int>,int,int)> range=
[&](auto vcti,int i,int max){
return i==max ?
vcti
: range([&i](auto vcti){
vcti.push_back(i);
return vcti;
}(vcti),i+1,max);
};
function<vector<string>(function<string(int)>,vector<int>,int,vector<string>)> map=
[&](auto xfun,auto vcti,int len,auto vcts){
return len==0 ?
vcts
: map(xfun,vcti,len-1,
[&xfun](int v,auto vcts){
vcts.push_back(xfun(v));
return vcts;
}(vcti[vcti.size()-len],vcts)
);
};
function<string(vector<string>,int,string)> join=
[&](auto vcts,int len,string s){
return len==0 ?
s
: join(vcts,len-1,
[](string v,string s){
return s+"\n"+v;
}(vcts[vcts.size()-len],s)
);
};
return [&](auto vcts){
return join(vcts,vcts.size(),string());
}(
[&](auto vcti){
return map(
[](int i){
return i%3==0 && i%5==0 ?
"Fizz Buzz"
: i%3==0 ?
"Fizz"
: i%5==0 ?
"Buzz"
:
to_string(i);
},
vcti,vcti.size(),vector<string>()
);
}(range(vector<int>(),1,[](int rl=0){cin>>rl;return rl+1;}()))
);
}()<<endl;
return 0;
}
もっと凄まじい可動性の何か。
iota、transform、copyを封印し、全て再帰ラムダに置き換えた。push_backしているので副作用が発生するというのは結局変化無し。