（１８）[ML] リストの扱い

[ トップ | 目次 | 前ページ | 次ページ ]

C言語の最も基本的でよく使われる構造データ配列とポインタであるとすれば，（初歩の）MLプログラミングで最もよく使用される複合データはリストと高階多相関数である．リストを用いたプログラムには，MLプログラミングの基本である以下の要素が含まれる．

• 再帰的データの生成と処理
• パターンマッチングによるデータ構造の分解
• 多相型高階関数

これらの習得が関数型言語マスターの鍵である．多数の簡単なリスト処理関数を通じてこれらの概念を学ぼう．

リストは要素のならびである．{と]の間に要素の式を並べると，リストが定義される．

# [1,2,3];
val it = [1, 2, 3] : int list

この式は，以下の式の略記法である．

# 1::2::3::nil;
val it = [1, 2, 3] : int list

この構文とその評価結果を理解しよう．

• e :: Lは要素を表す式eとリストを表す式Lから，リストLの先頭にeを付け加えて得られるリストを生成する式である．
• nilは空のリストを表す定数である．
• int listはint型を要素とするリストを表す型である．（このように，MLでは型構成子は後置される．）

記のような定数に限らず，任意の式を並べてリストを定義できる．MLプログラミングの原則

「式は型が正しいl限り自由に組み合わせることができる」

を思い出せば，以下のリストの例が理解できるはずである．

# fib 5 :: 1 + 1 :: [1,2,3];
val it = [8, 2, 1, 2, 3] : int list
# fib 4 :: factotial 4 :: 4 + 4 :: (if factorial 1 = 0 then nil else [1,2,3]);
val it = [5, 24, 8] : int list

整数のリスト以外に，任意の型のリストを作ることができる．上に書いた通り，唯一の制限は，すべての要素が同一の型をもつことである．以下は種々の型のリストの例である．

# [1.1, Math.pi, Math.sqrt 2.0];
val it = [1.1, 3.14159265359, 1.41421356237] : real list
# "I"::"became"::"operational"::"on"::"March 30, 2007"::nil;
val it = ["I", "became", "operational", "on", "March 30, 2007"] : string list
# [factorial, fib];
val it = [fn, fn] : (int  -> int) list
# [#"S", #"M", #"L", #"#"];
val it = [#"S", #"M", #"L", #"#"] : char list
# implode it;
val it = "SML#" : string
# explode it;
val it = [#"S", #"M", #"L", #"#"] : char list

implodeとexplodeはそれぞれ文字のリストを文字列に変換する関数および文字列を文字のリストに変換する関数である．

リスト構成子::と空リスト定数nilを使えば，種々のリスト生成関数を定義できる．

# fun cons (e,L) = e :: L;
val cons = fn : ['a .'a * 'a list  -> 'a list]

この関数の型は，consが'a型の値と'a list型の値を受け取り'a list型の値を返す関数であることを示している．そこで，この関数は，種々の型の値に適用し種々の型のリストを作ることができる．

# cons(1,nil);
val it = [1] : int list
# cons(#"S",nil);
val it = [#"S"] : char list

このような関数を多相関数とよぶ．この関数は，リスト構成子::を呼び出すだけであるから，::自身と同一である．

# op :: (1,nil);
val it = [1] : int list
# op :: (#"S",nil);
val it = [#"S"] : char list

ここで，op ::は演算子::を関数に変換する構文である．::に限らず，今までに出てきた演算子はopを着けることによって組みをとる通常として使用できる．

# op +;
val it = fn : int * int  -> int
# op + (1,2);
val it = 3 : int

次に整数nと値Eを受け取ってEをn個含む関数f(n,E)を定義してみよう．この関数は，nに関して再帰的に以下のように考えることができる．

• nが0ならf(0,E)は空リストである．
• nが1以上なら，f(n - 1,E)でn-1のリストを作り，その先頭にEを加えればよい．

そこで，f(n,E)は以下のようにコードできる．

# fun f (0 ,E) = nil
>   | f (n, E) = E :: f(n - 1, E);
val f = fn : ['a .int * 'a  -> 'a list]

この関数も多相型を持つので，以下のように種々の値に適用することができる．

# f (10,1);
val it = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : int list
# f (5,"SML#");
val it = ["SML#", "SML#", "SML#", "SML#", "SML#"] : string list
# f (7,#"S");
val it = [#"S", #"S", #"S", #"S", #"S", #"S", #"S"] : char list

全ての複合データ構造にあてはまる構造データの処理の原則は，

対象データの生成構造に対応した処理関数を書く

である．この原則に従えば，簡潔なプログラムを効率よく開発することができる． そのためにまず，リストの生成構造を確認しよう．

'a list型のリストは以下のようにして作られたデータ構造である．

1. 空リスト（nil）はリストである．
2. Eが'a型の値，Lが'a list型のリストなら，E :: Lは'a list型のリストである

リストは，このように空か否かの2つの場合がある．さらに，空でないリストは，その部分に（より小さな）リストを含む入れ子構造（再帰的構造）をしている．リストデータは，この構造に従って，まず．空か否かで場合分けを行い，空でない場合は，部分リストを再帰的に処理をする．従って，一般に以下のような構造をもつ．

1. リストが空の時は定数を返す．
2. 空でないリストは先頭要素と後続のリストに分解できる．まず，後続のリストを再帰的に処理し，その結果と先頭要素の値を使い，求める値を計算する．

場合分けは，リストの構造を関数の引数の位置に記述することによって行う．以下は簡単な例である．

# fun isEmptyList nil = true
   | isEmptyList (h::t) = false;
val isEmptyList = fn : ['a .'a list  -> bool]
# isEmptyList nil;
val it = true : bool
# isEmptyList [1,2];
val it = false : bool

関数isEmptyListは，リストの形を引数の位置に書き場合分けを行っている．この引数の位置に場合分けのために書いたリストの形をパターンとよぶ．パターンの中の変数には，引数で与えられるリストの対応する部分の値が与えられる．

# fun getFirst nil = ~1
>   | getFirst (h::t) = h;
val getFirst = fn : int list  -> int
# getFirst nil;
val it = ~1 : int
# getFirst [1,2,3];
val it = 1 : int

リストの形を判定するだけが目的で，値を取り出す必用がなければ，変数の代りにアンダースコア（_）を記述する．上記の関数はより簡潔に以下のように書ける．

fun isEmptyList nil = true
  | isEmptyList (_ :: _) = false;
fun getFirst nil = ~1
  | getFirst (h::_) = h;

場合分けは上から順にテストされるため，isEmptyは以下のように書いてもよい．

fun isEmptyList nil = true
  | isEmptyList (_ :: _) = false;

以上のパターンを用いた場合分け構文を再帰関数と一緒に使えば，種々のリスト処理関数を簡潔に効率よく定義可能である．例として，リストの長さを計算する関数を書いてみよう．リストの長さは，リストの構造に従い，以下のように特徴づけられる．

1. 空のリストの長さは0である
2. E :: Lの形のリストの長さは，部分リストLの長さに１を加えたものである．

この構造は，場合分けと再帰を使つかって以下のようにコードされる．

fun length nil = 0
  | length (h::t) = 1 + length t;

以下はその使用例である．

# fun length nil = 0
>   | length (h::t) = 1 + length t;
val length = fn : ['a .'a list  -> int]
# length [1,2,3,4,5];
val it = 5 : int

多くのリスト処理関数は，以上の考え方に従って記述できる．以下の例を通じて，この考え方を習得しよう．

リストの総和を求める関数．

リストの総和は，再帰的に以下のように定義できる．

1. 空のリストの総和は0である．
2. h::tの形のリストの総和は，tのリストの総和にhを加えたものである．

これは以下のコードで実現できる．

fun sumList nil = 0
  | sumList (h::t) = h + sumList t

与えられた値が与えられたリストLに含まれるか否かを判定する関数．

値がリストに含まれるか否かは，再帰的に以下のように定義できる．

1. 値は空リストには含まれない．
2. ある値Eがh :: tの形のリストに含まれるのは，E = hであるかまたは，Eがtに含まれる時である．

この定義をそのままコード化すると以下のような関数となる．

fun member (E, nil) =  false
  | member (E, h::t) = E = h orelse member (E,t)

整数のリストの各要素を2倍する関数

処理は以下のように定義できる．

1. 空のリストの要素を2倍して得られるリストは空である．
2. h::tの形のリストの要素を2倍して得られるリストは，tのリストの要素を2倍して得られるリストの先頭に2*hを付け加えたものである．

この定義をそのままコード化すると以下のような関数となる．

fun doubleList nil = nil
  | doubleList (h::t) = h*2 :: doubleLust t

整数のリストをそれぞれの数の階乗のリストに変換する関数

処理は以下のように定義できる．

1. 空のリストを変換して得られるリストは空である．
2. h::tの形のリストを変換してリストは，tのリストを変換して得られるリストの先頭にfactorial hを付け加えたものである．

この定義をそのままコード化すると以下のような関数となる．

fun factorialList nil = nil
  | factorialList (h::t) = factorial h :: factorialList t

整数のリストを文字のリストに変換する関数

処理は以下のように定義できる．

1. 空のリストを変換して得られるリストは空である．
2. h::tの形のリストを変換して得られるリストは，tのリストを変換して得られるリストの先頭にhを変換した値を付け加えたものである．

この定義をそのままコード化すると以下のような関数となる．

fun toStringList nil = nil
  | toStringList (h::t) = Int.toString h :: toStringList t

文字のリストをアスキーコードに変換する関数

処理は以下のように定義できる．

1. 空のリストを変換して得られるリストは空である．
2. h::tの形のリストを変換して得られるリストは，tのリストを変換して得られるリストの先頭にhを変換した値を付け加えたものである．

この定義をそのままコード化すると以下のような関数となる．

fun toAsciiList nil = nil
  | toAsciiList (h::t) = ord h :: toAsciiList t

[ トップ | 目次 | 前ページ | 次ページ ]