関数型プログラミング事始め (37) イミュータブル(2)
関数型プログラミングがはじめての方へ贈る入門の書
前節：イミュータブル(1) 次節：状態
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
ここではイミュータブルデータを使った例として、前回はランダムアクセスリストを紹介しましたが、今回はツリートラバースと待ち行列、エイトクイーンを見ていきます。
(3) イミュータブルデータの例
イミュタブルデータとは通常のような値がミュータブル（可変）なデータではなく、値が不変なデータです。プログラムのバグの原因の多くは、グローバルデータを不用意に変更してしまうことから起こります。イミュータブルデータではこのようなバグは起こりません。
でも空間と時間の効率が悪いのは秘密です。
この節ではイミュータブルデータを使ったプログラムの例を見ていくことにします。前節では配列と等価なランダムアクセスリストを紹介しましたが、ここではツリートラバースと待ち行列、エイトクイーンを見ていきます。
ここではOK! ISLispを使ってイミュータブルデータの例を見ていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。
> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>
(a) ツリートラバース
ツリートラバースとは、ツリー構造のデータの各ノードを巡回(トラバース traverse)するものです。
ここでツリー構造として、例えば、1→2→3と1→4→5の親子関係があるツリー構造のデータを考えてみます。これを(1 (2 3) (4 5))のリストで表現します。
ISLisp>
(defun traverse (tree fun)
(if (null tree)
nil
(if (consp (car tree))
(cons (traverse (car tree) fun) (traverse (cdr tree) fun))
(cons (funcall fun (car tree)) (traverse (cdr tree) fun)) )))
TRAVERSE
ISLisp>(traverse '(1 (2 3) (4 5)) (lambda (x) (+ x 1)))
(2 (3 4) (5 6))
関数traverseは第1引数のツリーの各ノードに対して、第２引数の関数を適用するものです。(traverse '(1 (2 3) (4 5)) (lambda (x) (+ x 1)))では、(1 (2 3) (4 5))のツリーの各ノードの1,2,3,4,5に対して、要素をプラス1したツリーを返すものです。
関数traverseはトラバースするときに、consを使って、引数のツリー構造と同じ構造を持ったツリーを新規に生成してます。これによって、引数のツリーには副作用を生じません。イミュータブルデータであることを保証しています。
(b) 待ち行列
待ち行列(キュー queue)は、先入れしたデータを先出し(First-In First-Out)するデータ構造です。待ち行列にデータを入れる関数をenq(enter queue)として、待ち行列から先頭のデータを削除した待ち行列を返す関数をdeq(delete queue)とし、待ち行列の先頭のデータを取り出す関数をheadとします。
待ち行列をリストで表現したときに、一番簡単な（で一番効率の悪い）実装は以下のようになります。
ISLisp>(defun enq (e queue) (cons e queue))
ENQ
ISLisp>(defun deq (queue) (reverse (cdr (reverse queue))))
DEQ
ISLisp>(defun head (queue) (car (reverse queue)))
HEAD
この待ち行列は単純に逆順のリストを生成するreverse関数で実装しています。つまりdeqとheadするときに、毎回reverseによるコピー操作をしています。この効率は非常に悪いものになっています。
なおheadではリストの最後尾のデータを返すだけなので、本来はコピーする必要はありませんが、ここでは簡単のためにreverseで実装しています。
待ち行列の実行は以下のようになります。
ISLisp>(defglobal queue ())
QUEUE
ISLisp>(setq queue (enq 1 queue))
(1)
ISLisp>(setq queue (enq 2 queue))
(2 1)
ISLisp>(setq queue (enq 3 queue))
(3 2 1)
ISLisp>(head queue)
1
ISLisp>(setq queue (deq0 queue))
(3 2)
ISLisp>(head0 queue)
2
(c) ２本のリストによる効率の良い待ち行列
ここではenq用のリストとdeq用のリストの２本のリストによる待ち行列の実装を見ていきます。２本のリストを用意することで効率の良い待ち行列の実装になっています。
ISLisp>
(defun enq (e queue)
(if (null (car queue))
(cons (cons e (car queue)) (cdr queue))
(cons (car queue) (cons e (cdr queue))) ))
ENQ
ISLisp>
(defun deq (queue)
(if (null (cdr (car queue)))
(cons (reverse (cdr queue)) nil)
(cons (cdr (car queue)) (cdr queue)) ))
DEQ
ISLisp>
(defun head (queue)
(car (car queue)) )
HEAD
待ち行列は、(deq用リスト . enq用リスト)の構造をしています。deqするときにコピーの回数が減少することに注目してください。
実行は以下のようになっています。
ISLisp>(defglobal queue '(nil . nil))
QUEUE
ISLisp>queue
(NIL) ; (nil . nil)
ISLisp>(setq queue (enq 1 queue))
((1)) ; ((1) . nil)
ISLisp>(setq queue (enq 2 queue))
((1) 2) ; ((1) . (2))
ISLisp>(setq queue (enq 3 queue))
((1) 3 2) ; ((1) . (3 2))
ISLisp>(head queue)
1
ISLisp>(setq queue (deq queue))
((2 3)) ; ((2 3) . nil)
ISLisp>(head queue)
2
ISLisp>(setq queue (deq queue))
((3)) ; ((3) . nil)
ISLisp>(head queue)
3
(c) エイトクイーン
エイトクイーン(8-queen)はチェス盤(8x8)に８枚のクイーン（縦、横、斜めに移動可能（利き筋）なチェスの駒）を配置して、お互いにクイーンの利き筋に配置しないようにするパズルです。
ここでは8人のクイーンに制限せずに、n人のクイーンをnxnのチェス盤に配置するnクイーン(n-queen)に拡張して、プログラムを作ってみます。
この関数の値は各列に配置する行番号のリスト(c1 c2 c3 … cn)を返します。例えば(3 2 1)とは3行1列、2行2列、1行3列にクイーンを配置することになります（なお、これはお互いのクイーンの利き筋に配置していますので失敗です）。
ISLisp>(defun nqueen (n) (nqueen2 n 1 nil) )
NQUEEN
ISLisp>
(defun nqueen2 (n y board)
(if (> y n)
nil
(if (or (member y board) (diagonal 1 y board))
(nqueen2 n (+ y 1) board)
(append
(if (= (length board) (- n 1))
(list (cons y board))
(nqueen2 n 1 (cons y board)) )
(nqueen2 n (+ y 1) board) ))))
NQUEEN2
ISLisp>
(defun diagonal (x queen board)
(if (null board)
nil
(if (= (abs (- (car board) queen)) x)
t
(diagonal (+ x 1) queen (cdr board)) )))
DIAGONAL
関数DIAGONALは既に配置しているクイーンの利き筋にあるかどうかを判定する関数です。この聞き筋判定関数を使って、nqueen2で順に配置して、配置が不可能になった場合は最初からやり直すことを再帰呼び出しで実装しています。
このときにnqueen2ではappendとconsによってコピーするようにしています。これでイミュータブルデータにしています。
nqueenを実行すると以下のようになります。
ISLisp>(nqueen 8)
((4 2 7 3 6 8 5 1) (5 2 4 7 3 8 6 1) (3 5 2 8 6 4 7 1) (3 6 4 2 8 5 7 1) (5 7 1 3 8 6 4 2) (4 6 8 3 1 7 5 2) (3 6 8 1 4 7 5 2) (5 3 8 4 7 1 6 2) (5 7 4 1 3 8 6 2) (4 1 5 8 6 3 7 2) (3 6 4 1 8 5 7 2) (4 7 5 3 1 6 8 2) (6 4 2 8 5 7 1 3) (6 4 7 1 8 2 5 3) (1 7 4 6 8 2 5 3) (6 8 2 4 1 7 5 3) (6 2 7 1 4 8 5 3) (4 7 1 8 5 2 6 3) (5 8 4 1 7 2 6 3) (4 8 1 5 7 2 6 3) (2 7 5 8 1 4 6 3) (1 7 5 8 2 4 6 3) (2 5 7 4 1 8 6 3) (4 2 7 5 1 8 6 3) (5 7 1 4 2 8 6 3) (6 4 1 5 8 2 7 3) (5 1 4 6 8 2 7 3) (5 2 6 1 7 4 8 3) (6 3 7 2 8 5 1 4) (2 7 3 6 8 5 1 4) (7 3 1 6 8 5 2 4) (5 1 8 6 3 7 2 4) (1 5 8 6 3 7 2 4) (3 6 8 1 5 7 2 4) (6 3 1 7 5 8 2 4) (7 5 3 1 6 8 2 4) (7 3 8 2 5 1 6 4) (5 3 1 7 2 8 6 4) (2 5 7 1 3 8 6 4) (3 6 2 5 8 1 7 4) (6 1 5 2 8 3 7 4) (8 3 1 6 2 5 7 4) (2 8 6 1 3 5 7 4) (5 7 2 6 3 1 8 4) (3 6 2 7 5 1 8 4) (6 2 7 1 3 5 8 4) (3 7 2 8 6 4 1 5) (6 3 7 2 4 8 1 5) (4 2 7 3 6 8 1 5) (7 1 3 8 6 4 2 5) (1 6 8 3 7 4 2 5) (3 8 4 7 1 6 2 5) (6 3 7 4 1 8 2 5) (7 4 2 8 6 1 3 5) (4 6 8 2 7 1 3 5) (2 6 1 7 4 8 3 5) (2 4 6 8 3 1 7 5) (3 6 8 2 4 1 7 5) (6 3 1 8 4 2 7 5) (8 4 1 3 6 2 7 5) (4 8 1 3 6 2 7 5) (2 6 8 3 1 4 7 5) (7 2 6 3 1 4 8 5) (3 6 2 7 1 4 8 5) (4 7 3 8 2 5 1 6) (4 8 5 3 1 7 2 6) (3 5 8 4 1 7 2 6) (4 2 8 5 7 1 3 6) (5 7 2 4 8 1 3 6) (7 4 2 5 8 1 3 6) (8 2 4 1 7 5 3 6) (7 2 4 1 8 5 3 6) (5 1 8 4 2 7 3 6) (4 1 5 8 2 7 3 6) (5 2 8 1 4 7 3 6) (3 7 2 8 5 1 4 6) (3 1 7 5 8 2 4 6) (8 2 5 3 1 7 4 6) (3 5 2 8 1 7 4 6) (3 5 7 1 4 2 8 6) (5 2 4 6 8 3 1 7) (6 3 5 8 1 4 2 7) (5 8 4 1 3 6 2 7) (4 2 5 8 6 1 3 7) (4 6 1 5 2 8 3 7) (6 3 1 8 5 2 4 7) (5 3 1 6 8 2 4 7) (4 2 8 6 1 3 5 7) (6 3 5 7 1 4 2 8) (6 4 7 1 3 5 2 8) (4 7 5 2 6 1 3 8) (5 7 2 6 3 1 4 8))
ISLisp>(nqueen 3)
NIL
ISLisp>(nqueen 4)
((3 1 4 2) (2 4 1 3))
ISLisp>(length (nqueen 8))
92
ISLisp>(length (nqueen 5))
10
エイトクイーンはいかがだったでしょうか。イミュータブルデータの例と言うよりも再帰プログラミングの例として、おいしい例になっています。
(予告) 3.6 状態の繰り込み
次回は副作用のもとになる「状態」を引数として関数の世界に繰り込むことを見ていきます。
いいなと思ったら応援しよう！
