mapcanを実装してみた

- [mapcarを実装してみた - Qiita](https://qiita.com/inutomo0123/items/985bd62c8949206030f4)
- [maplistを実装してみた - Qiita](https://qiita.com/inutomo0123/items/6563bdd140ac13f09ec7)
- [mapcを実装してみた - Qiita](https://qiita.com/inutomo0123/items/aaaa815c3c3add5ad615)
- [maplを実装してみた - Qiita](https://qiita.com/inutomo0123/items/bb5b3f1064cf51c8b07e)

若干手こずりました。

## 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の挙動を確認する

```common-lisp
(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の比較です。高階関数の引数のリストは同じですが、最終的な戻り値が違います。

```common-lisp
(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は必要ないですが、次の例では必要です。

```common-lisp
(format t "~%~A" (mapcar #'+ *list1* *list2* *list3*))
;;; (6 66 666)

(format t "~%~A" (mapcan #'+ *list1* *list2* *list3*))
;;; 666
```

```common-lisp
(append (append (append nil '(6))
                '(66))
        '(666))
=> (6 66 666)

(cdr (nconc (nconc (nconc (list 'dummy) 6)
                   66)
            666))
=> 666
```

もっと良い解釈があるのかもしれません。

## CARのリストを取り出してみる。

```common-lisp
(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のリストを取り出してみる。

```common-lisp
(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のリストを取り出してみる。

```common-lisp
(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のリストを再帰的に取り出してみる

```common-lisp
(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))
```

## 高階関数を適用する

```common-lisp
(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に変えてみる

```common-lisp
(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する

```common-lisp
(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)

```common-lisp
(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)
```

正しく返りました！

## 整える

```common-lisp
(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)と初期化すると嵌ります。


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