Scalaのリスト－1階メソッド－

続いては、Listの1階操作。

要素の取得

まずは、List要素を取得するようなやつらから。

• isEmpty
• head
• tail
• length
• last
• take
• drop
• split
• apply
• init

おなじみですね。じゃ、次。というのもアレなので、それぞれのメソッドの実装を見てみる。

def isEmpty: Boolean = this match {
  case Nil => true
  case x :: xs => false
}

def head: A = this match {
  case Nil => error("Nil.head")
  case x :: xs => x
}

def tail: List[A] = this match {
  case Nil => error("Nil.tail")
  case x :: xs => xs
}

この辺はそのまんまという感じ。

def length: Int = this match {
  case Nil => 0
  case x :: xs => 1 + xs.length
}

def last: A = this match {
  case Nil => error("Nil.last")
  case x :: Nil => x
  case x :: xs => xs.last
}

def take(n: Int): List[A] = if (n == 0 || isEmpty) Nil else head :: tail.take(n1)

def drop(n: Int): List[A] = if (n == 0 || isEmpty) this else tail.drop(n1)

このあたりから再帰が入ってくる。正直自分も関数型にはあまり慣れてないんだけど、ちょっとずつわかってきた気がする。手続き型のように問題をトップダウンで分解するというよりは、解が明らかな状況から積み上げるように考える…ような。

def split(n: Int): (List[A], List[A]) = (take(n), drop(n))

def apply(n: Int): A = drop(n).head

定義済みの関数を使えば簡単に書ける。

挿入ソート

ScalaByExampleから挿入ソートのサンプルを転載。

def isort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case x :: xs1 => insert(x, isort(xs1))
}

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List() => List(x)
  case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys) }

うーん、いいね。やっぱこうでないと。Listのインスタンスはすべてcaseクラスだから、こゆ風になるのね。caseパターンのバリエーションについてはもう少し知りたいところだけど、それはまた別の機会にちゃんと調べることにする。

ZIP

ホグワーツ違法学校が浮かんでくるが、それはまぁ良いとして…ZIPです。同じ長さの複数のListを縦（？）に結合して1つのListとして返すもの。

def zip[B](that: List[B]): List[(a,b)] = if (this.isEmpty || that.isEmpty) Nil else (this.head, that.head) :: (this.tail zip that.tail)

こんな感じ。

Listの結合

演算子「:::」を使う。これまた、Listのメソッド。正直、「::」とどう違うのかよくわかってません ^^;

def :::[B >: A](prefix: List[B]): List[B] = prefix match {
  case Nil => this
  case p :: ps => this.:::(ps).::(p)
}

リバース

reverseメソッドを使う。

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil => Nil
  case x :: xs => reverse(xs) ::: List(x)
}

:::を使ってうまいこと書いてある。

マージソート

例として、マージソートが書いてある。わからないところはないんだけど、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))
}