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

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はfoldとfoldrという二種類の関数を用意する道を選びました。

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でAPPENDをREDUCEを使って実装するなら、以下のようになるでしょう。

(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*のテイクは充分に短く把握が容易です。
本記事が参考になったなら幸い！