Chapter 04

関数によるリスト処理

TAKIZAWA Yozo
TAKIZAWA Yozo
2021.12.27に更新

連結リストとmap

関数型プログラミングでは,リスト構造,特に,次の図で示されるような連結リストと呼ばれるデータ構造がよく用いられます.同じ型の値が整然と並んでいる配列と異なり,様々な種類の値を数珠つなぎに結びつけているため,再帰関数規則による処理が行いやすいためです[1]

上記の図と同じ構造をLISP系言語で定義するには,組込関数consを用いて次のように表現します.なお,fpLISPでは,偽の値であるnilを,リスト構造の最後を示す『空リスト』を指定するためにも用いています.

fpLISP
(cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil)))))
(10 20 30 40 50)

評価結果の通り,連結リストは,関数規則を構成する方法(括弧と空白区切り)と同じ表現を用いています.空白区切りのため,左からも右からも順番につながっているように見えますが,あくまで,左の先頭からつながっているものと捉えて下さい.

ここで,連結リストのそれぞれの要素について,同じ関数規則を適用することを考えます.そのために更に必要な組込関数としては,consの逆,すなわち,連結リストの先頭の要素を参照する関数と,先頭の要素を除いた残りの要素をもつ連結リストを参照する関数があります[2].LISP系言語では,前者をcar,後者はcdrを用います.

fpLISP
(car (cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil))))))
10 ⇒ 最初のconsの1番目の引数と同じ
fpLISP
(cdr (cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil))))))
(20 30 40 50) ⇒ 最初のconsの2番目の引数と同じ

まず,conscarcdrを用いて,引数に指定した連結リストの値を先頭から取り出し,また連結リストとしてつなげていく関数規則を構成してみます.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x)
      (if (eq x nil) nil
          (cons (car x) ((u u) (cdr x)))))))
 (cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil))))))
(10 20 30 40 50)

ここで,連結リストを再構築する際に,(cons (car x) ((u u) (cdr x)))としています.それぞれの要素に同じ関数規則を適用するには,この部分の(car x)を引数として適用すると良いことがわかります.次は,(lambda (x) ...)の引数に関数fを加えて(lambda (f x) ...)とし,引数fに『引数に1を足して返すラムダ式』を値として与えた例です.fは,(u u)の引数にも追加していることに注意して下さい.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      (if (eq x nil) nil
          (cons (f (car x)) ((u u) f (cdr x)))))))
 (lambda (x) (+ x 1))
 (cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil))))))
(11 21 31 41 51)

連結リストの各要素に同じ関数規則を適用するこのような関数はmapと呼ばれています.ちなみに,関数fはどのようなラムダ式でも良いので,前章のフィボナッチ数を求める再帰関数を引数の値としてみましょう.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      (if (eq x nil) nil
          (cons (f (car x) 0 1) ((u u) f (cdr x)))))))
 ((lambda (u) (u u))
  (lambda (u)
    (lambda (n a b)
      (if (eq n 0) a
          ((u u) (- n 1) b (+ a b))))))
 (cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil))))))
(55 6765 832040 102334155 12586269025)

ところで,LISP系言語にはlistがあり,引数から連結リストを作成する関数です.構文ではなく,あくまで関数であり,複数の引数をとってそれぞれを評価した結果を要素としたリストを作ります.引数の数が不定であるため,本来であれば組込関数として提供されるところです.ですがfpLISPでは,ラムダ式の変数に,リストではなく,ひとつの変数のみを指定することで,そのひとつの変数が複数の引数全てを対象とする,すなわち,リストとして得ることが可能です.これは,listの関数機能そのものです.

fpLISP
((lambda x x) 10 (+ 20 1) 30 (- (* 40 50) 100))
(10 21 30 1900)

連想リストとassoc

連想リストとは,ふたつの値のセット(ペア)をリストとして構成しているデータ構造で,こちらも関数型プログラミングではよく用いられます[3]

LISP系言語の場合,consがもともとペアを作成する関数であることから,上記の図で示される連想リストは次のように表現できます.

fpLISP
((lambda x x) (cons 1 10) (cons 2 20) (cons 3 30) (cons 4 40) (cons 5 50))
((1 . 10) (2 . 20) (3 . 30) (4 . 40) (5 . 50))

consによって作られたペア構造は,括弧と空白区切り,そして,ドットを用いた出力となります.なお,連結リストである

fpLISP
(cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil)))))

についても,ペア構造の評価結果と同じであるならば,

(10 . (20 . (30 . (40 . (50 . nil)))))

となるのですが,連結リストについては,空白のみで区切られる

(10 20 30 40 50)

の方がとても見やすいため,慣例的に後者の形式で評価結果が出力されます[4]

連想リストは,ペア構造を(検索キー . 値)とすることで,検索キーに対応する値を取り出すためのデータ構造を構成することによく使われます[5].例として,上記の連想リストを検索キーと値のペアのリストとみなした場合の,検索キー3に対応する値30を求めるラムダ式を次に示します.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (k v)
      (if (eq v nil) nil
          (if (eq k (car (car v)))
              (cdr (car v))
              ((u u) k (cdr v)))))))
 3
 ((lambda x x)
  (cons 1 10) (cons 2 20) (cons 3 30) (cons 4 40) (cons 5 50)))
30

検索時は(car (car v))と比較しているのに対し,合致した場合には(cdr (car v))の評価結果を返していることに注意して下さい.なお,連想リストを検索する関数規則はassoc呼ばれることがあります.

畳み込み処理foldfilter

前々節で登場したmapの例をもう一度見てみます.ただし,連結リストはlist相当のラムダ式を用いて構築しています.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      (if (eq x nil) nil
          (cons (f (car x)) ((u u) f (cdr x)))))))
 (lambda (x) (+ x 1))
 ((lambda x x) 10 20 30 40 50))
(11 21 31 41 51)

この例について,ラムダ式本体のcons+に変更するとどのようになるでしょうか?ただし,数値計算に変更となるため,最後に返すのはリストの最後を示すnilではなく0とします.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      (if (eq x nil) 0
          (+ (f (car x)) ((u u) f (cdr x)))))))
 (lambda (x) (+ x 1))
 ((lambda x x) 10 20 30 40 50))
155

変更前の結果のリスト内の値を合計した結果となりました.これは,各要素に適用するラムダ式を(lambda (x) x)とすることで,実際には何も適用しないことにすると,単純に,引数として与えた連結リスト内の値を合計した結果が得られることを意味します.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      (if (eq x nil) 0
          (+ (f (car x)) ((u u) f (cdr x)))))))
 (lambda (x) x)
 ((lambda x x) 10 20 30 40 50))
150

次は,引数fを,各要素に適用するラムダ式ではなく,上記の+に置き換えた箇所の関数とすることにした例です.なお,最後に返す値についても引数iに置き換えています.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x i)
      (if (eq x nil) i
          (f (car x) ((u u) f (cdr x) i))))))
 (lambda (a b) (+ a b))
 ((lambda x x) 10 20 30 40 50)
 0)
150

上記は,次の処理に相当します.

fpLISP
(+ 10 (+ 20 (+ 30 (+ 40 (+ 50 0)))))

ここで,足し算の計算を行うラムダ式を,元のconsを行うラムダ式に変更してみます.最後に返す値もnilに戻します.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x i)
      (if (eq x nil) i
          (f (car x) ((u u) f (cdr x) i))))))
 (lambda (a b) (cons a b))
 ((lambda x x) 10 20 30 40 50)
 nil)
(10 20 30 40 50)

与えた連結リストそのままが結果となりました.これは, 次の処理に相当するためです.+consに,0nilに置き換わっていることがわかります.

fpLISP
(cons 10 (cons 20 (cons 30 (cons 40 (cons 50 nil)))))

このように,連結リストの各要素に,数珠繋ぎのように関数適用していく処理を畳み込み処理といい,foldまたはreduceと呼ばれています[6]

ところで,上記の例では,それぞれの要素をそのままリストに追加しています.ここで,判断分岐を行う適用関数を指定するとどのようになるでしょうか?次は,連結リストの要素が4で割り切れるならばそのままリストに追加し,そうでなければリストに追加しないラムダ式の例です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x i)
      (if (eq x nil) i
          (f (car x) ((u u) f (cdr x) i))))))
 (lambda (a b) (if (eq (% a 4) 0) (cons a b) b))
 ((lambda x x) 10 20 30 40 50)
 nil)
(20 40)

このような『ふるい分け』を行う処理はfilterと呼ばれています.

逆畳み込み処理unfold

前節で畳み込み処理を取り上げましたが,逆の処理,すなわち,初期値に所定の関数を次々と適用して連結リストを生成する処理はあるのでしょうか?その例が,次の0から5の整数列のリストを生成するラムダ式です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x)
      (if (lt 5 x) nil
          (cons x ((u u) (+ x 1)))))))
 0)
(0 1 2 3 4 5)

初期値を0として与えると,値をひとつずつ増やしながらリストに追加していき,値が5を超えた時点でリストの最後を示すnilを返して出力します.これは,次の関数適用と同じ処理を行っています.

fpLISP
(cons 0 (cons (+ 0 1) (cons (+ (+ 0 1) 1) (cons (+ (+ (+ 0 1) 1) 1) (cons (+ (+ (+ (+ 0 1) 1) 1) 1) (cons (+ (+ (+ (+ (+ 0 1) 1) 1) 1) 1) nil))))))

このラムダ式を,前節の畳み込み処理の時と同じように,処理内容の一部を引数にしてみます.まず,リストの最後となることを判定する条件式を引数pとします.これで,引数によって任意の範囲の整数列を生成することができるようになります.下記は,3から7までの整数列を生成する例です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (p x)
      (if (p x) nil
          (cons x ((u u) p (+ x 1)))))))
 (lambda (x) (lt 7 x))
 3)
(3 4 5 6 7)

次に,繰り返し呼び出されるたびに行われる式を引数gとします.これで,引数によって任意の数だけ増やしていくことができるようになります.下記は,0から10を超えるまでふたつずつ増やしながら値をリストに追加していく例です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (p g x)
      (if (p x) nil
          (cons x ((u u) p g (g x)))))))
 (lambda (x) (lt 10 x))
 (lambda (x) (+ x 2))
 0)
(0 2 4 6 8 10)

更に,リストに追加する際に値を加工する関数の引数bを追加します.これにより,リスト生成の際にmapと同じ処理を行わせることができます.次は,0から10を超えるまで値をひとつずつ増やし,その値を二乗してからリストに追加していく例です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (p b g x)
      (if (p x) nil
          (cons (b x) ((u u) p b g (g x)))))))
 (lambda (x) (lt 10 x))
 (lambda (x) (* x x))
 (lambda (x) (+ x 1))
 0)
(0 1 4 9 16 25 36 49 64 81 100)

最後に,p b gfに統合します.具体的には,pに相当する処理が偽となった時にnilを返す,b gの結果はconsによるふたつの要素のペアとして返す,といった構成のラムダ式fを想定します.次は,そのようなラムダ式に変更した上で,上記と同じ処理を行うラムダ式の例です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      (if (eq (f x) nil) nil
          (cons (car (f x))
                ((u u) f (cdr (f x))))))))
 (lambda (x) (if (lt 10 x) nil (cons (* x x) (+ x 1))))
 0)
(0 1 4 9 16 25 36 49 64 81 100)

ところで,上記のラムダ式本体は(f x)が3回登場し,その都度同じ評価が実行されるため効率が悪くなります.そこで,第二章で登場したlet相当のラムダ式を追加することで,(f x)を1回だけ評価・実行してrという名前を付けて利用すれば良いようにします.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      ((lambda (r)
         (if (eq r nil) nil
             (cons (car r) ((u u) f (cdr r)))))
       (f x)))))
 (lambda (x) (if (lt 10 x) nil (cons (* x x) (+ x 1))))
 0)
(0 1 4 9 16 25 36 49 64 81 100)

これで完成です.このように,初期値に関数適用を繰り返してリストを生成する処理を逆畳み込み処理といい,unfoldと呼ばれています.応用例として,第三章で登場したフィボナッチ数を求める処理について,単純にn番目の値を求めるのではなく,求める過程で得られるフィボナッチ数をリストに追加していくラムダ式を次に示します.なお,終了する条件は,追加しようとする値が11000を超えた場合です.したがって,0番目から21番目のフィボナッチ『数列』が得られます.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      ((lambda (r)
         (if (eq r nil) nil
             (cons (car r) ((u u) f (cdr r)))))
       (f x)))))
 (lambda (x) (if (lt 11000 (car x)) nil
                 (cons (car x)
                       (cons (cdr x) (+ (car x) (cdr x))))))
 (cons 0 1))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)

この例では,初期値が数値ではなく,consを用いたペア構造(0 . 1)となっていることに注意して下さい.この(0 . 1)に,併せて指定したラムダ式を適用すると,次の結果が得られます(rに与える(f x)の結果に相当します).

(cons 0 (cons 1 (+ 0 1))) => (0 . (1 . 1))

最初のcons0は書き換え前のfに対する引数相当,次のcons(1 . 1)は書き換え前のgに対する引数相当です.書き換え前のラムダ式で表現し直すと次のようになります.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (p b g x)
      (if (p x) nil
          (cons (b x) ((u u) p b g (g x)))))))
 (lambda (x) (lt 11000 (car x)))
 (lambda (x) (car x))
 (lambda (x) (cons (cdr x) (+ (car x) (cdr x))))
 (cons 0 1))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)

検索処理member

先に登場したassocは,連想リストのキー検索に特化した関数です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (k v)
      (if (eq v nil) nil
          (if (eq k (car (car v)))
              (cdr (car v))
              ((u u) k (cdr v)))))))
 3
 ((lambda x x)
  (cons 1 10) (cons 2 20) (cons 3 30) (cons 4 40) (cons 5 50)))
30

これを,foldunfoldのように,より一般化してみましょう.まず,比較をしている(eq k (car (car v)))を引数fにします.これは,引数kが関数fの一部となることを意味しますので,引数kは不要となり,引数fの中で検索キーである3`を組み込むことになります.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f v)
      (if (eq v nil) nil
          (if (f v)
              (cdr (car v))
              ((u u) f (cdr v)))))))
 (lambda (x) (eq 3 (car (car x))))
 ((lambda x x)
  (cons 1 10) (cons 2 20) (cons 3 30) (cons 4 40) (cons 5 50)))
30

次に,連想リスト固有の結果処理である(cdr (car v))を,単純に,合致した要素を取り出す(car v)に変更します.これにより,連想リストの場合は結果として(3 . 30)といったキーと値のペアが関数出力されることになりますが,その出力にcdrを適用することで,検索結果の値の部分だけ取り出すことが可能です.

fpLISP
(cdr 
  (((lambda (u) (u u))
    (lambda (u)
      (lambda (f v)
        (if (eq v nil) nil
            (if (f v) (car v)
                ((u u) f (cdr v)))))))
   (lambda (x) (eq 3 (car (car x))))
   ((lambda x x)
    (cons 1 10) (cons 2 20) (cons 3 30) (cons 4 40) (cons 5 50))))
30

この段階で,連想リストではなく,値が並んだだけの連結リストに対する処理を行ってみましょう.引数として指定する関数は,連想リストではないため,単純に連結リストの最初の要素(car x)との比較とします.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f v)
      (if (eq v nil) nil
          (if (f v) (car v)
              ((u u) f (cdr v)))))))
 (lambda (x) (eq 30 (car x)))
 ((lambda x x) 10 20 30 40 50))
30

これで,一応,検索のための式はできました.ですが,これだけでは,ある要素が引数の連結リストに含まれているかどうかを確認する機能しか利用できません.たとえば,連結リストに同じ要素がいくつも含まれている場合,上記の処理では,最初に一致した要素しかわかりません.

そこで,一致した要素以降の連結リストを返す式に変更します.これは,合致した時点の連結リストの最初の要素のみを返すのではなく,その時点の連結リストをそのまま返すよう変更するだけで済みます.また,合致する要素がなかった場合はnilを返しますので,このように変更しても,合致する要素があったかなかったかを判定することが可能です.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (f v)
      (if (eq v nil) nil
          (if (f v) v
              ((u u) f (cdr v)))))))
 (lambda (x) (eq 30 (car x)))
 ((lambda x x) 10 20 30 40 50))
(30 40 50)

このような処理は,LISP系言語ではmemberと呼ばれます[7]

練習問題

次は,引数のひとつに0以上の整数xを指定すると,0からx-1までの整数が要素として並ぶ連結リスト(x=0の時は空リストを表すnil)を出力する関数規則の一部と,x=10で評価している時の出力結果です.不足している記述を考えて完成させたプログラムコードを解答して下さい.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x r)
      (if (eq x 0) r
          ((u u)                        )))))
 10 nil)
(0 1 2 3 4 5 6 7 8 9)
脚注
  1. 連結リストのデータ構造が再帰的,とも言えます. ↩︎

  2. 先頭の要素を取り出す関数と先頭の要素を取り除く関数,ではないことに注意して下さい.第一章で述べたように,連結リストはどこかに『格納』されているわけではなく,引数の値として与えられるだけに過ぎません. ↩︎

  3. 他のプログラミング言語でいう,連想配列や辞書型,ハッシュテーブルに近い使い方が可能です. ↩︎

  4. 実際は,LISPプログラム自身が連結リスト構造で表現されでおり,LISPプログラムでLISPプログラムを操作しやすくするため,というのが最大の理由です. ↩︎

  5. 特に,(変数名 . 値)とすることで,プログラミング言語処理系における変数管理に使われます. ↩︎

  6. ここで紹介した畳み込み処理は,実際の処理の流れの通り,連結リストの左側から関数適用が行われています.このため,foldは正確にはfoldlまたはfold-leftと呼ばれています. ↩︎

  7. memberは正確には,引数指定した要素以降のリストを返す関数処理を指します.この例のように,引数指定にラムダ式を指定するものはmember-ifまたはfind-tailと呼ばれています. ↩︎