読者です 読者をやめる 読者になる 読者になる

Common Lispで遅延評価を作って遊ぶ(3-1) - (数)列で遊ぶ、その1

今回の目的

ここまでに作ったcl-lazyライブラリを使って、こまけーことはいいんだよ、の精神で色々な(数)列を作って遊んでみたいと思います。気ままに遊んでいたら思いの外に長くなったので適当に2回に分けようと思います。

なお、以下では冗長なのでREPLによる評価値の出力は実行例から省略します。

前置き:数列の作り方

; 今は亡きマクロ版(前回書いたもの)
CL-USER> (make-series (0 1) (+ (lnth (- .n 1) .a)
                               (lnth (- .n 2) .a))))

前回は数学的なフィボナッチ数列の定義方法を目標に、数列作成用のマクロmake-seriesを作成しました。上にフィボナッチ数列の定義例を示します。(0 1)が初期値で、+で始まる式はそれ以降の項の定義です。.nは自身のインデックス、.aは数列自身を指しています。

; 関数版
CL-USER> (make-series '(0 1) (lambda (a n) (+ (lnth (- n 1) a)
                                              (lnth (- n 2) a))))

; 関数版にリードマクロを被せてみた版(次々回記事を書く予定)
CL-USER> #<a[n] = 0, 1, (+ a[n-1] a[n-2])>

前回も書いたように、結局マクロ版は捨てて関数版にリードマクロを被せた版を採用することにしました。まず関数版をマクロ版と比較すると、初期値がリストになっている*1こと、aとnをアナフォリックにではなくlambdaの中で明示的に命名している点が異なります。そして一番下がリードマクロを被せた版です。一気に短くなりました。ここまで来ると遅延評価の色もなくなり、特に解説がなくとも使い方が伝わる…ものになったと主張したいのですがどうでしょうか。若干装飾はつきますが、展開すると上の関数版と同等のものができあがります。今回はこのリードマクロ版を使って遊びたいと思います*2

このライブラリを使うための準備(誰も使わない)。まず以下からcl-lazyをquicklispから見える場所にcloneします。

eshamster/cl-lazy · GitHub

あとは以下のようにすると今回書いたものが動くはずです(今後非互換な変更が入らなければ)。

CL-USER> (ql:quickload :cl-lazy)
; cl-lazyのパッケージ指定を省略可能にする
CL-USER> (use-package :cl-lazy)
; 上記のリードマクロを有効化する
CL-USER> (enable-series-processing-syntax)

基本編

等差数列

初項3,公差2な等差数列。計算速度的には一つ目の書き方が良いですが、別解のほうが意味ははっきりします。なお、#{x[i]}(または#{x i}と書いても可)は(lnth i x)に展開されます。参照部分でも遅延評価の色をなくしてみました。

CL-USER> (defparameter x #<a[n] = (+ 3 (* n 2))>)
CL-USER> (dotimes (i 20) (format t "~D " #{x[i]}))
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
; 別解
CL-USER> (defparameter x #<a[n] = 3, (+ a[n-1] 2)>)

等比数列

初項3,公比2な等比数列

CL-USER> (defparameter x #<a[n] = 3, (* a[n-1] 2)>)
CL-USER> (dotimes (i 15) (format t "~D " #{x[i]}))
3 6 12 24 48 96 192 384 768 1536 3072 6144 12288 24576 49152

無限長固定乱数列

遅延評価の特性を活かして、一度取り出すと値が固定される乱数列を作ってみます。同じ位置の値は何度取り出しても同じ値になります。何かに使えそう。ちなみに、このライブラリ結構遊べそう、と思ったのはこれを思いついた時でした。

CL-USER> (defparameter x #<a[n] = (random 1.0)>)
CL-USER> (dotimes (i 10) (format t "~5,3F " #{x[i]}))
0.719 0.780 0.040 0.534 0.584 0.542 0.705 0.506 0.261 0.635
CL-USER> (dotimes (i 10) (format t "~5,3F " #{x[i]}))
0.719 0.780 0.040 0.534 0.584 0.542 0.705 0.506 0.261 0.635

数列から数列を作る

目的の数列を直接作ることが難しい場合でも、別の数列を基にすると簡単に作れるというケースがあるかと思います。そのためのユーティリティを2つほど書いてみました。

普通に既存の数列を参照する

特にユーティリティを用意しなくとも、上記のリードマクロを直接使うことで容易に新しい数列を生成できる場合もあります。例えば階差数列はその例で、試しにフィボナッチ数列を階差に持つ初項0の数列fibdif*3を作ってみます。

CL-USER> (defparameter fib #<a[n] = 0, 1, (+ a[n-1] a[n-2])>)
CL-USER> (defparameter fibdif #<a[n] = 0, (+ a[n-1] fib[n-1])>)
CL-USER> (dotimes (i 20) (format t "~D " #{fibdif[i]}))
0 0 1 2 4 7 12 20 33 54 88 143 232 376 609 986 1596 2583 4180 6764

数列の合成

listの世界では各要素に処理をして同要素数の新たなlistを作成するmapcar関数があります。数列でも似たようなものがあると何かに使えそうです。ということで、一つの数列を処理するmap-series関数…ではなく、これを拡張して一つ以上の数列を受け取って新しい一つの数列を作成するconcat-seriesマクロを作成しました。今回扱う数列はすべて「長さ」が同じ(無限長)であるため、自然な拡張になると考えます。

余り面白そうな例も思いつかなかったので手抜きで3つの数列の各要素をリストとしてくっつけた列を作ってみます。「数」列以外の列も問題なく作れることを示す例ということで。ついでに、リーダマクロの仕様として'a'と'n'の組み合わせである必要は特にないので別の記号も使ってみました*4

CL-USER> (defparameter a1 #<a[n] = (* n 1)>)
CL-USER> (defparameter a2 #<b[k] = (* k 2)>)
CL-USER> (defparameter a3 #<c[l] = (* l 3)>)
CL-USER> (defparameter a123 (concat-series #'list a1 a2 a3))
CL-USER> (dotimes (i 8) (format t "~A " #{a123[i]}))
(0 0 0) (1 2 3) (2 4 6) (3 6 9) (4 8 12) (5 10 15) (6 12 18) (7 14 21)

数列の抽出

ある数列から条件に合致した値だけを取り出して新たな数列を作る、ということができるともう少し遊べそうです(次回はこれを使って少し遊んでみます)。これを実現するためにfilter-series関数を作りました。正確には、以下のfilter-series-using-little関数を呼び出して、funcall fn-findにtargetだけを渡すようにしたものです。実装のポイントとして、受け取った数列seriesは前にたどるだけで後ろに戻ることがないことを利用して効率化を図っています。クロージャrest-seriesに基となる数列seriesを包み、(setf rest-series (lcdr rest-series))で更新していくことで、同じ値を二度見ないようにしています*5。また、無限ループしないようにgive-up-distanceだけ進んでも条件に合致する値が見つからない場合は以降nilを返し続けるようにしました。

(defun filter-series-using-little (fn-find series &key (give-up-distance 10000))
  (let ((rest-series series)
        (has-give-up nil))
    (make-series
     nil
     #'(lambda (a n)
         (block blk
           (if has-give-up (return-from blk nil))
           (loop for i from 0 to give-up-distance do
                (let ((target (lcar rest-series)))
                  (setf rest-series (lcdr rest-series))
                  (if (funcall fn-find target a n)
                      (return-from blk target))))
           (setf has-give-up t)
           nil)))))

使用例。余り意味がない例ですが、フィボナッチ数列から奇数のみを取り出した数列を作ってみます。ちなみに、7の倍数を取り出してみた(oddpを(lambda (val) (= (mod val 7) 0)に置き換える)ところ、20番目にはすでに32桁の自然数になっていました。

CL-USER> (defparameter fib #<a[n] = 0, 1, (+ a[n-1] a[n-2])>)
CL-USER> (defparameter fib-odd (filter-series #'oddp fib))
CL-USER> (dotimes (i 20) (format t "~D " #{fib-odd[i]}))
1 1 3 5 13 21 55 89 233 377 987 1597 4181 6765 17711 28657 75025 121393 317811 514229

数列の列

make-seriesで作れるのはなにも「数」列だけではないと上にも書きましたが、要素として数列をとることもできます。つまりは、n次元数列を作ることが可能ということです。ここでは二次元数列で遊んでみます。

ずれたフィボナッチ数列

二次元数列の1行目にフィボナッチ数列、2行目に1つ左にずらしたフィボナッチ数列、…、k+1行目にk個左にずらしたフィボナッチ数列を配置してみます。

まず、a[n]の初期値、すなわち一行目の数列としてフィボナッチ数列b[k]を作成します。2行目以降を表すc[l]では一つ上(n-1)の一つ右(l+1)の値を取り出せば良いということで、下のような定義になります。

CL-USER> (defparameter x #<a[n] =
                       #<b[k] = 0, 1, (+ b[k-1] b[k-2])>,
                       #<c[l] = a[n-1][l+1]>>)
CL-USER> (dotimes (i 10)
           (dotimes (j 10)
             (format t "~5D" #{x[i][j]}))
           (fresh-line))
    0    1    1    2    3    5    8   13   21   34
    1    1    2    3    5    8   13   21   34   55
    1    2    3    5    8   13   21   34   55   89
    2    3    5    8   13   21   34   55   89  144
    3    5    8   13   21   34   55   89  144  233
    5    8   13   21   34   55   89  144  233  377
    8   13   21   34   55   89  144  233  377  610
   13   21   34   55   89  144  233  377  610  987
   21   34   55   89  144  233  377  610  987 1597
   34   55   89  144  233  377  610  987 1597 2584

なお、縦方向に見てもずれたフィボナッチ数列になっていることに着目すると、下の別解1のような書き方もできます。一つずらしたフィボナッチ数列を初期値として2つ用意して、c[l]では自身の上2つの値を足しています。横方向と縦方向が対称に書ける点がきれいです。「ずれたフィボナッチ数列」という元々の意図は逆に見えにくくなりますが。また、フィボナッチ数列をいったん変数化した別解2も書けます。短くはなりましたが、実装である遅延評価が見えてしまう点(lcdr)は少々気になります。同様にlcdrを躊躇せずに使えば、別解3の書き方もできます。「ずれたフィボナッチ数列」という意図が一番はっきりしているかもしれません。

; 別解1
CL-USER> (defparameter x #<a[n] =
                       #<b[k] = 0, 1, (+ b[k-1] b[k-2])>,
                       #<b[k] = 1, 1, (+ b[k-1] b[k-2])>,
                       #<c[l] = (+ a[n-1][l] a[n-2][l])>>)

; 別解2
CL-USER> (defparameter fib #<a[n] = 0, 1, (+ a[n-1] a[n-2])>)
CL-USER> (defparameter x #<a[n] = fib, (lcdr fib), #<c[l] = (+ a[n-1][l] a[n-2][l])>>)

; 別解3
CL-USER> (defparameter fib #<a[n] = 0, 1, (+ a[n-1] a[n-2])>)
CL-USER> (defparameter x #<a[n] = fib, (lcdr a[n-1])>)

次回へ

もともとmake-seriesはフィボナッチ数列を簡単に定義できるようになって満足、で終わるはずだったのですが、実際に道具ができてみると色々遊んでみたくなりました。特にリードマクロができてからはしばらくいじり回していました。数学的素養のある人であればもっと遊べるのでしょうか…。

さて、数といえば素数ですねということで、次回は素数列を作ってみます。よくある素数の求め方の拡張版とともに、無限長数列があることで可能なもう少し面白い版も模索します。ついでに、できあがった素数列自体でも遊んでみます。

シリーズリンク

*1:このために生成時点で初期値リストが評価されてしまうという欠点があるのですが、初期値ぐらいはまあいいかと思うことにしました。

*2:見た目は悪く無いと思いますが、その実だいぶ手抜きなリードマクロです。例えば[]の内部はハイフンを含まない式1つか、四則演算1つでつないだ(ハイフンを含まない)2つの式しか入りません。

*3:なんとなくfizz-buzzみたいで語呂がいいですね

*4:さらに言うと一文字でなくても問題無いです。若干の落とし穴はありますが

*5:concat-seriesも同様の最適化が馴染むのですがサボってます…