SML# - Tutorial/017 Diff

  • Added parts are displayed like this.
  • Deleted parts are displayed like this.

[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/016]] | [[ 次ページ |Tutorial/018]] ]
----
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型のリストは以下のようにして作られたデータ構造である.
# 空リスト(nil)はリストである.
# Eが'a型の値,Lが'a list型のリストなら,E :: Lは'a list型のリストである
リストは,このように空か否かの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;
以上のパターンを用いた場合分け構文を再帰関数と一緒に使えば,種々のリス
ト処理関数を簡潔に効率よく定義可能である.
例として,リストの長さを計算する関数を書いてみよう.
リストの長さは,リストの構造に従い,以下のように特徴づけられる.
# 空のリストの長さは0である
# E :: Lの形のリストの長さは,部分リストLの長さに1を加えたものである.
この構造は,場合分けと再帰を使つかって以下のようにコードされる.
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
多くのリスト処理関数は,以上の考え方に従って記述できる.
以下の例を通じて,この考え方を習得しよう.

!!リストの総和を求める関数.
リストの総和は,再帰的に以下のように定義できる.
# 空のリストの総和は0である.
# h::tの形のリストの総和は,tのリストの総和にhを加えたものである.
これは以下のコードで実現できる.
fun sumList nil = 0
   | sumList (h::t) = h + sumList t

!!与えられた値が与えられたリストLに含まれるか否かを判定する関数.
値がリストに含まれるか否かは,再帰的に以下のように定義できる.
# 値は空リストには含まれない.
# ある値Eがh :: tの形のリストに含まれるのは,E = hであるかまたは,Eがtに含まれる時である.
この定義をそのままコード化すると以下のような関数となる.
fun member (E, nil) =  false
   | member (E, h::t) = E = h orelse member (E,t)

!!整数のリストの各要素を2倍する関数
処理は以下のように定義できる.
# 空のリストの要素を2倍して得られるリストは空である.
# h::tの形のリストの要素を2倍して得られるリストは,tのリストの要素を2倍して得られるリストの先頭に2*hを付け加えたものである.
この定義をそのままコード化すると以下のような関数となる.
fun doubleList nil = nil
   | doubleList (h::t) = h*2 :: doubleLust t

!!整数のリストをそれぞれの数の階乗のリストに変換する関数
処理は以下のように定義できる.
# 空のリストを変換して得られるリストは空である.
# h::tの形のリストを変換してリストは,tのリストを変換して得られるリストの先頭にfactorial hを付け加えたものである.
この定義をそのままコード化すると以下のような関数となる.
fun factorialList nil = nil
   | factorialList (h::t) = factorial h :: factorialList t

!!整数のリストを文字のリストに変換する関数
処理は以下のように定義できる.
# 空のリストを変換して得られるリストは空である.
# h::tの形のリストを変換して得られるリストは,tのリストを変換して得られるリストの先頭にhを変換した値を付け加えたものである.
この定義をそのままコード化すると以下のような関数となる.
fun toStringList nil = nil
   | toStringList (h::t) = Int.toString h :: toStringList t

!!文字のリストをアスキーコードに変換する関数
処理は以下のように定義できる.
# 空のリストを変換して得られるリストは空である.
# h::tの形のリストを変換して得られるリストは,tのリストを変換して得られるリストの先頭にhを変換した値を付け加えたものである.
この定義をそのままコード化すると以下のような関数となる.
fun toAsciiList nil = nil
   | toAsciiList (h::t) = ord h :: toAsciiList t
----
[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/016]] | [[ 次ページ |Tutorial/018]] ]