Yet Another Scala Problems

はじめに

このページは M.Hiroi が Scala の勉強で作成した簡単なプログラムをまとめたものです。元ネタは P-99: Ninety-Nine Prolog Problems で、拙作のページ Yet Another Prolog Problems や Yet Another Scheme Problems などの Scala バージョンになります。同じような問題が多くなると思いますが、あしからずご了承くださいませ。

●問題１

整数 n から m までの和、二乗の和、三乗の和を求める関数 sumOfInt, sumOfSquare, sumOfCube を定義してください。

def sumOfInt(n: Int, m: Int): BigInt
def sumOfSquare(n: Int, m: Int): BigInt
def sumOfCube(n: Int, m: Int): BigInt

scala> sumOfInt(1, 1000)
val res0: BigInt = 500500

scala> sumOfSquare(1, 1000)
val res1: BigInt = 333833500

scala> sumOfCube(1, 1000)
val res2: BigInt = 250500250000

解答

●問題２

点を多角形の形に並べたとき、その総数を「多角数 (polygonal number) 」といいます。三角形に配置したものを三角数、四角形に配置したものを四角数、五角形に配置したものを五角数といいます。三角数、四角数、五角数を下図に示します。

n 番目の p 角数を求める関数 polygonalNum を定義してください。

def polygonalNum(p : Int, n: Int) Int

scala> polygonalNum(3, 1)
val res0: Int = 1

scala> polygonalNum(3, 2)
val res1: Int = 3

scala> polygonalNum(3, 3)
val res2: Int = 6

scala> polygonalNum(4, 1)
val res3: Int = 1

scala> polygonalNum(4, 2)
val res4: Int = 4

scala> polygonalNum(4, 3)
val res5: Int = 9

scala> polygonalNum(5, 1)
val res6: Int = 1

scala> polygonalNum(5, 2)
val res7: Int = 5

scala> polygonalNum(5, 3)
val res8: Int = 12

解答

●問題３

次の公式を使って平方根の整数部分を求める関数 sqrtInt を定義してください。

(1) 1 + 3 + 5 + ... + (2n - 1) = n²
(2) 1 + 3 + 5 + ... + (2n - 1) = n² < m < 1 + 3 + ... (2n - 1) + (2n + 1) = (n + 1)²

式 (1) は、奇数 1 から 2n - 1 の総和は n² になることを表しています。式 (2) のように、整数 m の値が n² より大きくて (n + 1)² より小さいのであれば、m の平方根の整数部分は n であることがわかります。これは m から奇数 1, 3, 5 ... (2n - 1), (2n + 1) を順番に引き算していき、引き算できなくなった時点の (2n + 1) / 2 = n が m の平方根になります。参考文献によると、この方法を「めのこ平方」と呼ぶそうです。

def sqrtInt(n: Int) Int

scala> sqrtInt(100)
val res0: Int = 10

scala> sqrtInt(1000)
val res1: Int = 31

scala> sqrtInt(10000)
val res2: Int = 100

scala> sqrtInt(123456789)
val res3: Int = 11111

-- 参考文献 --------
[1] 仙波一郎のページ, 『平方根計算法 (PDF)』

解答

●問題４

実数 a の平方根 √a の値を Newton (ニュートン) 法で求めてください。

def sqrt(n: Double): Double

scala> sqrt(2)
val res0: Double = 1.414213562373095

scala> sqrt(3)
val res1: Double = 1.7320508075688772

scala> sqrt(4)
val res2: Double = 2.0

scala> sqrt(123456789)
val res3: Double = 11111.111060555555

方程式を f(x), その導関数を f'(x) とすると、ニュートン法は次の漸化式の値が収束するまで繰り返す方法です。

x_n+1 = x_n - f(x_n) / f'(x_n)

平方根を求める場合、導関数は f'(x) = 2x になるので、漸化式は次のようになります。

x_n+1 = (x_n + a / x_n) / 2

参考文献によると、√a より大きめの初期値から出発し、置き換え x <- (x + a / x) / 2 を減少が止まるまで繰り返すことで √a の正確な値を求めることができるそうです。

-- [参考文献] --------
[1] 奥村晴彦,『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991

解答

●問題５

リスト xs の中から最小値を求める関数 minimum と最大値を求める関数 maximum を定義してください。

def minimum[A](xs: List[A])(implicit f: A => Ordered[A]): A
def maximum[A](xs: List[A])(implicit f: A => Ordered[A]): A

scala> maximum(List(1, 2, 3, 4, 5, 6, 7, 8))
val res0: Int = 8

scala> minimum(List(1, 2, 3, 4, 5, 6, 7, 8))
val res1: Int = 1

scala> maximum(List(1.1, 2.2, 3.3, 4.4))
val res2: Double = 4.4

scala> minimum(List(1.1, 2.2, 3.3, 4.4))
val res3: Double = 1.1

解答

●問題６

リスト xs の中から x と等しい要素をひとつ削除する関数 remove と述語 f が真を返す要素をひとつ削除する関数 removeIf を定義してください。

def remove[A](x: A, xs: List[A]): List[A]
def removeIf[A](f: A => Boolean, xs: List[A]): List[A]

scala> remove(2, List(1, 2, 3, 1, 2, 3))
val res0: List[Int] = List(1, 3, 1, 2, 3)

scala> removeIf((x:Int) => x > 4, List(1, 2, 3, 4, 5, 6))
val res1: List[Int] = List(1, 2, 3, 4, 6)

解答

●問題７

リスト xs から重複要素を取り除く関数 distinct, リストを集合とみなして、集合の和を求める関数 union, 集合の積を求める関数 intersection, 集合の差を求める関数 difference を定義してください。

def distinct[A](xs: List[A]): List[A]
def union[A](xs: List[A], ys: List[A]): List[A]
def intersection[A](xs: List[A], ys: List[A]): List[A]
def difference[A](xs: List[A], ys: List[A]): List[A]

scala> distinct(List(1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5))
val res0: List[Int] = List(1, 2, 3, 4, 5)

scala> union(List(1, 2, 3, 4), List(3, 4, 5, 6))
val res1: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> intersection(List(1, 2, 3, 4), List(3, 4, 5, 6))
val res2: List[Int] = List(3, 4)

scala> difference(List(1, 2, 3, 4), List(3, 4, 5, 6))
val res3: List[Int] = List(1, 2)

解答

●問題８

2 つのリスト xs, ys を受け取り、同じ位置にある要素をタプルにまとめ、それをリストに格納して返す関数 zip, zip したリストを元に戻す関数 unzip, 連想リスト xs からキー x とその値を探索する関数 assoc, 連想リスト xs から述語 f が真を返すキーと値を求める関数 assocIf を定義してください。

def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)]
def unzip[A, B](xs: List[(A, B)]): (List[A], List[B])
def assoc[A, B](x: A, xs: List[(A, B)]): Option[(A, B)]
def assocIf[A, B](f: A => Boolean, xs: List[(A, B)]): Option[(A, B)]

scala> val a = zip(List("a", "b", "c", "d"), List(1, 2, 3, 4))
val a: List[(String, Int)] = List((a,1), (b,2), (c,3), (d,4))

scala> unzip(a)
val res0: (List[String], List[Int]) = (List(a, b, c, d),List(1, 2, 3, 4))

scala> assoc("a", a)
val res1: Option[(String, Int)] = Some((a,1))

scala> assoc("d", a)
val res2: Option[(String, Int)] = Some((d,4))

scala> assoc("e", a)
val res3: Option[(String, Int)] = None

scala> assocIf((_: String) > "c", a)
val res4: Option[(String, Int)] = Some((d,4))

解答

●問題９

選択ソート (selection sort) は、ソートしていないデータの中から最小値（または最大値）を見つけ、それを先頭のデータと交換する、という手順を繰り返すことでソートを行います。最初は、すべてのデータの中から最小値を探し、それを配列の先頭 buff[0] と交換します。次は、buff[1] 以降のデータの中から最小値を探し、それを buff[1] と交換します。これを繰り返すことでソートすることができます。

 [9 5 3 7 6 4 8]   3 と 9 を交換する
  +   +

 3 [5 9 7 6 4 8]   5 と 4 を交換する
    +       +

 3 4 [9 7 6 5 8]   9 と 5 を交換する
      +     +

 3 4 5 [7 6 9 8]   7 と 6 を交換する
        + +

 3 4 5 6 [7 9 8]   7 と 7 を交換する
          +

 3 4 5 6 7 [9 8]   9 と 8 を交換してソート終了
            + +


        図 : 選択ソート

配列 buff を選択ソートする関数 selectSort を定義してください。

def selectSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit

scala> val a = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0)
val a: Array[Int] = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0)

scala> selectSort(a)

scala> a
val res0: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

解答

●問題10

リスト xs を選択ソートする関数 selectSortList を定義してください。

def selectSortList[A](xs: Array[A])(implicit f: A => Ordered[A]): Unit

scala> selectSortList(List(5, 6, 4, 7, 2, 3, 8, 9, 1, 0))
val res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> selectSortList(List(5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 0, 0))
val res1: List[Int] = List(0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5)

解答

●解答１

整数の和、二乗の和、三乗の和は、高階関数 sumOf を定義すると簡単です。

リスト : 整数の和、二乗の和、三乗の和

  // 二乗
  def square(n: BigInt): BigInt = n * n

  // 三乗
  def cube(n: BigInt): BigInt = n * n * n

  // 高階関数
  def sumOf(f: BigInt => BigInt)(n: Int, m: Int, a: BigInt = 0): BigInt =
    if (n > m) a
    else sumOf(f)(n + 1, m, a + f(n))

  // 整数の和
  def sumOfInt(n: Int, m: Int): BigInt =  sumOf(identity)(n, m)

  // 二乗の和
  def sumOfSquare(n: Int, m: Int): BigInt = sumOf(square)(n, m)

  // 三乗の和
  def sumOfCube(n: Int, m: Int): BigInt = sumOf(cube)(n, m)

関数 sumOf は n から m までの整数に関数 f を適用して、その結果の総和を求めます。sumOf に恒等関数 identity を渡せば整数の和を、square を渡せば二乗の和を、cube を渡せば三乗の和を求めることができます。

sumOf は末尾再帰でプログラムしていますが、次のように n から m までの数列を生成して、メソッド map と sum で解を求めることもできます。

リスト : 関数 sumOf の別解

  def sumOf1(f: BigInt => BigInt)(n: Int, m: Int): BigInt =
    (BigInt(n) to m).map(f).sum

ところで、数列の和を求める公式を使うと、プログラムはもっと簡単になります。

1 + 2 + 3 + ... + n = n(n+1)/ 2
1 + 2² + 3² + ... + n² = n(n+1)(2n+1)/6
1 + 2³ + 3³ + ... + n³ = n²(n+1)²/4

リスト : 別解

  def sumOfInt1(n: Int, m: Int): BigInt = {
    def f(x: BigInt): BigInt = x * (x + 1) / 2
    f(m) - f(n - 1)
  }

  def sumOfSquare1(n: Int, m: Int): BigInt = {
    def f(x: BigInt): BigInt = x * (x + 1) * (2 * x + 1) / 6
    f(m) - f(n - 1)
  }

  def sumOfCube1(n: Int, m: Int): BigInt = {
    def f(x: BigInt): BigInt = x * x * (x + 1) * (x + 1) / 4
    f(m) - f(n - 1)
  }

局所関数 f が公式を表しています。あとは f(m) から f(n - 1) を引き算すれば解を求めることができます。

●解答２

多角数の点の増分を表に示すと、次のようになります。

 n   三角数            四角数             五角数
---+-----------------------------------------------------------
 1 |  1                 1                  1
 2 |  3 = 1+2           4 = 1+3            5 = 1+4
 3 |  6 = 1+2+3         9 = 1+3+5         12 = 1+4+7
 4 | 10 = 1+2+3+4      16 = 1+3+5+7       22 = 1+4+7+10
 5 | 15 = 1+2+3+4+5    25 = 1+3+5+7+9     35 = 1+4+7+10+13
 6 | 21 = 1+2+3+4+5+6  36 = 1+3+5+7+9+11  51 = 1+4+7+10+13+16

      ・・・・・・      ・・・・・・・     ・・・・・

 n | n(n + 1) / 2      n^2                n(3n - 1) / 2

表を見ればお分かりのように、三角数は公差 1、四角数は公差 2、五角数は公差 3、p 角数は公差 p - 2 の等差数列の和になります。初項を a, 公差を d とすると、等差数列の和 S_n は次式で求めることができます。

S_n = n(2a + (n - 1)d) / 2

a = 1, d = p - 2 を代入して計算すると、多角数 P_p,n は次式で求めることができます。

P_p,n = ((p - 2)n^2 - (p - 4)n) / 2

この式を Scala でプログラムすると、次のようになります。

リスト : 多角数

  def polygonalNum(p: Int, n: Int): Int =
   ((p - 2) * n * n - (p - 4) * n) / 2

簡単な実行例を示します。

scala> for (p <- 3 to 8) {
     | for (n <- 1 to 20) {
     | print(s"${polygonalNum(p, n)} ")
     | }
     | println("")
     | }
1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400
1 5 12 22 35 51 70 92 117 145 176 210 247 287 330 376 425 477 532 590
1 6 15 28 45 66 91 120 153 190 231 276 325 378 435 496 561 630 703 780
1 7 18 34 55 81 112 148 189 235 286 342 403 469 540 616 697 783 874 970
1 8 21 40 65 96 133 176 225 280 341 408 481 560 645 736 833 936 1045 1160

p 角数の初項は 1 で、第 2 項は p になります。多角数 - Wikipedia によると、多角数にはいろいろな面白い性質があるようです。

●解答３

リスト : めのこ平方

  def sqrtInt(n: Int, m: Int = 1): Int = 
    if (n < m) m / 2 else sqrtInt(n - m, m + 2)

アルゴリズムをそのままプログラムしただけなので、とくに難しいところは無いと思います。この方法はとても簡単ですが、数が大きくなると時間がかかるようになります。そこで、整数を 2 桁ずつ分けて計算していくことにします。次の図を見てください。

整数 6789 を 67 と 89 に分ける

1 + 3 + ... + 15 = 8² < 67

両辺を 100 倍すると 80² < 6700 < 6789

80² = 1 + 3 + ... + 159 (= 2 * 80 - 1)

161 + 163 < (6789 - 6400 = 389) < 161 + 163 + 165

整数 6789 を 67 と 89 に分けます。最初に 67 の平方根を求めます。この場合は 8 になり、8² < 67 を満たします。次に、この式を 100 倍します。すると、80² < 6700 になり、6700 に 89 を足した 6789 も 80² より大きくなります。80² は 1 から 159 までの奇数の総和であることはすぐにわかるので、6789 - 6400 = 389 から奇数 161, 163, ... を順番に引き算していけば 6789 の平方根を求めることができます。

プログラムは次のようになります。

リスト : めのこ平方 (改良版)

  def sqrtInt1(n: Int): Int =
    if (n < 100)
      sqrtInt(n)
    else {
      val m = 10 * sqrtInt1(n / 100)
      sqrtInt(n - m * m, 2 * m + 1)
    }

sqrtInt1 は n の平方根の整数部分を求めます。n が 100 未満の場合は sqrtInt で平方根を求めます。これが再帰呼び出しの停止条件になります。n が 100 以上の場合は、n の下位 2 桁を取り除いた値 (n / 100) の平方根を sqrtInt1 で求め、その値を 10 倍して変数 m にセットします。そして、sqrInt で n - m * m から奇数 2 * m + 1, 2 * m + 3 ... を順番に引き算していって n の平方根を求めます。

●解答４

リスト : 平方根を求める

  def sqrt(n: Double): Double = {
    def init(s: Double, x: Double): Double =
      if (s >= x) s
      else init(s * 2, x / 2)

    def iter(p: Double): Double = {
      val q = (p + n / p) / 2
      if (q >= p) p else iter(q) 
    }

    if (n < 0) throw new Exception("sqrt: domain error")
    else if (n == 0) 0
    else iter(if (n > 1) init(1, n) else 1)
  }

局所関数 init は √x よりも大きめの初期値を求めます。たとえば、√123456 を求める場合、初期値の計算は次のようになります。

   s         x
-------------------
  1.0  123456.0
  2.0   61728.0
  4.0   30864.0
  8.0   15432.0
 16.0    7716.0
 32.0    3858.0
 64.0    1929.0
128.0     964.5
256.0     482.25
512.0     241.125

√123456 = 351.363060095964

s を 2 倍、x を 1 / 2 していき、s >= x となったときの s が初期値 (512) となります。4, 16, 64, 256, ... 2²ⁿ の平方根はこれだけで求めることができます。

あとは漸化式を計算して変数 q にセットし、q がひとつ前の値 p 以上になったら p を返すだけです。√123456 を求めたときの p と q の値を示します。

   p                  q
--------------------------------------
512.0              376.5625
376.5625           352.20622925311204
352.20622925311204 351.3640693544162
351.3640693544162  351.3630600974135
351.3630600974135  351.363060095964
351.363060095964   351.363060095964

√123456 = 351.363060095964

6 回の繰り返しで √123456 を求めることができます。

●解答５

リスト : 最小値と最大値

  def minimum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
    def min(xs: List[A], a: A): A =
      xs match {
        case Nil => a
        case y::ys => if (y < a) min(ys, y) else min(ys, a)
      }
    //
    min(xs.tail, xs.head)
  }

  def maximum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
    def max(xs: List[A], a: A): A =
      xs match {
        case Nil => a
        case y::ys => if (y > a) max(ys, y) else max(ys, a)
      }
    //
    max(xs.tail, xs.head)
  }

  // 別解
  def minimum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
    xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x < a) x else a)

  def maximum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
    xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x > a) x else a)

実際の処理は局所関数 max, min で行います。どちらの関数も再帰呼び出しで最大値 (最小値) を求めます。第 2 引数 a に最大値 (最小値) を格納します。最初は先頭要素 x.head が初期値になります。あとは、残りのリスト xs.tail の要素と a を比較して、a よりも大きい (小さい) 要素 y が見つかれば、a の値を y に置き換えます。別解はメソッド foldLeft で書き直したものです。

●解答６

リスト : 要素の削除

  def remove[A](x: A, xs: List[A]): List[A] = 
    xs match {
      case Nil => Nil
      case y::ys => if (x == y) ys else y :: remove(x, ys)
    }

  def removeIf[A](f: A => Boolean, xs: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case y::ys => if (f(y)) ys else y :: removeIf(f, ys)
    }

remove と removeIf は最初に見つけた要素だけを削除します。remove の場合、x と要素 y が等しければ、残りのリスト ys を返します。removeIf の場合は、f(y) が真を返したら残りのリスト ys を返します。これで y だけを削除することができます。

●解答７

リスト : 集合演算

  def distinct[A](xs: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case y::ys => if (ys contains y) distinct(ys) else y::distinct(ys)
    }

  def union[A](xs: List[A], ys: List[A]): List[A] =
    xs match {
      case Nil => ys
      case (x::xs1) => if (ys contains x) union(xs1, ys) else x::union(xs1, ys)
    }

  def intersection[A](xs: List[A], ys: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case (x::xs1) => if (ys contains x) x::intersection(xs1, ys) else intersection(xs1, ys)
    }

  def difference[A](xs: List[A], ys: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case (x::xs1) => if (ys contains x) difference(xs1, ys) else x::difference(xs1, ys)
    }

  // 別解
  def distinct1[A](xs: List[A]): List[A] =
    xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (a contains x) a else x::a)

  def union1[A](xs: List[A], ys: List[A]): List[A] =
    xs.foldLeft(ys)((a: List[A], x: A) => if (a contains x) a else x::a)

  def intersection1[A](xs: List[A], ys: List[A]): List[A] =
    xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) x::a else a)

  def difference1[A](xs: List[A], ys: List[A]): List[A] =
    xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) a else x::a)

distinct はリストを分解して、先頭要素 y が残りのリスト ys に含まれていなければ、distinct(ys) の返り値に y を追加します。そうでなければ y を追加しません。union は xs が空リストになったら ys を返します。次に、リスト xs を x::xs1 に分解して、x が ys に含まれていなければ、union(xs1, ys) の返り値に x を追加します。そうでなければ x を追加しません。

intersection は xs が空リストになったら Nil を返します。次に、xs を x::xs1 に分解して、x が ys に含まれていれば、intersection(xs1, ys) の返り値に x を追加します。そうでなければ x を追加しません。difference は intersection とは逆に、x が ys に含まれていなければ、difference(xs1, ys) の返り値に x を追加します。

別解はメソッド foldLeft で書き直したものです。簡単な実行例を示します。

scala> distinct1(List(1,2,3,1,2,3,4,1,2,3,4,5))
val res5: List[Int] = List(5, 4, 3, 2, 1)

scala> union1(List(1,2,3,4), List(3,4,5,6))
val res6: List[Int] = List(2, 1, 3, 4, 5, 6)

scala> intersection1(List(1,2,3,4), List(3,4,5,6))
val res7: List[Int] = List(4, 3)

scala> difference1(List(1,2,3,4), List(3,4,5,6))
val res8: List[Int] = List(2, 1)

●解答８

リスト : 連想リスト

  def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)] =
    (xs, ys) match {
      case (Nil, _) | (_, Nil) => Nil
      case (x::xs, y::ys) => (x, y)::zip(xs, ys)
    }

  def unzip[A, B](xs: List[(A, B)]): (List[A], List[B]) =
    xs match {
      case Nil => (Nil, Nil)
      case (x, y)::zs => {
        val (xs1, ys1) = unzip(zs)
        (x::xs1, y::ys1)
      }
    }

  def assoc[A, B](x: A, xs: List[(A, B)]): Option[(A, B)] =
    xs match {
      case Nil => None
      case (k, v)::ys => if (k == x) Some((k, v)) else assoc(x, ys)
    }

  def assocIf[A, B](f: A => Boolean, xs: List[(A, B)]): Option[(A, B)] =
    xs match {
      case Nil => None
      case (k, v)::ys => if (f(k)) Some((k, v)) else assocIf(f, ys)
    }

zip はリストの要素 x, y を取り出してタプルにまとめ、それを返り値のリストに追加していくだけです。どちらかの引数が空リストになったときが再帰呼び出しの停止条件です。unzip は引数が空リストの場合、2 つの空リストを格納したタプルを返します。これが再帰の停止条件になります。次に、unzip を再帰呼び出しして、変数 xs1, ys1 に返り値のリストを受け取ります。あとは、xs1 に x を、ys1 に y を追加してタプルに格納して返すだけです。

assoc, assocIf は引数のリストが空リストの場合は None を返します。そうでなければ、aasoc はタプルの先頭要素 k が x と等しいかチェックします。等しい場合は Some((k, v)) を返し、そうでなければ assoc を再帰呼び出しして次の要素をチェックします。assocIf は f(k) が真の場合に Some((k, v)) を返し、そうでなければ assocIf を再帰呼び出しします。

●解答９

リスト : 選択ソート

  def selectSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
    for (i <- 0 until buff.size) {
      var min = i
      for (j <- i + 1 until buff.size) {
        if (buff(j) < buff(min)) min = j
      }
      var tmp = buff(i)
      buff(i) = buff(min)
      buff(min) = tmp
    }
  }

最初のループで変数 i の値は 0 から buff.size - 1 まで動きます。2 番目のループで buff(i) から buff(buff.size - 1) までの中から最小値を探します。最小値の位置は変数 min に格納します。初期値は i になります。2 番目のループを終了したら、buff(i) と buff(min) の値を交換します。

●解答10

リスト : 選択ソート (リスト版)

  def selectSortList[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] = {
    def sort(xs: List[A], ys: List[A]): List[A] =
      xs match {
        case Nil => ys
        case z::zs => {
          val x = maximum(xs)
          sort(remove(x, xs), x::ys)
        }
      }
    sort(xs, Nil)
  }

実際の処理は局所関数 sort で行います。引数 xs の中から最大値 x を maximum で求め、それを引数 ys のリストに追加します。このとき、remove で xs から x を削除します。xs が空リストになったらソートが完了したので ys を返します。

選択ソートの実行時間はデータの個数の 2 乗に比例する遅いソートです。

●プログラムリスト

//
// yasp01.scala : Yet Another Scala Problems (1)
//
//                Copyright (C) 2014-2021 Makoto Hiroi
//

object yasp01 {
  // Q01
  def square(n: BigInt): BigInt = n * n
  def cube(n: BigInt): BigInt = n * n * n

  def sumOf(f: BigInt => BigInt)(n: Int, m: Int, a: BigInt = 0): BigInt =
    if (n > m) a
    else sumOf(f)(n + 1, m, a + f(n))

  def sumOf1(f: BigInt => BigInt)(n: Int, m: Int): BigInt =
    (BigInt(n) to m).map(f).sum

  def sumOfInt(n: Int, m: Int): BigInt =  sumOf(identity)(n, m)
  def sumOfSquare(n: Int, m: Int): BigInt = sumOf(square)(n, m)
  def sumOfCube(n: Int, m: Int): BigInt = sumOf(cube)(n, m)

  def sumOfInt1(n: Int, m: Int): BigInt = {
    def f(x: BigInt): BigInt = x * (x + 1) / 2
    f(m) - f(n - 1)
  }

  // 別解
  def sumOfSquare1(n: Int, m: Int): BigInt = {
    def f(x: BigInt): BigInt = x * (x + 1) * (2 * x + 1) / 6
    f(m) - f(n - 1)
  }

  def sumOfCube1(n: Int, m: Int): BigInt = {
    def f(x: BigInt): BigInt = x * x * (x + 1) * (x + 1) / 4
    f(m) - f(n - 1)
  }

  // Q02
  def sqrtInt(n: Int, m: Int = 1): Int =
    if (n < m) m / 2 else sqrtInt(n - m, m + 2)

  def sqrtInt1(n: Int): Int =
    if (n < 100)
      sqrtInt(n)
    else {
      val m = 10 * sqrtInt1(n / 100)
      sqrtInt(n - m * m, 2 * m + 1)
    }

  // Q03
  def sqrt(n: Double): Double = {
    def init(s: Double, x: Double): Double =
      if (s >= x) s
      else init(s * 2, x / 2)

    def iter(p: Double): Double = {
      val q = (p + n / p) / 2
      if (q >= p) p else iter(q)
    }

    if (n < 0) throw new Exception("sqrt: domain error")
    else if (n == 0) 0
    else iter(if (n > 1) init(1, n) else 1)
  }

  // Q04
  def polygonalNum(p: Int, n: Int): Int =
   ((p - 2) * n * n - (p - 4) * n) / 2

  // Q05
  def minimum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
    def min(xs: List[A], a: A): A =
      xs match {
        case Nil => a
        case y::ys => if (y < a) min(ys, y) else min(ys, a)
      }
    //
    min(xs.tail, xs.head)
  }

  def maximum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
    def max(xs: List[A], a: A): A =
      xs match {
        case Nil => a
        case y::ys => if (y > a) max(ys, y) else max(ys, a)
      }
    //
    max(xs.tail, xs.head)
  }

  // 別解
  def minimum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
    xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x < a) x else a)

  def maximum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
    xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x > a) x else a)

  // Q06
  def remove[A](x: A, xs: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case y::ys => if (x == y) ys else y :: remove(x, ys)
    }

  def removeIf[A](f: A => Boolean, xs: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case y::ys => if (f(y)) ys else y :: removeIf(f, ys)
    }

  // Q07
  def distinct[A](xs: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case y::ys => if (ys contains y) distinct(ys) else y::distinct(ys)
    }

  def union[A](xs: List[A], ys: List[A]): List[A] =
    xs match {
      case Nil => ys
      case (x::xs1) => if (ys contains x) union(xs1, ys) else x::union(xs1, ys)
    }

  def intersection[A](xs: List[A], ys: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case (x::xs1) => if (ys contains x) x::intersection(xs1, ys) else intersection(xs1, ys)
    }

  def difference[A](xs: List[A], ys: List[A]): List[A] =
    xs match {
      case Nil => Nil
      case (x::xs1) => if (ys contains x) difference(xs1, ys) else x::difference(xs1, ys)
    }

  // 別解
  def distinct1[A](xs: List[A]): List[A] =
    xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (a contains x) a else x::a)

  def union1[A](xs: List[A], ys: List[A]): List[A] =
    xs.foldLeft(ys)((a: List[A], x: A) => if (a contains x) a else x::a)

  def intersection1[A](xs: List[A], ys: List[A]): List[A] =
    xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) x::a else a)

  def difference1[A](xs: List[A], ys: List[A]): List[A] =
    xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) a else x::a)

  // Q08
  def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)] =
    (xs, ys) match {
      case (Nil, _) | (_, Nil) => Nil
      case (x::xs, y::ys) => (x, y)::zip(xs, ys)
    }

  def unzip[A, B](xs: List[(A, B)]): (List[A], List[B]) =
    xs match {
      case Nil => (Nil, Nil)
      case (x, y)::zs => {
        val (xs1, ys1) = unzip(zs)
        (x::xs1, y::ys1)
      }
    }

  def assoc[A, B](x: A, xs: List[(A, B)]): Option[(A, B)] =
    xs match {
      case Nil => None
      case (k, v)::ys => if (k == x) Some((k, v)) else assoc(x, ys)
    }

  def assocIf[A, B](f: A => Boolean, xs: List[(A, B)]): Option[(A, B)] =
    xs match {
      case Nil => None
      case (k, v)::ys => if (f(k)) Some((k, v)) else assocIf(f, ys)
    }

  // Q09
  def selectSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
    for (i <- 0 until buff.size) {
      var min = i
      for (j <- i + 1 until buff.size) {
        if (buff(j) < buff(min)) min = j
      }
      var tmp = buff(i)
      buff(i) = buff(min)
      buff(min) = tmp
    }
  }

  // Q10
  def selectSortList[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] = {
    def sort(xs: List[A], ys: List[A]): List[A] =
      xs match {
        case Nil => ys
        case z::zs => {
          val x = maximum(xs)
          sort(remove(x, xs), x::ys)
        }
      }
    sort(xs, Nil)
  }
}

初版 2014 年 9 月 14 日
改訂 2021 年 4 月 11 日

Scala Programming