SML# - Tutorial/017-2 Diff

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

[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/017-1]] | [[ 次ページ |Tutorial/018]] []
----
!以下のリスト生成関数を定義せよ.

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

----
[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/017-1]] | [[ 次ページ |Tutorial/018]] ]