なぜfor文は禁止なのか?関数型記述のススメ (Emacs Lisp 遅延評価版)

はじめに (stream.el 紹介)

なぜfor文は禁止なのか?関数型記述のススメ
https://qiita.com/ukiuni@github/items/abad07524856c65a20ea

上記サイトのEmacs Lisp遅延評価版を掲載して、使われている遅延評価ライブラリのstream.elの使い方を解説します。
なぜ関数プログラミングは重要かによると、関数プログラミング(Functional Programming)にとっては、高階関数と遅延評価が重要である旨が書かれています。

上記サイト(なぜfor〜)では、最終的に高階関数は使われていますが遅延評価は使われていません。
それによる弊害として1〜100までの数列を最初に全部作成してしまっています。
この場合は言うまでもなく、個数が多ければ多いほど最初に膨大なメモリを消費しかねません。
遅延評価を使えば、それを回避することが出来ます。

最終的にEmacs Lisp遅延評価版は以下になります。
使ってる遅延評価ライブラリはstream.elですがEmacs自体にバグがある為100をあまり大きい値にするとEmacsごと落ちます…。
このバグは致命的過ぎてせっかくの遅延評価ライブラリが台無しですが、現実的な範囲では多分大丈夫でしょう…。

;; Emacs Lisp 遅延評価版 (25.1 以上)

(require 'cl-lib)
(require 'stream) ;; (package-install 'stream)

(seq-reduce #'+ (seq-filter #'cl-evenp (stream-range 1 100)) 0) ;; => 2450

stream.el 入門

このライブラリはEmacsには標準で含まれていませんがELPAにあるので、

(package-install 'stream)

でインストール出来ます。使うときは (require 'stream) します。
このライブラリは既にEmacsに含まれているseq.elを遅延リストを扱えるように拡張したものです。
なので、コードにはseq-*stream-*が混在することになりますが、そういう理由からだと思ってください。

さて、一番単純な例として

(stream-range)

これを*scratch*等で評価すると、何か変な値が表示されたと思いますが、これが整数の無限リスト(オブジェクト)を表しています。
概念的には(0 1 2 3 4 5 6 7 ...無限に続く)となります。

無限だと不便なので最初の10個を取得してみます。

(seq-take (stream-range) 10)

これでもまだ無限リスト(オブジェクト)の状態なので、通常のリストに変換します。

(seq-into (seq-take (stream-range) 10) 'list) ;; => (0 1 2 3 4 5 6 7 8 9)

これでようやく見て分かる状態になりました。最終的にはリストやベクターに変換するはずなので、この形が基本になります。
重要:決して(seq-into (stream-range) 'list)とやらないでください!Emacsごと落ちます!

次に「整数を0から合計して行って10000以上の最小値を表示する」というタスクを実装してみます。
整数の合計なので、最初に提示したようにstream-rangeseq-reduceを組み合わせれば良いように思いますが、
seq.elにある豊富なオペレーターを使用して以下のようにしてみても、終了しません…Emacsが落ちます。

(seq-find (lambda (n) (>= n 10000)) (seq-reduce #'+ (stream-range) 0))

これはseq-reduceの実装を見れば理解できますがseq-reduceは途中で止める事が出来ません。
(最初の提示では(stream-range 1 100)と有限の範囲でした)

なので、新たにオペレーターを実装する必要があります。seq-reduceを参考にseq-reduce-whileを実装します。

(cl-defgeneric seq-reduce-while (pred function sequence initial-value)
  (if (seq-empty-p sequence)
      initial-value
    (let ((acc initial-value))
      (catch 'seq--break
        (seq-doseq (elt sequence)
          (setq acc (funcall function acc elt))
          (unless (funcall pred acc)
            (throw 'seq--break nil))))
      acc)))

これを使って

(seq-reduce-while (lambda (n) (< n 10000))
                  #'+
                  (stream-range) 0) ;; => 10011

と実装する事が出来ました。

最後にフィボナッチ数列の最初の20個を表示する遅延評価版を作成します。

(defun lazy-fib ()
  (cl-labels ((rec (a b)
                   (stream-cons (+ a b)
                                (rec (+ a b) a))))
    (stream-cons 0 (stream-cons 1 (rec 1 0)))))

(seq-into (seq-take (lazy-fib) 20) 'list) ;; => (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

特徴としては終了判定が必要無くて、無限にコンスセルが繋って見えるところです。
もちろん実際は無限にコンスセルが作られてる訳ではなく、再帰呼び出しにすらなってないのです。

どうでしょうか?最終的なコードはfor文を使わずに、非常に綺麗なコードになってると思います。
望むオペレーターが無い場合は、一段階下りてオペレーター自身を実装する必要が出てきますが、
出来たものは再利用出来るもので、関数プログラミングのモジュラー性というものを表してると思います。

参考

stream.el 作者による解説

遅延リストの実装を知りたい場合は↓ここ (正しstream.elとはeven stream,odd streamの違いがある)
遅延リスト遊び - Emacsで学ぶLazyな世界(前編) - Code Aquarium

Scheme だけど参考になる
R7RSのdelay-forceとは何か

関数プログラミングする場合は必読
なぜ関数プログラミングは重要か

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.