2008年10月16日木曜日

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))
}

2 件のコメント:

murase_syuka さんのコメント...

:::はListとListの接続、
::はListと要素の合成です。
val a = List(1,2,3)
val b = List(4,5,6)
a:::b //=>List(1,2,3,4,5,6)
0::a //=>List(0,1,2,3)
こんな感じです。

kentaro さんのコメント...

なるほど、ありがとうございます。定義で引数の型をちゃんと見てればわかったはずの内容でしたね ;-(