mapconを実装してみた #lisp

hyperspecを確認してみる

Syntax:
mapc function &rest lists+ => list-1
mapcar function &rest lists+ => result-list
mapcan function &rest lists+ => concatenated-results
mapl function &rest lists+ => list-1
maplist function &rest lists+ => result-list
mapcon function &rest lists+ => concatenated-results

Descriptionを抜粋します。

mapcanとmapconは、関数を適用した結果がlistではなくnconcを使ってリストにまとめられることを除けば、それぞれmapcarとmaplistと同じです。つまり

(mapcon f x1 ... xn)
== (apply #'nconc (maplist f x1 ... xn))

また、mapcanとmapcarの関係も同様です。

なるほどなるほど。。。ここに興味深い記述があります。

maplistの結果をnconcしてるんですね！今回は末尾再帰関数を作りたいのでそのような実装にはなりませんが、組み合わせの妙を感じます。

mapconの挙動を確認する

(defvar *list1* '(1 11 111))
(defvar *list2* '(2 22 222))
(defvar *list3* '(3 33 333))

(format t "~%~A" (mapcon (lambda (&rest lists)
                           (format t "~%*~A" lists))
                         *list1* *list2* *list3*))
;;; *((1 11 111) (2 22 222) (3 33 333))
;;; *((11 111) (22 222) (33 333))
;;; *((111) (222) (333))
;;; NIL

maplistの場合、(NIL NIL NIL)が返りますが、mapconでは NILが返ります。

CDRのリストを取り出してみる

(defun aaa (lists acc)
  (cond ((null lists) acc)
        (t (aaa (cdr lists)
                (append acc `(,(cdr (car lists))))))))

(defun mapcon-aaa (fn &rest lists)
  (aaa lists nil))

(format t "~%~A" (mapcon-aaa nil *list1* *list2* *list3*))
;;; ((11 111) (22 222) (33 333))

正しく取り出せました。

CDRのリストのリストを取り出してみる

(defun bbb (lists acc)
  (cond ((null lists) acc)
        (t (bbb (cdr lists)
                (append acc `(,(cdr (car lists))))))))

(defun %mapcon (fn lists acc)
  (cond ((member nil lists) acc)
        (t (let ((tmp (bbb lists nil)))
             (%mapcon fn
                      tmp
                      (append acc `(,lists)))))))

(defun mapcon-bbb (fn &rest lists)
  (%mapcon fn lists nil))

(format t "~%~A" (mapcon-bbb nil *list1* *list2* *list3*))
;;; (((1 11 111) (2 22 222) (3 33 333))
;;;  ((11 111) (22 222) (33 333))
;;;  ((111) (222) (333)))

%mapconの引数listsを取り出しました。

高階関数を適用する

(defun ccc (lists acc)
  (cond ((null lists) acc)
        (t (ccc (cdr lists)
                (append acc `(,(cdr (car lists))))))))

(defun %mapcon (fn lists acc)
  (cond ((member nil lists) acc)
        (t (let ((tmp (ccc lists nil)))
             (%mapcon fn
                      tmp
                      (append acc `(,(apply fn lists))))))))

(defun mapcon-ccc (fn &rest lists)
  (%mapcon fn lists nil))

(format t "~%~A" (mapcon-ccc (lambda (&rest lists)
                               (format t "~%*~A" lists))
                             *list1* *list2* *list3*))
;;; *((1 11 111) (2 22 222) (3 33 333))
;;; *((11 111) (22 222) (33 333))
;;; *((111) (222) (333))
;;; (NIL NIL NIL)

(NIL NIL NIL)が戻っていますので、これはmaplistです。こちらを元にmapconに変更します。

maplistをmapconに変更する

(defun ddd (lists acc)
  (cond ((null lists) acc)
        (t (ddd (cdr lists)
                (append acc `(,(cdr (car lists))))))))


(defun mapcon-ddd (fn &rest lists)
  (let ((result (list 'dummy)))
    (labels ((%mapcon (fn lists)
               (cond ((member nil lists) (cdr result))
                     (t (let ((tmp (ddd lists nil)))
                          (nconc result (apply fn lists))
                          (%mapcon fn tmp))))))
      (%mapcon fn lists))))

(format t "~%~A" (mapcon-ddd (lambda (&rest lists)
                               (format t "~%*~A" lists))
                             *list1* *list2* *list3*))
;;; *((1 11 111) (2 22 222) (3 33 333))
;;; *((11 111) (22 222) (33 333))
;;; *((111) (222) (333))
;;; NIL

局所変数resultに高階関数の実行結果をnconcしています。

hyperspecのExampleでテストする

(mapcon #'list '(1 2 3 4)) => ((1 2 3 4) (2 3 4) (3 4) (4))

(format t "~%~A" (mapcon-ddd #'list '(1 2 3 4)))
;;; ((1 2 3 4) (2 3 4) (3 4) (4))

同じ結果が返りました！

整える

(defun my-mapcon (fn &rest lists)
  (let ((result (list 'dummy)))
    (labels ((%%mapcon (lists acc)
               (cond ((null lists) acc)
                     (t (%%mapcon (cdr lists)
                             (append acc `(,(cdr (car lists))))))))
             (%mapcon (fn lists)
               (cond ((member nil lists) (cdr result))
                     (t (let ((tmp (%%mapcon lists nil)))
                          (nconc result (apply fn lists))
                          (%mapcon fn tmp))))))
      (%mapcon fn lists))))

(format t "~%~A" (my-mapcon (lambda (&rest lists)
                              (format t "~%*~A" lists))
                            *list1* *list2* *list3*))
;;; *((1 11 111) (2 22 222) (3 33 333))
;;; *((11 111) (22 222) (33 333))
;;; *((111) (222) (333))
;;; NIL

(format t "~%~A" (my-mapcon #'list '(1 2 3 4)))
;;; ((1 2 3 4) (2 3 4) (3 4) (4))

maplistとmapcanを合体させたようなプログラムになりました。

mapcar,maplist,mapc,mapl,mapcan,mapconと一通り末尾再帰関数のパターンで実装することができました。

funcall,applyをうまく利用すれば、もっとスッキリとしたプログラムになるような気がします。今後はその辺りを観察していきたいと考えております。

最後までご覧頂きまして、ありがとうございました。