[ML] 演習の解答例:リストと多相関数

以下のリスト生成関数を定義せよ.

1. nから1までの自然数のリストを返す関数まず動作を再帰的に考える.

  • downFromN 0 は空リスト
  • downFromN n はdownFromN nの先頭にnを付け加えたもの.

この動作は,ほぼそのまま以下の様にコードできる.

fun downFromN 0 = nil
  | downFromN n = n :: downFromN (n - 1);

2. 1からnまでの自然数のリストを返す関数動作を再帰的に考える.

  • uptoN 0 は空リスト
  • uptoN n はuptoN (n - 1)の後ろにnを付け加えたもの.

そこで,リストの連結演算子を使えば以下の様にコードできる.

fun untoN 0 = nil
  | untoN n =  untoN (n - 1) @ [n]

しかし,リストの連結演算L1 @ L2は,これから学ぶとおりL1に関して再帰的にリストをたどる処理であり,効率がわるい.そこで,この問題を以下のように分析し直す.

  • リストは再帰を使って後ろから作成していく.
  • そこで,[j, ..., n]なるリストをj = n, n-1,...1までのループで作成することを考える.
    • 計算の途中結果を持つ変数をL,ループの回数を持つ変数をiとする.
    • 初期状態:L = nil (i = n)
    • 途中状態:L = [i, ..., n] (n > i > 0)
    • 最終状態:i = 0

以前学んだMLでのループの考え方を適用すれば,以下のようなコードを得る.

fun uptoN n =
  let
    fun loop (0,L) = L
      | loop (i,L) = loop(i - 1, i::L)
  in
    loop(n,nil)
  end

3. nからn+k-1までの自然数のリストを返す関数以下のように再帰的に考える.

  • fromNtoK (n,0)は空リスト
  • fromNtoK (n,k)は,fromNtoK (n + 1,k)の先頭にnを加えればよい,

これは,以下の様にコードできる.

fun fromNtoK (n,0) = nil
  | fromNtoK (n,k) = n :: fromNtoK (n + 1, k - 1);

4. 1からkまでの繰り返すn個の自然数のリストを返す関数この関数は,uptoN関数の各ループで,先頭に加える数を適当な数に代えることで実現できる.k=4の場合,以下のように考えることができる.

もとの数列(i)1 2 3 4 5 6 7 8
1引いた数(i - 1)0 1 2 3 4 5 6 7
4で割ったあまり((i - 1) mod 4)0 1 2 3 0 1 2 3
1を足した数((i - 1) mod 4 + 1)1 2 3 4 1 2 3 4

そこで,以下のようにコードできる.

fun KcycleUptoN (k,n) =
  let
    fun loop (0,L) = L
      | loop (i,L) = loop(i - 1,  (((i - 1) mod k) + 1)::L)
  in
    loop(n,nil)
  end

5. 文字cから順にn個の文字のリストを返す関数続く...

以下のリスト処理関数を定義せよ.

1. 整数のリストの要素の積を計算する関数:prodList.

fun prodList nil = 1
  | prodList (h::t) = h * prodList t

2. リストを要素の組みのリストに変換する関数pariList.

fun pairList nil = nil
  | pairList (h::t) = (h,h) :: pairList t

3. リストのリストを1段階のリストに変換する関数flatten.

fun flatten nil = nil
  | flatten (h::t) = h @ faltten t

4. 文字列のリストを受け取り,それら文字を連結して得られる文字列を返す関数:implodeString.

fun implodeString nil = ""
  | implodeString (h::t) = h ^ implodeString t

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

Last modified:2007/08/04 15:11:11
Keyword(s):
References:[(18−1)[ML] 演習:リスト]