Erlangとxrange

fizzbuzz作るときはまず1～100までのリストを作るのがLisp流なんだ、と言われると(誰に言われたわけでもないですが、そういう記述を本で読んだ記憶が若干)、なんだかとても抵抗を覚えます。1～100までのリストを確保するための領域と問題解決の間に何の関係があるんでしょう、などとひねくれたことを考えてしまうからです。そこまでひねくれなくても、1～10000だったらどうなる、100億だったら？と、いろいろ考えてしまいます(すぐに「億」と言いだすところは小学生並)。先日も、lists:seqを使うのに抵抗があるなあと書いていますね。

Pythonにはxrangeというものがあって、それを使うと実際にリストを生成することなく数列を作りだすことができます。こちらを見ると、どうもPython3ではxrangeはrangeと統合されたようですが。

"erlang xrange" で検索してみたところ、MLのスレッドを発見しました。このスレッドで紹介されているstreams.erlがなかなか面白かったです。

サンプルにあるように、

> streams:first(10, streams:primes())

などとすると、素数の最初の10コを得ることができます。同じように、integers_starting_from/1 というやつは、引数で指定した整数から1ずつ加算した整数を無限に返す関数となっています。順を追って見てみましょう。

13> streams:integers_starting_from(2).
[2|#Fun<streams.2.60508764>]

最初の要素と、その次を返す関数のリストになっています。

14> F = streams:integers_starting_from(2).
[2|#Fun<streams.2.60508764>]
15> streams:head(F).
2
16> streams:tail(F).
[3|#Fun<streams.2.60508764>]

headすると先頭の要素を返し、tailすると「次の要素、次の次の要素を得る関数」を得ることができるので、これを繰り返し適用してゆくと、対象の関数は無限再帰のように書いておいて、呼出し側は必要な分だけ取得できるという寸法です。必要な分だけ取得するために、firstといった関数も用意されています。

17> streams:head(streams:tail(F)).
3
18> streams:head(streams:tail(streams:tail(F))).
4
19> streams:first(10, F).
[2,3,4,5,6,7,8,9,10,11]

無限再帰ぽく書くために、cons_streamというマクロを作ってそれを呼ぶようにしているようです。

さて、streams.erlにはmapやfilterも定義されていますので、実現方法を応用することでfor i in xrange(1,10):... くらいのことはできそうです。

foreach(_F, []) ->
    ok;
foreach(F, S) ->
    F(head(S)),
    foreach(F,tail(S)).
xrange(From, To, Step) when From + Step > To ->
    ?cons_stream(From, []);
xrange(From, To, Step) when From =< To ->
    ?cons_stream(From, xrange(From+Step, To, Step)).
xrange(From, To) ->
    xrange(From, To, 1).

なんてのを用意して...

17> streams:foreach(fun(X) -> io:format("~p * 2 = ~p~n", [X, X*2]) end, streams:xrange(1,20,3)).
1 * 2 = 2
4 * 2 = 8
7 * 2 = 14
10 * 2 = 20
13 * 2 = 26
16 * 2 = 32
19 * 2 = 38
ok

ふむふむ。ちゃんと動いているようです(Stepをマイナスにできない等いけてないところがありますが)。lists:seq/3と比べて著しく効率がよいとも思えないのですが、なかなか面白いです。

なお、やっぱりリストを得たいとなったら、もともと入っているstreams:all/1を使うことができます。

18> streams:all(streams:xrange(1,20,3)).
[1,4,7,10,13,16,19]