プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(51)

「実践Common Lisp」やります。

破壊的操作

先日は関数的なプログラミングとリストの相性についてでしたが、残念ながら破壊的操作があります。
まあ、変数に値をセットすらできないなんて嫌です。特に残念でもないですね。
破壊的操作には大まかに2種類あり、副作用それ自体が目的であるような操作と、
引数のコンスセルを使い回すような操作があるということです。

副作用を目的とした操作では、まあ色々ありそうですね。setfがその最たるものみたいな書かれ方です。
あまりに明らさまだし、今更それらを「破壊的だ」と言うこともないでしょう。
というわけで注意しなくてはいけないは、予想外の場所にその「破壊」が及んでしまうことですね。

CL-USER> (defparameter *list-1* (list 1 2))
*LIST-1*
CL-USER> (defparameter *list-2* (list 3 4))
*LIST-2*
CL-USER> (defparameter *list-3* (append *list-1* *list-2*))
*LIST-3*                                ;*list-3*のコンスセルは*list-2*
CL-USER> (setf (car *list-2*) 0)
0
CL-USER> *list-2*
(0 4)
CL-USER> *list-3*
(1 2 0 4)
CL-USER>

これは予想外の破壊ですね。ふむふむ。

使い回しの操作は、関数的なコードの中で利用することを意図されているそうです。
引数として与えられたコンスセルのいくつかを結果を作りあげるときに必要な加工をしリサイクルすると。
というわけで、オリジナルがもういらない時が安全にリサイクルできるときです。
このリサイクル関数には大抵破壊的でない類似の関数がいますが、
場合によってはリサイクル関数の方が有用でエコであるそうで。

リサイクルな関数と構造共有の組み合わせ

リサイクル関数で使った引数の中に後で使うつもりのものがあったら悲しいことになります。
つまり構造共有との組み合わせはあまりよろしくありません。
リサイクル関数を使うときは、どのコンスセルがどこから参照されているのか把握していなくてはいけなくなります。

実践ではリサイクルな関数を使うときにはお決まりのイディオムがあるそうです。
よく使われるのは、リストの前に「コンスしていく」ことで組み立てたリストを
関数から返すときにそれをnreverseし結果を返すというものだそう。
上記のイディオムを使ってゼロから始まるn個の数値をリストを組み立てる関数が例で出てきます。

CL-USER> (defun upto (max)
           (let ((result nil))
               (dotimes (i max)
                 (push i result))
               (nreverse result)))
UPTO
CL-USER> 

このように関数内部で生成されたリストを弄るなら何の心配もなくリサイクルできますな。

他によく使われるイディオムには、リサイクルな関数の戻り値を即座に代入することだそう。

CL-USER> (setf *list-3* (delete 4 *list-3*))
(1 2 0)
CL-USER> *list-2*
(0)
CL-USER>

まあ当然注意が必要で、上では*list-3*と構造を共有していた*list-2*も変わりました。
deleteではなくremoveを使えばこんなことにはならないので、どうせsetfするならそっちを使えばいいような。
あと、上の例で最初は0を消そうとしたのですが、それだと*list-2*は変更されませんでした。
なんでだろう。何度やり直しても同じでした。
まあ、上の2例がリサイクルな関数を使う時のイディオムの8割を占めるそうです。

リストを操作するときは関数的なスタイルでコードを記述するのがベストだそうです。
関数は引数のリストの内容にだけ依存し、引数を変更しないようにするというルールに従えば
破壊的関数もリサイクルな関数も綺麗に排除することができます。
一旦は関数的なスタイルでコードを書きあげ、、最適化が必要なら、引数のリストが他のどこからも
参照されていないことを確認してから非破壊的なリスト操作をリサイクルバージョンに書きかえようとのこと。

あと、sort,stable-sort,margeはリストに適用したときはリサイクルな関数となるらしいです。
リストを破壊せずにソートするには、copy-listで生成したコピーを引数にする必要あると。
本当かな。

CL-USER> (defparameter *list* (list 4 3 2 1))
*LIST*
CL-USER> (sort *list* #'<)
(1 2 3 4)
CL-USER> *list*
(3 4)
CL-USER>

本当でした。

リスト操作関数

リスト操作のためのライブラリ関数を眺めていきます。
carとcdrをずっと使っていますが、firstとrestという同じ機能の関数があるようです。
まあ、そっちのほうがぱっと見でわかりやすい...のかな。今となってはどっちでも。
また、先頭から2番目の要素が欲しいとかいうときのため、secondからtenthまでの関数もあるそう。
これは便利そうですね。

CL-USER> (defparameter *list* (list 0 1 2 3 4 5 6 7 8 9))
*LIST*
CL-USER> (cadddr *list*)
3
CL-USER> (fourth *list*)
3
CL-USER> (cadddr (cdddr (cdddr *list*)))
9
CL-USER> (tenth *list*)
9
CL-USER>

凄い便利です。
じゃあもうcarやcdrなんて要らないのかななんて思いますが、
これらの関数はリストを扱うものというよりツリーを扱うためのもの、とあり用途によって使い分けると
プロ意識があるように見せかけられるかもしれません。
ツリーのデータを扱うときにfirstとか使ってたら実際変な感じがしますよね。多分。
でも多分これからもcarとcdr使っちゃいそうな気がします。secondとかは活用したいです。

他にも色々リスト操作関数が紹介されていますが、日常的に使いそうなのは
consp,atom,listp,nullぐらいな気がします。

マッピング

関数的スタイルのもう1つの重要な側面として高階関数の利用があるそうです。
おさらいですが、高階関数とは関数を引数として取ったり、戻り値が関数だったりするものです。
そしてCommon Lispにはリスト専用の6つのマッピング関数があるそうです。

1つはmapcar。ほぼmapですが、戻り値の型はリスト限定なので戻り値の型指定の引数が要らず、
第一引数に関数、それ以降の引数に関数に適用する要素を持つリストを取ります。
maplistはmapcarに似ているけど、関数に渡されるのがリストの要素ではなくコンスセルになるという
違いがあるようです。ふむ。

CL-USER> (maplist #'list '(1 2 3) '(10 20 30))
(((1 2 3) (10 20 30)) ((2 3) (20 30)) ((3) (30)))
CL-USER>

なるほど。なかなか使いどころはありそうですね。
mapcanとmapconは、それぞれmapcarとmaplistに似た動作をするそうです。戻り値の組立て以外。
mapcar,maplistは結果を保持するのに完全に新しいリストを作るのに対し、
mapcanとmapconは結果をnconcのように繋ぎ合わせるそうです。

CL-USER> (defparameter *list-2* (list 3 4))
*LIST-2*
CL-USER> (defparameter *list-1* (list 1 2 ))
*LIST-1*
CL-USER> (nconc *list-1* *list-2*)
(1 2 3 4)
CL-USER> *list-1*
(1 2 3 4)
CL-USER> *list-2*
(3 4)
CL-USER>

ふむふむ。これがnconc。

CL-USER> (mapcan #'+ *list-1* *list-2*)
6
CL-USER> *list-1*
(1 2)
CL-USER> *list-2*
(3 4)
CL-USER> (mapcon #'list *list-1* *list-2*)
((1 2) (3 4) (2) (4))
CL-USER> *list-1*
(1 2)
CL-USER> *list-2*
(3 4)
CL-USER> (mapcar #'+ *list-1* *list-2*)
(4 6)
CL-USER> (maplist #'list *list-1* *list-2*)
(((1 2) (3 4)) ((2) (4)))
CL-USER> (mapcan #'list *list-1* *list-2*)
(1 3 2 4)
CL-USER> 

関数を適用した結果の1つ1つをリストにしてそのリストを繋ぎ合わせていくイメージでしょうか。
残りはmapcとmapl。mapcは使ったことがあります。どちらとも関数ではなく制御構文だそう。
mapcがmapcarの、maplがmaplの一派で、いずれも最初のリスト引数をそのまま返します。
適用する関数の副作用だけを目当てに使うようで、また新たにリストを生成しない分速いらしいです。
「Land of Lisp」にそう書いてあった気がします。

久し振りに更新することができた満足感でいっぱいです。おやすみなさい。