SML# - Tutorial/018 Diff

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

[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/017]] | [[ 次ページ |Tutorial/019]]
----
高階関数とは,関数を受け受けっ取ったり関数を返したりする関数のことである.
この概念を理解し高階関数を使いこなそう.

!よく使われる計算パターンを見つける(1):算術演算の場合

高階関数を理解するために,[[再帰関数のページ|Tutorial/009-1]]で学んだ和を求める幾つかの関数を振り返ってみよう.
fun sum 0 = 0
   | sum n = n + sum (n - 1)

fun sigma2 0 = 0
   | sigma2 n = n * n + sigma2 (n - 1)

fun sigma3 0 = 0
   | sigma3 n = n * n * n + sigma2 (n - 1)

これら3つの関数の骨格は共通している.
この計算パターンを高等学校で学習するシグマ記号を使えば,以下のように表される.

||!ML関数||!対応するシグマ表記||シグマ表記が満たす等式||
|| sum(n) || [[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma1Sym.gif]]|| [[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma1.gif]]||
|| sigma2(n) || [[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma2Sym.gif]]||[[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma2.gif]]||
|| sigma3(n) || [[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma3Sym.gif]]||[[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma3.gif]]||

上記の例から理解されるとおり,シグマ記法は,関数の和を求める計算のパター
ンに名前をつけたものである.
整数関数の和を求める計算パターンをシグマ記法を通じて理解してしまえば,
種々の関数和の計算を関数の和の計算を含む計算を簡潔に分かりやすく記述することができる.

!高階関数で計算パターンをプログラムする

この状況は,紙の上で行う数学の計算ばかりでなく,プログラミングでも同様である.
一般性のある計算パターンをあらかじめプログラムしておき,必用に応じて呼び出して使えれると便利である.
これは高階関数によって実現できる.

高階関数は,計算パターンの中に含まれるパラメタを引数として受け取り,それらパラメ
タを含む計算のパターンを実行する関数である.

高階関数の定義とその動作を,シグマ記法と比較しながら,関数の和の計算を
例に考えてみよう.
fを整数を受け取り整数を返す関数,nを整数値とする.
f(1)からf(n)までの和を表すシグマ記法とそれが満たす等式は以下の通りであ
る.
||!一般のシグマ表記||!満たす等式||
||[[sigma|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigmaSym.gif]]||[[sigma|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigmaf.gif]]||
このシグマ記法のパラメタは,関数fと整数nである.
これらを引数とし,シグマ記法の満たす等式をそのままプログラムとして書き
下せば,以下のような関数定義が得られる.

fun Sigma f 0 = 0
   | Sigma f n = f n + Sigma f (n - 1)

これが,種々の関数の1からnまでの値の和を計算する高階関数である.
この関数の定義に対してコンパイラは以下のような型情報を表示する.
val Sigma = fn : (int -> int) -> int -> int
この型情報に含まれる記法の意味は以下の通りである.
* 記法(int -> int) -> int -> intは,(int -> int) -> (int -> int)の括弧が省略されたものである.このようにMLでは,関数構成子"->"は括弧を付けなければ左から括弧が付いているとみなされる.たとえば,int -> int -> intはint -> (int -> int)のことである.
* int -> intは最初の引数の型であり,これは「整数型を受け取って整数型を返す関数」を意味する.

Sigmaの型情報(int -> int) -> int -> intは以下の二通りに理解できる.
# int -> intの型の引数とint型の引数をこの順に受け取って,int型の値を返す関数
# int -> intの型の引数を受け取ってint -> int型の値を返す関数

最初の見方に従えば,「整数型を受け取って整数型を返す関数」と整数をこの順に受け取り整数を返す関数である.
そこで,以下のような計算が可能である.
  # fun sq x = x * x;
  val sq = fn : int -> int
  # Sigma sq 5;
  val it = 55 : int
Sigma sq 5は[[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma5.gif]]の計算に他ならない.

2番目の見方は,Sigmaが「整数型を受け取って整数型を返す関数」を受け取って
「整数型を受け取って整数型を返す関数」を返す関数であることを意味している.
従って,以下のようなプログラムが可能となる.
# val sigma2 = Sigma sq;
val sigma2 = fn : int -> int
# sigma2 5;
val it = 55 : int
Sigma sqはnを受け取って
[[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigma2Sym.gif]]
を返す関数であるから,その結果にsigma2と名前を付ける宣言
val sigma2 = Sigma sq

[[sum|http://www.pllab.riec.tohoku.ac.jp/images/latex/sigmaFunSq.gif]]
のような関数の定義に相当する.

!よく使われるパターンを見つける(2):リストの場合

高階関数として定義すると便利なパターンは,上記のような算術演算以外の種々
のデータ構造の処理にも当然よく現れる.
これらのパターンを見つけ,それらを高階関数として表現し利用する技術をマ
スターすることが,MLプログラミング上達の一つの鍵である.

前項のリストの処理で学んだ
* doubleList
* factorialList
* toStringList
* toAsciiList
の各関数を振り返ってみよう.
fun doubleList nil = nil
   | doubleList (h::t) = h*2 :: doubleLust t

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

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

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

これらを並べて眺めてみると,いずれも以下のような構造をしていることに気づく.
fun listFun nil = nil
   | listFun (h::t) = F h :: listFun t
ここで,Fはそれぞれの処理を表現する関数であり,このパターンのパラメタである.
それ以外の部分は同一であるので,このパラメタを引数とする高階関数を以下
のように定義すれば,これら関数に共通な処理パターンを実現する関数を定義できる.
  fun map F nil = nil
    | map F (h::t) = f h :: map f t
この関数は,Sigma関数と同様に二つの引数をとる.
最初の引数は,表そうとするパターンに含まれていたパラメータである.
従って,このmap関数の最初の引数としてそれぞれfactoria,Int.toString,およ
びord関数を与えると,上記の各関数が得られるはずである.
また,Sigmaの場合と同様に,map関数にFとリストを同時に与えることもでき
る.
これらの情報は,map関数の型で表現される.

!有用な高階関数の多くは多相型を持つ

以下は,map関数に対してSML#が推論する型情報である.
val map = fn : ['a.'b. ('a -> 'b) -> 'a list -> 'b list]
Sigmaの場合と違い,この型の中には'aと'bで表される特別な型が現れている.
これらは,定義された高階関数が使用する時に自動的に必用な型に置き換えら
れる'''型変数''である.
直感的には,型 'a -> 'bは,任意の型'aと'bに対して,'aから'bへの関数を表し,'a list -> 'b listは,要素の型が'aであるリストを受け取り要素の型が'bであるリストを返す関数を表す.
また,'a listは,任意の型'aに対して,要素の型が'aであるリストの型を表す.
従って,mapの型は,Sigmaの場合と同様,以下の2つの読み方ができる.
# 任意の型'aと'bに対して,「'aを受け取り'bを返す関数」を受け取り,「要素の型が'aであるリストを受け取り要素の型が7bであるリストを返す関数」を返す関数.
# 任意の型'aと'bに対して,'aを受け取り'bを返す関数と,要素の型が'aであるリストをこの順に受け取り,要素の型が'bであるリストを返す関数.
この型情報は,mapの引数であり,mapが表現している計算パターンのパラメータである関数Fは
種々の型でよいことを意味している.
このように,種々の異なった型の引数に対して同一のパターンの計算を表現する関数を
'''多相関数'''と呼ぶ.
多相関数の型は,型変数を含む型で表現される.
mapの例のように,有用な高階関数の多くは多相関数である.

以下は実行例である.
# map fib [1,2,3,4,5,6];
val it = [1, 2, 3, 5, 8, 13] : int list
# map Int.toString; [1,2,3,4,5,6];
val it = ["1", "2", "3", "4", "5"] : string list
# map ord [#"S", #"M", #"L", #"#"];
val it = [83, 77, 76, 35] : int list
このmapを使えば上記の関数は以下のように定義できる.
# fun double x = x * 2;
val double = fn : int -> int
# fun doubleList L = map double L;
val doubleList = fn : int list  -> int list
# fun factorialList L = map factorial L;
val factorialList = fn : int list  -> int list
# fun toStringList L = map Int.toString L;
val toStringList = fn : int list  -> string list
# fun toAsciiList L = map ord L;
val toStringList = fn : char list  -> int list
以下は,mapを使って上記の関数を定義しテストしたものである.
# val factorialList = map factorial;
val factorialList = fn : int list  -> int list
# factorialList [1,2,3,4,5];
val it = [1, 2, 6, 24, 120] : int list
# val toStringList = map Int.toString;
val toStringList = fn : int list  -> string list
# toStringList [1,2,3,4,5];
val it = ["1", "2", "3", "4", "5"] : string list
# val toAsciiList = map ord;
val toAsciiList = fn : char list  -> int list
# toAsciiList [#"S", #"M", #"L", #"#"];
val it = [83, 77, 76, 35] : int list
以上の例で,mapの型の型変数'aと'bが自動的に置き換えられているこ注意.
----
[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/017]] | [[ 次ページ |Tutorial/019]] ]