🦉

MY-APPEND or why reduce is not suitable for append.

4 min read 1

MY-APPEND or why reduce is not suitable for append.

Introduction

このようなツイートがありまして、このようにリツイートしたところまさかの返信がありまして。

話すと長くなるのでここにまとめます。

なお、僕はCommon Lispには明るいもののこちらのPureLISP_shについては暗いので以降の例は全てCommon Lispで書かれたものとなります。

REDUCE.

REDUCEという関数は二引数関数とリストをとり、畳み込み(reduce)を行う高階関数です。
以下のような振る舞いになります。

* (reduce #'+ '(1 2 3 4 5))
15

* (reduce #'max '(1 2 3 4 5))
5

* (reduce #'min '(1 2 3 4 5))
1

REDUCE*

元記事のREDUCEをCommon Lispで再実装すると以下になります。
CL:REDUCEと名前がぶつかるのでここでは末尾に*をつけて回避します。

(defun reduce* (function list initial-value)
  (cond
    ((eql list nil) initial-value)
    (t (funcall function
                (car list)
                (reduce* function (cdr list) initial-value)))))

Actualy it is foldr.

REDUCE*の一番の問題点は末尾再起になっておらず、いわゆるREDUCEと振る舞いが異なる点でしょうか。

* (trace reduce*)
(REDUCE*)

* (reduce* #'+ '(1 2 3 4 5) 0)
  0: (REDUCE* #<FUNCTION +> (1 2 3 4 5) 0)
    1: (REDUCE* #<FUNCTION +> (2 3 4 5) 0)
      2: (REDUCE* #<FUNCTION +> (3 4 5) 0)
        3: (REDUCE* #<FUNCTION +> (4 5) 0)
          4: (REDUCE* #<FUNCTION +> (5) 0)
            5: (REDUCE* #<FUNCTION +> NIL 0)
            5: REDUCE* returned 0
          4: REDUCE* returned 5
        3: REDUCE* returned 9
      2: REDUCE* returned 12
    1: REDUCE* returned 14
  0: REDUCE* returned 15
15

これはHaskellでいうfoldrの振る舞いです。
Haskellはfoldfoldrという二種類の関数を用意する道を選びました。

Common Lispは引数で制御する道を選びました。
Common LispのREDUCEはキーワード引数:FROM-ENDを受け付けます。
指定された場合Haskellでいうfoldrの振る舞いとなります。

;; いわゆるREDUCE。
* (reduce #'cons '(1 2 3) :initial-value nil)
(((nil . 1) . 2) . 3)

;; Haskellでいうfoldr。
* (reduce #'cons '(1 2 3) :initial-value nil :from-end t)
(1 2 3)

;; REDUCE*はfoldrの振る舞いをする。
* (reduce* #'cons '(1 2 3) nil)
(1 2 3)

APPEND by REDUCE.

Common LispでAPPENDREDUCEを使って実装するなら、以下のようになるでしょう。

(defun my-append (&rest lists)
  (reduce (lambda (list acc)
            (reduce (lambda (x y)
                      (cons x y))
                    list :initial-value acc :from-end t))
          lists
          :initial-value nil
          :from-end t))

APPEND without REDUCE.

Common Lispの界隈には、いにしえよりTCONCという技法が伝わっております。
効率の良いAPPENDの実装を考えるならTCONCを使ったものとなるでしょう。
これは要するに即席のqueueです。

(defun my-append2 (&rest lists)
  (do* ((acc (cons :dummy nil))
        (tail acc)
        (lists lists (cdr lists)))
    ((null lists) (cdr acc))
    (do ((list (car lists) (cdr list)))
      ((null list))
      (setf (cdr tail)
            (setf tail (list (car list)))))))

Bench.

まずは元ツイの全関数を実装。

(defun append2 (a b) (reduce* #'cons a b))

(defun append* (&rest lists)
  (reduce* #'append2 lists nil))

ベンチ。

* (time (append* '(1 2) '(3 4) '(5 6)))
Evaluation took:
  0.000 seconds of real time
  0.000003 seconds of total run time (0.000003 user, 0.000000 system)
  100.00% CPU
  5,356 processor cycles
  0 bytes consed

* (time (my-append '(1 2) '(3 4) '(5 6)))
Evaluation took:
  0.000 seconds of real time
  0.000003 seconds of total run time (0.000003 user, 0.000000 system)
  100.00% CPU
  7,048 processor cycles
  0 bytes consed

* (time (my-append2 '(1 2) '(3 4) '(5 6)))
Evaluation took:
  0.000 seconds of real time
  0.000002 seconds of total run time (0.000002 user, 0.000000 system)
  100.00% CPU
  2,368 processor cycles
  0 bytes consed

* (time (append '(1 2) '(3 4) '(5 6)))
Evaluation took:
  0.000 seconds of real time
  0.000004 seconds of total run time (0.000003 user, 0.000001 system)
  100.00% CPU
  2,636 processor cycles
  0 bytes consed

元ツイのAPPEND*CL:REDUCEで実装したものより早いですね。
これはCL:REDUCEが一つのインターフェイスに:FROM-ENDやら何やらあれこれつぎ込んだのがオーバーヘッドになっているからかと思われます。
とはいえTCONCのテイクは倍の速さとなります。
CL:APPENDの効率がTCONCのものと大差ないので、SBCLのAPPENDはおよそTCONCでの実装とみて良いのかもしれません。

Conclusion.

これ以上のベンチは取りようがないのでこれは憶測になってしまうのですが、REDUCEのテイクが遅いのは末尾再帰にならずスタック負荷が高いのと高階関数の宿命たる関数の動的呼び出しコストによるものではないかと思われます。

実装コストと実行コストはある程度あちらを立てればこちらが立たずという関係にあるかと思われます。
TCONCのテイクはお世辞にも読みやすいものではありません。
そのバランスを取るのは実装者の責任です。
REDUCE*のテイクは充分に短く把握が容易です。
本記事が参考になったなら幸い!

Discussion

元ツイートに関する充実した記事による解説ありがとうございました.すみません,Zenn への新規登録とかしてたら返信が遅くなりました.これを機に,Qiita記事のいくつかをZennに転載してみようかな….

reduceやappend実装についてはおっしゃる通りで,コンスセルに基づく関数型処理のみを想定すると,どうしても末尾再帰にならずスタック積みまくりという感じですね.当方はScheme(あるいはSICP)から本格的にLISPを始めた人間で,こちらの場合は,拡張仕様SRFI-1でいうfold-right(の,リスト引数がひとつのみの場合)相当でしょうか.左からのfoldであれば末尾再帰になるのですが.実用性を考えるなら,関数型を忘れて値書き換え(代入)やベクタ処理にしていくべきでしょうね.

ツイートの方でも言及しましたが,今回使用していた処理系は,LISP体験用に当方でシェルスクリプトとして簡易実装したもので,まあ,教育用ですね.元は評価器がjmc.lisp移植版だったのでプログラム記述はCommon Lispに似た感じですが,今はSICPの4.1章と同じ構成にすり替えているので,中身はScheme指向です.そういうこともあって,値書き換えや末尾再帰最適化どころか,数値すら扱えません(^^;).本格的にLISP活用するならGauche/Guile/SBCL/Emacsをというスタンスです.Common Lispの方がSBCL一択と化しているのがちょっと気になってますけど.GNU Emacsのcl-lib(Common Lisp Emulation)の実用性はどれくらいなんだろう….

ログインするとコメントできます