SML/NJ は関数型言語なので、関数を引数として受け取る関数、いわゆる「高階関数 (higher order function) 」を簡単に定義することができます。もちろん、値として関数を返すこともできるので、関数を作る関数を定義することも簡単です。実際、関数の操作は Common Lisp よりも柔軟で簡単です。
簡単な例として、リストの要素に関数 f を適用して、その結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング（写像）」といいます。次のリストを見てください。
リスト : マッピング fun mapcar( _, nil ) = nil | mapcar( f, x::xs ) = f( x ) :: mapcar( f, xs )
SML/NJ には同じの機能を持つ関数 map が定義されているので、関数名は mapcar としました。名前は Common Lisp から拝借しました。SML/NJ の場合、受け取った関数を呼び出すとき、特別なことを行う必要はありません。SML/NJ は引数 f が関数として使われているので、引数 f を関数型と推論してコンパイルします。関数を渡す場合も簡単です。関数が束縛されている変数を渡すだけでいいのです。とても簡単ですね。
mapcar を定義すると、次のように表示されます。
val mapcar = fn : ('a -> 'b) * 'a list -> 'b list
第 1 引数が関数型 'a -> 'b で第 2 引数がリスト 'a list になります。関数 f はリストの要素を受け取るので、関数 f の引数の型とリストの型は一致します。これを型変数 'a で表しています。同様に、関数 f の返り値の型と mapcar の返り値のリストの型は一致します。これを型変数 'b で表しています。このように、mapcar は多相型関数として定義されます。
それでは簡単な実行例を示しましょう。
- fun square(x) = x * x; val square = fn : int -> int - mapcar( square, [1, 2, 3, 4, 5] ); val it = [1,4,9,16,25] : int list - mapcar( fn(x) => x * x, [1, 2, 3, 4, 5] ); val it = [1,4,9,16,25] : int list
引数を 2 乗する関数 square を定義します。この関数を mapcar に渡すと、リストの要素が 2 乗されます。また、Common Lisp のラムダ式のように、SML/NJ にも「匿名関数」があります。匿名関数は次のように定義します。
fn(args, ...) => 式
匿名関数を定義する場合、fun ではなく fn を使うことに注意してください。mapcar に fn(x) => x * x を渡せば、リストの要素を 2 乗することができます。
フィルター (filter) はリストの要素に関数 f を適用し、関数 f が真を返す要素をリストに格納して返す関数です。真または偽を返す関数のことを「述語 (predicate) 」といいます。SML/NJ には filter が定義されているので、ここでは述語が真を返す要素を削除する関数 remove_if を作ってみましょう。関数名は Common Lisp から拝借しました。
リスト : remove_if
fun remove_if( _, nil ) = nil
| remove_if( p, x::xs ) =
if p( x ) then remove_if( p, xs ) else x::remove_if( p, xs )
remove_if も簡単ですね。p( x ) が真ならば x をリストに加えず、偽ならば x をリストに加えるだけです。remove_if を定義すると次のようになります。
val remove_if = fn : ('a -> bool) * 'a list -> 'a list
関数 p が if のテストで使われているので、SML/NJ は関数 p の型を 'a -> bool と推論しています。もちろん、remove_if も多相型関数として定義されます。SML/NJ の型推論はとても便利ですね。簡単な実行例を示します。
- remove_if( fn(x) => x >= 10, [1, 10, 2, 12, 3, 13] ); val it = [1,2,3] : int list - remove_if( fn(x) => x = "abc", ["abc", "def", "abc", "ghi"] ); val it = ["def","ghi"] : string list
最初の例は述語が x >= 10 なので、10 以上の要素が削除されます。次の例は文字列 "abc" が削除されます。
関数 reduce は 2 つの引数を取る関数 f とリストを引数に取ります。そして、reduce はリストの各要素に対して関数 f を次のように適用します。
(1) [a1, a2, a3, ..., an-1, an] => f( ... f( f( a1, a2 ), a3 ), ...), an-1 ), an ) (2) [a1, a2, a3, ..., an-1, an] => f( a1, f( a2, f( a3, ..., f( an-1, an ) ... )))
関数 f を適用する順番で 2 通りの方法があります。たとえば、関数 f が単純な加算関数とすると、reduce の結果はリストの要素の和になります。
f(x, y) = x + y の場合 : reduce => a1 + a2 + a3 + ... + an-1 + an
このような操作を「縮約」とか「畳み込み」といいます。reduce は引数に初期値 g を指定する場合があります。この場合は、次のような動作になります。
(1) [a1, a2, a3, ..., an-1, an] => f( ... f( f( g, a1 ), a2 ), ...), an-1 ), an ) (2) [a1, a2, a3, ..., an-1, an] => f( a1, f( a2, f( a3, ..., f( an, g ) ... )))
SML/NJ には foldl と foldr という同等の機能を持つ関数が定義されているので、ここでは (2) の動作を行う関数 reduce を作ってみましょう。プログラムは次のようになります。
リスト : reduce fun reduce( _, g, nil ) = g | reduce( f, g, x::xs ) = f( x, reduce( f, g, xs ) )
第 1 引数 f が適用する関数、第 2 引数 g が初期値、第 3 引数がリストです。最初の定義は再帰呼び出しの停止条件ですが、reduce に空リストが与えられた場合にも対応します。この場合は初期値 g を返します。次の規則で関数 f を適用します。関数 f の引数がリストの先頭の要素 x で、第 2 引数が reduce( f, g, xs ) の返り値です。
たとえば、reduce( f, g, [a1, a2, a3] ) は次のように展開されます。
reduce( f, g, [a1, a2, a3] )
↓
f( a1, reduce( f, g, [a2, a3] ) )
↓
f( a1, f( a2, reduce( f, g, [a3] ) ) )
↓
f( a1, f( a2, f( a3, reduce( f, g, nil ) ) ) )
↓
f( a1, f( a2, f( a3, g ) ) )
図 : reduce の動作
これで reduce の (2) の動作を実現することができます。それでは、簡単な実行例を示しましょう。
val reduce = fn : ('a * 'b -> 'b) * 'b * 'a list -> 'b
- reduce( op +, 0, [1, 2, 3, 4, 5] );
val it = 15 : int
reduce の返り値は初期値 g の型と同じになります。つまり、リストの要素と同じ型である必要はありません。op は 2 項演算子を 2 引数の関数として使うためのものです。次の例を見てください。
- op +(1, 2); val it = 3 : int
2 項演算子を関数に渡す場合は op を使ってください。reduce の例では、初期値に 0 を指定することで、リストの要素の合計値を求めています。
ところで、reduce と 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。たとえば、length, map, filter などの例を示します。
(* length *) - reduce( fn(x, y) => y + 1, 0, [1, 2, 3, 4, 5] ); val it = 5 : int - reduce( fn(x, y) => y + 1, 0, ["a", "b", "c"] ); val it = 3 : int (* map *) - reduce( fn(x, y) => (x * x)::y, nil, [1, 2, 3, 4]); val it = [1,4,9,16] : int list (* filter *) - reduce( fn(x, y) => if x > 10 then x::y else y, nil, [1, 11, 2, 12, 3, 13] ); val it = [11,12,13] : int list (* count_if *) - reduce( fn(x, y) => if x > 10 then y + 1 else y, 0, [1, 11, 2, 12, 3, 13] ); val it = 3 : int
reduce の場合、関数 f の第 1 引数にリストの要素、第 2 引数に今までの計算結果が渡されます。length の場合は、初期値を 0 にして第 2 引数の値を +1 することで実現できます。map の場合は、初期値を nil にして第 1 引数の計算結果を第 2 引数のリストに追加するだけです。上の例では、リストの要素を 2 乗しています。filter の場合も初期値を nil にして、第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。最後の例は Common Lisp の関数 count-if と同じで、条件を満たしている要素の個数を数えます。
関数 print は文字列を標準出力（画面）へ出力する関数です。次の例を見てください。
- print( "hello, world\n" ); hello, world val it = () : unit
print は画面に文字列を出力する「副作用 (side effect) 」が目的の関数です。hello, world は出力結果であり、print の返り値ではありません。() が print の返り値で、これをユニット (unit) といいます。unit 型のデータは () しかなく、print のように副作用が目的の関数の返り値などで使用されます。
SML/NJ の print は文字列しか表示できないので、他のデータ型を表示するにはそれを文字列に変換する必要があります。たとえば、整数や実数は次に示す関数で変換することができます。
- Int.toString( 100 ); val it = "100" : string - Real.toString( 1.234 ); val it = "1.234" : string
SML/NJ には「ストラクチャ (structure) 」というモジュール機能があります。ストラクチャはデータ型の定義やそれを操作する関数などをまとめたものです。Int はストラクチャの名前で、この中に整数を操作する関数が定義されています。ストラクチャ内の関数を呼び出すには、ストラクチャ名と関数名をドット ( . ) でつなげます。
structure_name.function_name
関数名が同じでもストラクチャ名が異なれば、別々の関数として識別されます。Int.toString はストラクチャ Int で定義されていて、Real.toString はストラクチャ Real で定義されています。関数名は同じ toString でも、異なる関数になります。ストラクチャは SML/NJ の重要な機能なので、あとで詳しく説明します。
リストを表示する場合は高階関数を使うと便利です。つまり、副作用を伴う関数を受け取り、その関数をリストの要素に適用するのです。SML/NJ には app という高階関数が用意されていますが、私達でも簡単に作ることができます。関数名は Common Lisp から拝借して mapc としました。
リスト : mapc fun mapc( _, nil ) = () | mapc( f, x::xs ) = ( f( x ); mapc( f, xs ) )
最初の定義が空リストの場合です。mapc は関数 f の副作用が目的なので、返り値はユニットにします。副作用を伴う関数を使う場合、関数定義で複数の式を書く必要があります。mapc は要素 x に関数 f を適用してから mapc を再帰呼び出しします。SML/NJ で複数の式を書くには「複文」を使います。複文は複数の式をカッコで囲んで、式をセミコロン ( ; ) で区切ります。
複文 : ( expr1; expr2; .....; exprN )
実は、let の in ... end の部分も複文になっていて、セミコロンで区切れば複数の式を書くことができます。
それでは、簡単な実行例を示します。
- mapc( fn(x)=>print(Int.toString(x) ^ "\n"), [1,2,3,4,5] ); 1 2 3 4 5 val it = () : unit
SML/NJ の入出力は Common Lisp と同様に「ストリーム (stream) 」を介して行われます。入力ストリームを表すデータ型が instream で、出力ストリームを表すデータ型が outstream です。テキストファイルの入出力はストラクチャ TextIO にまとめられています。ファイル入出力の詳細はあとで詳しく説明するとして、ここでは標準入出力について簡単に説明します。
標準入出力に対応するストリームは TextIO 内の変数に定義されています。
print は文字列を標準出力へ出力する関数でしたが、入力ストリームから文字列を読み込む関数が inputLine です。
- TextIO.inputLine( TextIO.stdIn ); hello, world val it = "hello, world\n" : string
hello, world と入力してリターンキーを押すと、inputLine は入力データを文字列にして返します。このとき、文字列に改行文字が含まれることに注意してください。
それでは簡単な例題として、入力をそのままエコーバックする関数 echo を作ってみましょう。プログラムは次のようになります。
リスト : echo
fun echo() =
let
val x = TextIO.inputLine( TextIO.stdIn )
in
if x = "" then () else (print( x ); echo())
end
echo のように副作用が目的の関数で、引数が必要ない場合はユニット () を渡します。inputLine で標準入力から 1 行読み込み、その値を変数 x に束縛します。入力データが無い場合、inputLine は空文字列 "" を返します。Windows の場合、標準入力から Ctrl-Z を入力すると、inputLine の返り値は空文字列になります。x が空文字列であればユニットを返します。そうでなければ、print で x を画面に出力して echo を再帰呼び出しします。
簡単な実行例を示します。
val echo = fn : unit -> unit - echo(); abcd <-- 入力 abcd efgh <-- 入力 efgh hello, world <-- 入力 hello, world
echo を終了するには Ctrl-Z を入力してください。
近代的なプログラミング言語は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能を持っています。SML/NJ の場合、組を使って新しい型を表すことができますが、もうひとつ重要な方法に datatype 宣言があります。
datatype (型変数, ... 型変数) 型の名前 =
データ構成子A of 型式A
| データ構成子B of 型式B
.....
| データ構成子N of 型式N
「型式 (type expression) 」とはデータ型を表す式のことで、基本的な型である int, real, string, bool などのほかに、関数型や組を表す積型、list と組み合わせてできる int list や string list などがあります。データ構成子とは型式のデータを表す名前です。データを生成するときやパターンマッチングのときにも使用します。
もっとも簡単な datatype 宣言は、Ｃ言語などの列挙型 (enum) のように使う方法です。次の例を見てください。
- datatype fruit = Apple | Orange | Grape; datatype fruit = Apple | Grape | Orange - Apple; val it = Apple : fruit - Grape; val it = Grape : fruit - Orange; val it = Orange : fruit
SML/NJ の場合、データ構成子は英大文字で始める習慣があります。fruit というデータ型は Apple, Orange, Grape から構成されます。このあと、Apple, Orange, Grape を SML/NJ のプログラムで使うことができます。次のように fruit を組やリストに入れることもできます。
- val a = [Apple, Orange, Grape]; val a = [Apple,Orange,Grape] : fruit list - val b = (Apple, Orange); val b = (Apple,Orange) : fruit * fruit
datatype はＣ言語の共用体と同じ働きをします。たとえば、number というデータ型を定義してみましょう。次の例を見てください。
- datatype number = Int of int | Real of real; datatype number = Int of int | Real of real - Int 10; val it = Int 10 : number - Real 1.1; val it = Real 1.1 : number - [Int 1, Real 1.5, Int 2, Real 2.5]; val it = [Int 1,Real 1.5,Int 2,Real 2.5] : number list
number は数を表すデータ型で、データは整数 (int) または実数 (real) です。Int of int によりデータ構成子 Int の型は int と定義され、Real of real でデータ構成子 Real の型は real と定義されます。
データ型 number の生成はデータ構成子を使います。Int 10 または Real 1.1 で number 型のデータが生成されます。Int( 10 ) や Real( 1.1 ) のようにカッコで囲んでもかまいません。最後の例のように、number 型のデータをリストに格納することができます。このように新しいデータ型 number を定義することで、整数と実数をいっしょにリストに格納することができます。
データ構成子は「パターン」として使うことができます。たとえば、number list の整数の合計値と実数の合計値を求める関数 number_sum を作ってみましょう。次のリストを見てください。
リスト : 整数と実数の合計値を別々に求める
fun number_sum( num_list ) =
let
fun sum( nil, i, r ) = (i, r)
| sum( Int( x )::xs, i, r ) = sum( xs, i + x, r )
| sum( Real( x )::xs, i, r ) = sum( xs, i, r + x )
in
sum( num_list, 0, 0.0 )
end
number_sum は整数と実数の合計を求め、組 (int * real) にして返します。実際の処理は関数 sum で行います。sum の第 2, 3 引数を累算変数として使い、第 2 引数に整数の合計値、第 3 引数に実数の合計値を求めます。Int( x )::xs と Real( x )::xs がパターンです。リストの先頭の要素が Int の場合、2 番目の定義とマッチングして、x の値は整数になります。要素が Real の場合は 3 番目の定義とマッチングして、x の値は実数になります。Int( x )::xs と Real( x )::xs は、Int x ::xs と Real x ::xs としてもかまいません。
それでは実行例を示します。
val number_sum = fn : number list -> int * real - number_sum( [Int 10, Int 11, Real 2.5, Int 12, Real 3.1, Real 4.2] ); val it = (33,9.8) : int * real
型変数を使うと 'a list のような多相的なデータ型を作ることができます。簡単な例として、SML/NJ に定義されている option 型をみてみましょう。option の定義を示します。
datatype 'a option = NONE | SOME of 'a
型変数は datatype と名前の間に指定します。複数の型変数を使う場合は ('a, 'b, ... 'n) のように、型変数をカッコで囲んでカンマで区切ります。option はデータの有無を表す型です。データが無い場合は NONE を、データが有る場合は SOME を使います。SOME の型式は 'a なので、どのデータ型でも option に格納することができます。次の例を見てください。
- NONE; val it = NONE : 'a option - SOME 10; val it = SOME 10 : int option - SOME "foo"; val it = SOME "foo" : string option
NONE だけではデータ型を定めることができないので、型は 'a option と表示されます。SOME 10 の場合、与えられたデータ型が int なので int option になります。同様に、SOME "foo" の型は string option になります。
たとえば、リストからデータを探索する処理を考えてみましょう。「リストの探索」で作成した関数 member は、データが見つかれば残りのリストを、見つからなければ空リスト (nil) を返すように作りました。見つけたデータをそのまま返さないのは、データが見つからない場合の返り値 (nil) とデータ型を一致させるためです。SML/NJ はデータ型を厳密にチェックするプログラミング言語なので、異なるデータ型を返すことはできないのです。
このような場合、役に立つのが option です。見つけたデータをそのまま返さずに、option に格納して返せばいいわけです。簡単な例として、リストの中から述語を満たす要素を探す関数 find_if を作ってみましょう。SML/NJ には find という同じ機能を持つ関数が用意されていますが、私達でも簡単に作ることができます。ちなみに、関数名は Common Lisp (find-if) から拝借しました。
リスト : リストの探索
fun find_if( _, nil ) = NONE
| find_if( p, x::xs ) =
if p( x ) then SOME x else find_if( p, xs )
最初の定義で、データが見つからない場合は NONE を返します。次の定義で、述語 p( x ) が真を返せば SOME x を返します。そうでなければ、find_if を再帰呼び出しして次の要素を調べます。
それでは、簡単な実行例を示します。
val find_if = fn : ('a -> bool) * 'a list -> 'a option
- val a = find_if( fn(x) => x >= 10, [1, 2, 11, 12, 3, 4] ); val a = SOME 11 : int option - val b = find_if( fn(x) => x >= 10, [1, 2, 3, 4, 5, 6] ); val b = NONE : int option - isSome a; val it = true : bool - isSome b; val it = false : bool - getOpt( a, 0 ); val it = 11 : int - getOpt( b, 0 ); val it = 0 : int - valOf a; val it = 11 : int - valOf b; uncaught exception Option
データが見つからない場合は NONE を返しますが、リストの要素が int なので NONE のデータ型も int option になります。ここで、option 型を操作する主な関数を紹介しましょう。
val getOpt : 'a option * 'a -> 'a val isSome : 'a option -> bool val valOf : 'a option -> 'a
関数 isSome は option 型のデータの有無をチェックする関数です。データがあれば true を、無ければ false を返します。getOpt は option 型からデータを取り出す関数です。データがあればその値を返し、無ければ第 2 引数を返します。valOf もデータを取り出す関数ですが、データが無い場合は「例外 (exception)」を送出します。例外はあとで詳しく説明します。もちろん、パターンマッチングを使ってデータを取り出すこともできます。
datatype は再帰的なデータ構造も定義することができます。たとえば、連結リスト (linkedlist) は次のように定義できます。
datatype 'a linkedlist = Nil | Cell of 'a * 'a linkedlist
Nil が連結リストの終端を表し、Cell がコンスセルを表します。積型 'a * 'a linkedlist で、最初の要素が格納するデータになり、2 番目の要素が次の Cell を格納するデータになります。これで SML/NJ のリストと同等の多相的なデータ型になります。次の例を見てください。
- datatype 'a linkedlist = Nil | Cell of 'a * 'a linkedlist; datatype 'a linkedlist = Cell of 'a * 'a linkedlist | Nil - val a = Cell( 1, Nil ); val a = Cell (1,Nil) : int linkedlist - val b = Cell( 2, a ); val b = Cell (2,Cell (1,Nil)) : int linkedlist - val c = Cell( 10, Cell( 11, Cell( 12, Nil ) ) ); val c = Cell (10,Cell (11,Cell #)) : int linkedlist
このように、Cell を使って linkedlist を組み立てることができます。ようするに、データ構成子 Cell が list のコンス演算子と同じ働きをしているわけです。実際、SML/NJ の list は次のように定義されています。
datatype 'a list = :: of 'a * 'a list | nil
これで多相的なリスト構造を実現できるのですから、SML/NJ の型システムは柔軟で強力な機能だと思います。
それでは簡単な例題として、「連想リスト (association list : a-list) 」を作ってみましょう。連想リストは Lisp でよく用いられるデータ構造で、SML/NJ ではキーとデータの組を要素とするリストで実現できます。データ型で記述すると ('a, 'b) list になり、'a がキーで 'b がデータに対応するデータになります。次の図を見てください。
┌────┬────┬────┬──→ データ
│ │ │ │
連想リスト => [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
│ │ │ │
└────┴────┴────┴──→ キー
図 : 連想リストの構造
上図の場合、文字列 "a", "b", "c", "d" がキーで、整数 1, 2, 3, 4 がデータとなります。一般に、キーは等値型のデータが用いられますが、データは何でもかまいません。SML/NJ では連想リストのことを ListPair といい、連想リストを操作する関数がストラクチャ ListPair に定義されています。
今回は SML/NJ の学習ということで、あえて「連想リスト」を表すデータ型とその操作関数を作成してみましょう。最初に datatype でデータ型を定義します。
リスト : 連想リストの定義
datatype ('a, 'b) alist =
Nil | Cell of 'a * 'b * ('a, 'b) alist
名前は alist にしたので、型は ('a, 'b) alist になります。Nil が空の連想リストを表します。Cell の内部では 'a と 'b を組 ('a * 'b) にする必要はないので、Cell の型式は 'a * 'b * ('a, 'b) list としました。
最初に連想リストを生成する関数を作りましょう。関数名は Common Lisp から拝借しました。次のリストを見てください。
リスト : 連想リストの生成 fun acons( x, y, alist ) = Cell( x, y, alist ) fun pairlis( nil, _ ) = Nil | pairlis( _, nil ) = Nil | pairlis( x::xs, y::ys ) = Cell( x, y, pairlis( xs, ys ) )
関数 acons はキー x とデータ y と連想リスト alist を受け取り、alist の先頭に x と y を追加します。これは簡単ですね。関数 pairlis は 2 つのリストを受け取り、第 1 引数のリストの要素がキー、第 2 引数のリストの要素がデータとなる連想リストを生成します。引数のリストの長さが違う場合は短い方に合わせます。最初の定義が第 1 引数のリストが空になった場合で、次の定義が第 2 引数のリストが空になった場合です。最後の定義で Cell を生成して x と y を格納します。
次はデータを探索する関数を作ります。関数 assoc は指定したキーと等しいデータを探します。関数 assoc_if は述語が真となるキーを探します。どちらの関数も、見つけたキーとデータを組にして option 型に格納して返します。見つからない場合は NONE を返します。
リスト : 連想リストの探索
fun assoc( _, Nil ) = NONE
| assoc( x, Cell( a, b, next ) ) =
if x = a then SOME (a, b) else assoc( x, next )
fun assoc_if( _, Nil ) = NONE
| assoc_if( f, Cell( a, b, next ) ) =
if f( a ) then SOME (a, b) else assoc_if( f, next )
どちらの関数もパターンマッチングで Cell 内のデータを取り出しています。a がキーで、b がデータ、next が次の Cell です。連想リストが空 (Nil) の場合は option 型の NONE を返します。assoc は引数 x とキー a を比較して、等しければ SOME (a, b) を返します。assoc_if は f( a ) の評価結果が真であれば SOME (a, b) を返します。
それでは、簡単な実行例を示します。
val acons = fn : 'a * 'b * ('a,'b) alist -> ('a,'b) alist
val pairlis = fn : 'a list * 'b list -> ('a,'b) alist
val assoc = fn : ''a * (''a,'b) alist -> (''a * 'b) option
val assoc_if = fn : ('a -> bool) * ('a,'b) alist -> ('a * 'b) option
- val a = acons( 1, 10, Nil ); val a = Cell (1,10,Nil) : (int,int) alist - val b = acons( 2, 12, a ); val b = Cell (2,12,Cell (1,10,Nil)) : (int,int) alist - val c = pairlis( [1, 2, 3, 4, 5], [11, 12, 13, 14, 15] ); val c = Cell (1,11,Cell (2,12,Cell #)) : (int,int) alist - assoc( 4, c ); val it = SOME (4,14) : (int * int) option - assoc_if( fn(x) => x mod 2 = 0, c ); val it = SOME (2,12) : (int * int) option
正常に動作していますね。
ここでちょっと寄り道をして、素数を求めるプログラムを作ってみましょう。いちばん簡単な方法は、奇数 3, 5, 7, 9, ... をそれまでに見つけた素数で割ってみることです。素数はリストに格納しておけばいいでしょう。このとき、素数を全部チェックする必要はありません。実は、√n よりも小さい素数を調べるだけで、n が素数か判定することができます。
プログラムは次のようになります。
リスト : 素数を求める
(* 素数の判定 *)
fun prime_p( n, nil ) = true
| prime_p( n, x::xs ) =
if x * x > n then true (* 修正 2009/06/??)
else if n mod x = 0 then false
else prime_p( n, xs );
(* 素数のリストを返す *)
fun prime_sub( n, m, l ) =
if( n < m ) then l (* 修正 2009/06/??)
else if prime_p( m, l ) then prime_sub( n, m + 2, l @ [m] )
else prime_sub( n, m + 2, l )
(* 素数を求める *)
fun prime( n ) = 2 :: prime_sub( n, 3, nil )
関数 prime( n ) は n 以下の素数をリストに格納して返します。実際の処理は関数 prime_sub で行います。第 1 引数 n が上限値、第 2 引数 m がチェックする整数、第 3 引数 l が素数のリストです。奇数だけチェックすればいいので、m の初期値は 3 とし、値を +2 ずつしていきます。素数のリストは nil に初期化し、prime_sub の返り値に 2 を追加します。prime_sub は n < m になったら再帰呼び出しを終了し、素数のリスト l を返します。そうでなければ、関数 prime_p で m が素数かチェックします。そうであれば、l @ [m] で素数のリストの最後に m を追加します。
素数を判定する prime_p は簡単です。第 1 引数 n がチェックする整数で、第 2 引数が素数のリストです。最初の定義が空リストの場合です。次の定義でリストを分解し、n が x で割り切れるかチェックします。x > √n のチェックを x * x > n で行っていることに注意してください。そうであれば、n は素数なので true を返します。n mod x = 0 ならば、n は素数ではないので false を返します。それ以外の場合は prime_p を再帰呼び出しして、次の素数を調べます。
それでは実行してみましょう。
val prime = fn : int -> int list - val a = prime( 100 ); val a = [2,3,5,7,11,13,17,19,23,29,31,37,...] : int list - app (fn(x)=>print(Int.toString(x)^" ")) a; 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 val it = () : unit
100 以下の素数は全部で 25 個あります。app は SML/NJ に用意されている関数で、簡単な入出力 で作成した mapc と同じ働きをします。app は「カリー化関数」のところで説明します。