shutdown -r now

Scalaリスト遊び１（Scala関数型デザインより）

「Scala関数型デザイン&プログラミング」のリスト

第 3 章　関数型プログラミングのデータ構造

辺りのリスト

コード

package example

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))

  def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match {
      case Nil => a2
      case Cons(h,t) => Cons(h, append(t, a2))
    }

  def drop[A](l: List[A], n: Int): List[A] =
    if (n <= 0) l
    else l match {
      case Nil => Nil
      case Cons(_,t) => drop(t, n-1)
    }

  @annotation.tailrec
  def foldLeft[A,B](l: List[A])(z: B)(f: (B, A) => B): B = l match {
    case Nil => z
    case Cons(h, t) => foldLeft(t)(f(z, h))(f)
  }

  def foldRight[A,B](l: List[A])(z: B)(f: (A, B) => B): B = l match {
    case Nil => z
    case Cons(h, t) => f(h, foldRight(t)(z)(f))
  }

  def length2[A](l: List[A]): Int =
    foldRight(l)(0)((_,acc) => acc + 1)

  def sum(l: List[Int]) = foldLeft(l)(0)(_ + _)
  def sum2(l: List[Double]) = foldLeft(l)(0.0)(_ + _)
  def product(l: List[Int]) = foldLeft(l)(1)(_ * _)
  def product2(l: List[Double]) = foldLeft(l)(1.0)(_ * _)
  def length[A](l: List[A]): Int = foldLeft(l)(0)((acc, _) => acc + 1)

  def main(args: Array[String]): Unit ={
    val l = List(1,2,3,4,5)
    println(s"l:${l}")

    val ld = drop(l, 3)
    println(s"ld:${ld}")

    val ldw = dropWhile(l)(i => i < 4)
    println(s"ldw:${ldw}")

    val sumResult = sum(l)
    println(s"sumResult:${sumResult}")
    val productResult = product(l)
    println(s"productResult:${productResult}")

  }

}

リストの定義

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))

トレイトとそのコンパニオンクラスとして、Listを定義する。
sealed trait List[+A] の[+A]の+は、共変を意味する
共変・反変・上限境界・下限境界の関係性まとめ
Nilが空と終端のリストを表し
リストの中身は、Cons
applyは、可変長引数をもらって、初期化を行う val l = List(1,2,3,4,5) で初期化できるようにする

リストの操作

  def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match {
      case Nil => a2
      case Cons(h,t) => Cons(h, append(t, a2))
    }

  def drop[A](l: List[A], n: Int): List[A] =
    if (n <= 0) l
    else l match {
      case Nil => Nil
      case Cons(_,t) => drop(t, n-1)
    }

append で、リスト同士をつなげる
drop は、リストの先頭からn個の要素を削除する実装は、再帰呼び出しでループさせて、指定された個数のあとのリストを返している

畳み込み

  @annotation.tailrec
  def foldLeft[A,B](l: List[A])(z: B)(f: (B, A) => B): B = l match {
    case Nil => z
    case Cons(h, t) => foldLeft(t)(f(z, h))(f)
  }

  def foldRight[A,B](l: List[A])(z: B)(f: (A, B) => B): B = l match {
    case Nil => z
    case Cons(h, t) => f(h, foldRight(t)(z)(f))
  }

foldLeft は、左畳み込み素直に実装。fを呼んで、初期値として、foldLeftを再帰呼び出しすればよい
foldRightは、右畳み込み foldRightを再帰呼び出しし続けてから、終端のNilで初期値を戻しつつ、fを呼ぶこの実装では、末尾再帰にならない。

foldLeftの使用例

  def sum(l: List[Int]) = foldLeft(l)(0)(_ + _)
  def sum2(l: List[Double]) = foldLeft(l)(0.0)(_ + _)
  def product(l: List[Int]) = foldLeft(l)(1)(_ * _)
  def product2(l: List[Double]) = foldLeft(l)(1.0)(_ * _)
  def length[A](l: List[A]): Int = foldLeft(l)(0)((acc, _) => acc + 1)
  def length2[A](l: List[A]): Int = foldRight(l)(0)((_,acc) => acc + 1)