若干手こずりました。
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と同じです。
mapcanの挙動を確認する
(defvar *list1* '(1 11 111))
(defvar *list2* '(2 22 222))
(defvar *list3* '(3 33 333))
(format t "~%~A" (mapcar (lambda (&rest lists)
(format t "~%*~A" lists))
*list1* *list2* *list3*))
;;; *(1 2 3)
;;; *(11 22 33)
;;; *(111 222 333)
;;; (NIL NIL NIL)
(format t "~%~A" (mapcan (lambda (&rest lists)
(format t "~%*~A" lists))
*list1* *list2* *list3*))
;;; *(1 2 3)
;;; *(11 22 33)
;;; *(111 222 333)
;;; NIL
mapcarとmapcanの比較です。高階関数の引数のリストは同じですが、最終的な戻り値が違います。
(append (append (append nil (list nil))
(list nil))
(list nil))
=> (NIL NIL NIL)
(cdr (nconc (nconc (nconc (list 'dummy) nil)
nil)
nil))
=> NIL
こういうことのようです。dummyのリストにnconcし、最後にCDRを取っています。この例ではdummyは必要ないですが、次の例では必要です。
(format t "~%~A" (mapcar #'+ *list1* *list2* *list3*))
;;; (6 66 666)
(format t "~%~A" (mapcan #'+ *list1* *list2* *list3*))
;;; 666
(append (append (append nil '(6))
'(66))
'(666))
=> (6 66 666)
(cdr (nconc (nconc (nconc (list 'dummy) 6)
66)
666))
=> 666
もっと良い解釈があるのかもしれません。
CARのリストを取り出してみる。
(defun aaa (lists acc)
(cond ((null lists) acc)
(t (aaa (cdr lists)
(append acc `(,(car (car lists))))))))
(defun mapcan-aaa (fn &rest lists)
(aaa lists nil))
(format t "~%~A" (mapcan-aaa nil *list1* *list2* *list3*))
;;; (1 2 3)
CDRのリストを取り出してみる。
(defun bbb (lists acc)
(cond ((null lists) acc)
(t (bbb (cdr lists)
(append acc `(,(cdr (car lists))))))))
(defun mapcan-bbb (fn &rest lists)
(bbb lists nil))
(format t "~%~A" (mapcan-bbb nil *list1* *list2* *list3*))
;;; ((11 111) (22 222) (33 333))
CARのリストとCDRのリストを取り出してみる。
(defun ccc (lists acc-car acc-cdr)
(cond ((null lists) `(,acc-car . ,acc-cdr))
(t (ccc (cdr lists)
(append acc-car `(,(car (car lists))))
(append acc-cdr `(,(cdr (car lists))))))))
(defun mapcan-ccc (fn &rest lists)
(ccc lists nil nil))
(format t "~%~A" (mapcan-ccc nil *list1* *list2* *list3*))
;;; ((1 2 3) (11 111) (22 222) (33 333))
CARのリストとCDRのリストを再帰的に取り出してみる
(defun ddd (lists acc-car acc-cdr)
(cond ((null lists) `(,acc-car . ,acc-cdr))
(t (ddd (cdr lists)
(append acc-car `(,(car (car lists))))
(append acc-cdr `(,(cdr (car lists))))))))
(defun %mapcan (fn lists acc)
(cond ((member nil lists) acc)
(t (let ((tmp (ddd lists nil nil)))
(%mapcan fn
(cdr tmp)
(append acc `(,(car tmp))))))))
(defun mapcan-ddd (fn &rest lists)
(%mapcan fn lists nil))
(format t "~%~A" (mapcan-ddd nil *list1* *list2* *list3*))
;;; ((1 2 3) (11 22 33) (111 222 333))
高階関数を適用する
(defun eee (lists acc-car acc-cdr)
(cond ((null lists) `(,acc-car . ,acc-cdr))
(t (eee (cdr lists)
(append acc-car `(,(car (car lists))))
(append acc-cdr `(,(cdr (car lists))))))))
(defun %mapcan (fn lists acc)
(cond ((member nil lists) acc)
(t (let ((tmp (eee lists nil nil)))
(%mapcan fn
(cdr tmp)
(append acc `(,(apply fn (car tmp)))))))))
(defun mapcan-eee (fn &rest lists)
(%mapcan fn lists nil))
(format t "~%~A" (mapcan-eee #'+ *list1* *list2* *list3*))
;;; (6 66 666)
これはmapcarと同じです。ここからmapcanに変更していきます。
appendをnconcに変えてみる
(defun fff (lists acc-car acc-cdr)
(cond ((null lists) `(,acc-car . ,acc-cdr))
(t (fff (cdr lists)
(append acc-car `(,(car (car lists))))
(append acc-cdr `(,(cdr (car lists))))))))
(defun %mapcan (fn lists acc)
(cond ((member nil lists) acc)
(t (let ((tmp (fff lists nil nil)))
(%mapcan fn
(cdr tmp)
(nconc acc `(,(apply fn (car tmp)))))))))
(defun mapcan-fff (fn &rest lists)
(%mapcan fn lists nil))
(format t "~%~A" (mapcan-fff #'+ *list1* *list2* *list3*))
;;; (6 66 666)
正しくは 666 が返ってほしい。これではだめです。。。
局所変数にnconcする
(defun ggg (lists acc-car acc-cdr)
(cond ((null lists) `(,acc-car . ,acc-cdr))
(t (ggg (cdr lists)
(append acc-car `(,(car (car lists))))
(append acc-cdr `(,(cdr (car lists))))))))
(defun mapcan-ggg (fn &rest lists)
(let ((result (list 'dummy)))
(labels ((%mapcan (fn lists)
(cond ((member nil lists) result)
(t (let ((tmp (ggg lists nil nil)))
(nconc result (apply fn (car tmp)))
(%mapcan fn (cdr tmp)))))))
(%mapcan fn lists)
(cdr result))))
(format t "~%~A" (mapcan-ggg #'+ *list1* *list2* *list3*))
;;; 666
(format t "~%~A" (mapcan-ggg (lambda (x)
`(,(1+ x)))
'(1 2 3)))
;;; (2 3 4)
正しく返りました！
hyperspecのExsampleでテストする
(mapcan #'(lambda (x y) (if (null x) nil (list x y)))
'(nil nil nil d e)
'(1 2 3 4 5 6)) => (D 4 E 5)
(mapcan #'(lambda (x) (and (numberp x) (list x)))
'(a 1 b c 3 4 d 5))
=> (1 3 4 5)
(format t "~%~A" (mapcan-ggg #'(lambda (x y)
(if (null x) nil (list x y)))
'(nil nil nil d e)
'(1 2 3 4 5 6)))
;;; (D 4 E 5)
(format t "~%~A" (mapcan-ggg #'(lambda (x)
(and (numberp x) (list x)))
'(a 1 b c 3 4 d 5)))
;;; (1 3 4 5)
正しく返りました！
整える
(defun my-mapcan (fn &rest lists)
(let ((result (list 'dummy)))
(labels ((%%mapcan (lists acc-car acc-cdr)
(cond ((null lists) `(,acc-car . ,acc-cdr))
(t (%%mapcan (cdr lists)
(append acc-car `(,(car (car lists))))
(append acc-cdr `(,(cdr (car lists))))))))
(%mapcan (fn lists)
(cond ((member nil lists) result)
(t (let ((tmp (%%mapcan lists nil nil)))
(nconc result (apply fn (car tmp)))
(%mapcan fn (cdr tmp)))))))
(%mapcan fn lists)
(cdr result))))
(format t "~%~A" (my-mapcan #'+ *list1* *list2* *list3*))
;;; 666
(format t "~%~A" (my-mapcan (lambda (x)
`(,(1+ x)))
'(1 2 3)))
;;; (2 3 4)
嵌りポイント
今回の嵌りポイントは
- nconc自体の挙動。引数にリスト以外を渡した場合の挙動を知りました。
- 局所変数がリストを束縛する場合の初期化方法。(list 'dummy)と初期化していますが、'(dummy)と初期化すると嵌ります。
最後までご覧いただきありがとうございました。