Scala 関数型デザイン&プログラミング:Exercize3.2 - 3.13

前回 からの続き
教本はこれ

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

Exercise 3.2

問題

Listの最初の要素を削除する関数 tail を実装せよ。この関数の実行時間が一定であることに注意。List が Nil である場合、実装上の選択肢として他に何があるか。この質問については次章で再び取り上げる。

とのこと。

で、オブ脳な個人的に「あれ？tailってあるよね？trait でIF作ってって事？」と本家 scala.collections の List っぽく

sealed trait List[+A] {
  def head: A
  def tail: List[A]
}

case object Nil extends List[scala.Nothing] {
  override def head = sys.error("Empty head")
  override def tail = sys.error("Empty list")
}

case class Cons[+A](head: A, tail: List[A]) extends List[A]

で、なんか違うな…筆者は何を想定してるんだろう？と思って回答を見た。

fpinscala/List.scala at master · fpinscala/fpinscala · GitHub

違った…コンパニオンオブジェクトの話だったという…。
忘れたふりしてさらっと

  def tail[A](l: List[A]): List[A] = l match {
    case Nil           => Nil
    case Cons(_, tail) => tail
  }

object Exercise3_2 extends App {

  val result = List.tail(List(1, 2, 3, 4))

  def printRec(l: List[Int]): Unit = l match {
    case Nil => println("")
    case Cons(n, t) => {print(s"$n "); printRec(t)}
  }

  printRec(result)
}

Exercise 3.3

問題

Exercise 3.2 と同じ考え方に基づいて、List の最初の要素を別の値と置き換えるsetHead 関数を実装せよ。

  def head[A](l: List[A]): A = l match {
    case Nil        => sys.error("no head in empty")
    case Cons(a, _) => a
  }

/*
// 検証
object Exercise3_3 extends App {
  println(List.head(List(1,2,3,4,5)))
}
 */

どう考えたって例外しか思い浮かばない…

Exercise 3.4

先頭から N 個を削除する関数 drop を作れ

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

/*
object Exercise3_4 extends App {
  printRec(List.drop(List(1,2,3,4,5), 2))
}
*/

Exercise3.5

述語とマッチする場合に限り、Listからその要素までの要素を削除する dropWhile を実装せよ。

  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = {
    l match {
      case Cons(h, t)  if f(h) =>  dropWhile(t, f)
      case _ => l
    }
  }

/*
object Exercise3_5 extends App {
  printRec(List.dropWhile[Int](List(1,2,3,4,5,6,7), _ < 5))
}
*/

Exercise 3.6

List の末尾を除く、すべての要素で構成された List を返す init 関数を実装せよ。

これは先頭から舐めるしかやり様がないので、要素 O(n) なんだろねー

  def reverse[A](l: List[A]): List[A] = {
    def inner(a: List[A], l: List[A]): List[A] = {
      l match {
        case Nil        => a
        case Cons(h, t) => inner(Cons(h, a), t)
      }
    }
    inner(Nil, l)
  }

  def init[A](list: List[A]): List[A] = {
    def inner(a: List[A], l: List[A]): List[A] = {
      l match {
        case Nil          => Nil
        case Cons(_, Nil) => a
        case Cons(h, t)   => inner(Cons(h, a), t)
      }
    }
    reverse(inner(Nil, list))
  }

/*
object Exercise3_6 extends App {
  val result: List[Int] = List.init(List(1,2,3,4,5))
  printRec(result)
}
*/

末尾再帰に拘らなければもっと短くなった気がする…今更か。

Exercise 3.7

考察問題なので端折る。

Exercise 3.8

foldRight 実装が前提になるので、まずは実装。
教科書通りの実装なのだが…

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = {
    as match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }
  }

…末尾再帰じゃない

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = {
    as match {
      case Nil         => z
      case Cons(x, xs) => foldRight(xs, f(x, z))(f)
    }
  }

これじゃあかんのかと思ったのだが…まぁ式に直すと f(5, f(4, f(3, f(2, f(1, z))) こんな感じになるから直感的ではないのかも？

object Exercise3_8 extends App {
  println(List(1,2,3,4,5))
  println(List.foldRight(List(1,2,3,4,5), Nil: List[Int])(Cons(_, _)))
}

結果はそう変わらず。
そりゃ head から順にとってけばそうなるよね

Exercise 3.9

リストの長さを計算する length を実装せよ。

  def length[A](as: List[A]): Long =
    foldRight(as, 0L)((_, b) => b + 1)
/*
object Exercise3_9 extends App {
  println(List.length(List(1,2,3,4,5)))
}
*/

Exercise 3.10

foldLeft を末尾再帰で実装せよ

…これってさっき書いた末尾再帰じゃね？ (･･;)

  def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = {
    as match {
      case Nil => z
      case Cons(x, Nil) => f(z, x)
      case Cons(x, xs)  => foldLeft(xs, f(z, x))(f)
    }
  }

Exercise 3.11

sum, product を foldLeft で実装せよ

  def sum(ints: List[Int]): Int = foldLeft(ints, 0)(_ + _)

  def product(sd: List[Double]): Double = foldLeft(sd, 1.0)(_ * _)

Exercise 3.12

リストを逆順する reverse 関数を作れ

あれ？上で書いた reverse 関数だよね？

Exercise 3.13

foldRight をベースに、foldLeft を記述することは可能か？その逆はどうか？

foldRight の初期値に関数突っ込めばいけるか？（つまり関数スタックを高階関数でやる）

  def foldLeftViaRight[A, B](as: List[A], z: B)(f: (B, A) => B): B =
    foldRight(as, (b:B) => b)((a, g) => b => g( f(b, a) ))(z)

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B =
    foldLeft(reverse(as), z)((a, b) => f(b, a))

foldRight の方は割とすんなり。