『Scala by Example』第9章Lists

リストはCやJavaの配列のようですが、3つの違いがあります.1.リストは可変です.2.リストは再帰的であり、配列は平坦である.3.リストは多くの操作の豊富な集合をサポートしますが、配列はありません.
9.1使用リスト
リストタイプ:配列と同様にリストも同質化(homogeneous).すなわち、すべての要素が同じタイプである.
リスト構造:すべてのリストは、Nilと::(cons)の2つの部分で構成されています.
基本操作:主に3つあります:head,tail,isEmpty.これらはすべてList Objectに定義されています.headとtailは空でないリストでしか使用できません.「挿入ソート」の例で説明できます.
パターンマッチング::Scala標準ライブラリにはcase classがあります.モードマッチングで
 
9.2 Listクラスの定義
Listは抽象クラスです.リストには多くの方法が定義されており、以下のように解釈されている.
リストを分解します.
噛み合い(zipping lists):2つのリストを1つのリストペアに結合し、例えば、リスト:xs=リスト(X 1,...Xn)とys=リスト(y 1,...,yn)、xs zipysがあると、リストペア:リスト((X 1,Y 1),...(Xn , Yn))
アクションリスト:他の接頭辞オペレータと同様に、::オブジェクトとして実装する方法.Scalaで「:」で終わるオペレータはすべて右オペレータとして扱われ、つまり右から左へ演算されます.
接続リスト:::::::::オペレータは、2つのリストを接続するために使用できます.
反転リスト:もう一つの有用な操作は反転(reversal)です.reverse法の実装を示したが,この方法はListの長さに比例し,あまり有効ではなかった.その後,線形関係のみの実装が与えられる.

def reverse[A](xs : List[A]) : List[A] = xs match{

  case Nil => Nil 

  case x :: xs => reverse(xs) ::: List(x)

}

 
9.3例:集計ソート(merge sort)
以前の挿入ソート(insertion sort)は簡単ですが、あまり効果的ではありません.平均複雑度は、入力リストの長さの二乗に比例します.ソートを挿入するよりも良いアルゴリズムは、「集計ソート」です.次のように動作します.
一、このリストに0個または1個の要素がある場合、それはすでに並べられており、直接このリストに戻ることができる.少し長いリストは2つの部分に分けられ、各部分には元のリストの約半分の長さの内容が含まれている.各サブリストは、再帰的なソート呼び出しによってソートされ、2つのソートされたリストは、1つのマージ操作によってマージされます.
集計ソートの実装では、要素タイプを指定するとともに、ソートルールを決定するために比較(comparison)を行う関数も指定します.1つの実装は次のとおりです.

  def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {



    def merge(xs1: List[A], xs2: List[A]): List[A] =

      if (xs1.isEmpty) xs2

      else if (xs2.isEmpty) xs1

      else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)

      else xs2.head :: merge(xs1, xs2.tail)



    val n = xs.length / 2

    if (n == 0) xs

    else merge(msort(less)(xs.take(n)), msort(less)(xs.drop(n)))



  }

msortの定義はコリー化されているので、このように使用できます.

val intSort = msort((x : Int , y : Int) => x < y)

val reverseSort = msort((x : Int , y : Int) => x > y)