“Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。ちょっとずつ読んで、各章の内容をまとめてゆきます。

https://www.amazon.co.jp/exec/obidos/asin/4844337769/esplo06-22

今回は3章まで。主にデータ更新です。関数型っぽさが増してきます。

https://blog.esplo.net/entry/2016/09/sfdp-2

3章

純粋関数では副作用が無いわけですが、どうやってデータを更新するの？というのが主な章です。

早速Listの定義が現れて面食らいますが、読み解くのはそこまで難しくありませんでした。単方向リストの説明も行われ、パターンマッチの説明があります。 matchはやっぱり便利ですね。

ここでパターンマッチの簡単なクイズがあります（略）。

次に、データが変更されないことを利用して、データの共通化をして節約してるよ、という話が入ります。ここから怒涛の練習問題です。大量に出てきます。詰込型プログラミングです。

Listに対するtail, setHead, drop, dropWhile, initを実装せよ。エラー処理は各自考えよ。

リストの定義などはgithubに上げられています。

https://github.com/fpinscala/fpinscala/blob/master/exercises/src/main/scala/fpinscala/datastructures/List.scala

エラー処理は色々と方法がありそうですが、とりあえずNilを返すことにしました。本家ScalaのListでは例外を吐いていましたが、とりあえず簡単に実装できることを優先します。

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

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

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

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

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

↓はテスト用のコードです。

object Main extends App {
  val x = List(1,2,3,4,5)
  val y = List()

  println("  # ex 3.2")
  println(List.tail(x))
  println(List.tail(y))

  println("  # ex 3.3")
  println(List.setHead(x, 10))
  println(List.setHead(y, 10))

  println("  # ex 3.4")
  println(List.drop(x, 1))
  println(List.drop(x, 4))
  println(List.drop(x, 10))
  println(List.drop(y, 1))

  println("  # ex 3.5")
  println(List.dropWhile(x, (a:Int)=> a < 4))
  println(List.dropWhile(x, (a:Int)=> a > 4))
  println(List.dropWhile(x, (a:Int)=> a < 100))

  println("  # ex 3.6")
  println(List.init(x))
  println(List.init(y))
}

dropだけネストしてて不格好だなぁ……。

豆知識として、dropWhileの型推論を改善する方法が紹介されています。カリー化して2つ目の引数を推測できるようにしています。なるほど。

さて、既に定義されていたsumとproductを一般化するため、foldRightが出てきました。 Scalaを触り始めて最初にこいつを見た時は、全く意味がわからなかったことを覚えています。

さて、またしても練習問題です。

foldRightでのproductは0.0を検出した瞬間に、直ちに再帰を中止して0.0を返せるか？

質問されてしまいました。こういうパターンもあるのね。独自のproductであれば0.0の要素まで来た時に続く再帰をさせず0.0を返すことはできますが、そこまでの要素は展開されてしまい計算するしかありません。 foldRightだとfの中でそのような処理を行えますが、fが評価されるのは全て展開された後です。というわけで「直ちに0.0を返せるか」という問はNoだと言えます。

Nil及びCons自体をfoldRightに渡すとどうなるか？データコンストラクタとの関係は？

なんとも曖昧な質問ではありますが、畳み込みでListのコンストラクタができる、ということだと思います。 2要素をくっつけるのも演算として捉えられ、それを繰り返すことで単方向リストも作れるよ、というまさに抽象的な考え方です。

foldRightを使ってリストの長さを求めよ。

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

foldRightは末尾再帰でないため、スタックセーフでない。末尾再帰なfoldLeftを実装せよ。

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

foldLeftがさっくり出てきましたね。末尾再帰でないから〜という方向から紹介するのは何となく目新しいです。

foldLeftを使って、sum/product/lengthを実装せよ。

  def flSum(l: List[Int]) = foldLeft(l, 0)(_ + _)
  def flProduct(l: List[Double]) = foldLeft(l, 1.0)(_ * _)
  def flLength[A](l: List[A]): Int = foldLeft(l, 0)((x,y) => x + 1)

reverseを実装せよ。

  def reverse[A](l: List[A]): List[A] = foldLeft(l, Nil: List[A])((x,y) => Cons(y, x))

foldRightでコンストラクトすると普通の順でしたが、foldLeftを使うと逆順になりますね。

[難問] foldRightを使ってfoldLeftを記述できるか？またその逆は？

難問マークは、なんか辛い問題に付けられているらしいです。 foldRightはf(a1, f(a2, f(a3, init)))、foldLeftはf( f( f(init, a1), a2), a3)となっていることを考えると、リストをひっくり返して適用すれば同じようなことができそうです。ただ、fの適用順も違いますので、引数の順をひっくり返したf2を用意しました。

  def foldLeft2[A, B](l: List[A], z: B)(f: (B, A) => B): B = {
    val f2: (A, B) => B = (a: A, b: B) => f(b, a)
    foldRight(reverse(l), z)(f2)
  }
  def foldRight2[A, B](as: List[A], z: B)(f: (A, B) => B): B = {
    val f2: (B, A) => B = (b: B, a: A) => f(a, b)
    foldLeft(reverse(as), z)(f2)
  }

テスト用コードです。

  println(List.foldRight(List(1,2,3,4), 0)(_ - _))
  println(List.foldRight2(List(1,2,3,4), 0)(_ - _))
  println(List.foldLeft(List(1,2,3,4), 0)(_ - _))
  println(List.foldLeft2(List(1,2,3,4), 0)(_ - _))

上手く行ってそうです。ただ、reverseでfoldLeftを使っているので、foldLeft2をfoldLeftとして使うと無限ループしてしまいました。

解説を読むと、何ともいかついコードが現れました。

  def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

ぱっと見では理解できませんが、具体的なListなどを放り込んであげると見えてきました。うまーく関数を渡すことで、処理順を変えています。これがパッと書けるとステキ。

foldRight or foldLeftを使ってappendを実装せよ。

  def flAppend[A](a1: List[A], a2: List[A]): List[A] = foldRight(a1, a2)(Cons(_, _))

うーん、スッキリ。

[難問] 既に定義した関数を使って、複数のリストからなるリストを1つのリストとして連結する関数を実装せよ。

appendを使って各要素をListとみなしてくっつけていけば出来そうです。

  def concat[A](l: List[List[A]]): List[A] = foldLeft(l, Nil: List[A])(append(_, _))

IntelliJの教えに従い、appendは以下のように簡単に呼び出せます。

 foldLeft(l, Nil: List[A])(append)

各要素に1を足したリストを返す関数を実装せよ。

 def plusOne(l: List[Int]): List[Int] = foldRight(l, Nil: List[Int])((x,y) => Cons(x + 1, y))

List[Int]をList[Double]に変換する関数を実装せよ。

  def doubleToString(l: List[Double]): List[String] = foldRight(l, Nil: List[String])((x,y) => Cons(x.toString, y))

mapを作れ。

  def map[A, B](l: List[A])(f: A => B): List[B] = foldRight(l, Nil: List[B])((x,y) => Cons(f(x), y))

あのmapがこんなにも簡単に！

filter関数を記述せよ。

  def filter[A](as: List[A])(f: A => Boolean): List[A] = {
    foldRight(as, Nil: List[A])((x,y) => {
      if(f(x))
        Cons(x, y)
      else
        y
    })
  }

ifが出てきて若干不格好です。

flatMapを実装せよ。

  def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] = concat(map(as)(f))

事前に作成した関数が活きました。

flatMapを使ってfilterを実装せよ。

条件を満たさない場合は空配列を返してあげることで、flattenした際に勝手に消えてくれそうです。というわけで、受け取った関数を少しいじってflatMapに渡します。

  def ffilter[A](as: List[A])(f: A => Boolean): List[A] = {
    val t = (a: A) => if(f(a)) Cons(a, Nil) else Nil
    flatMap(as)(t)
  }

リストを2つ受け取り、対応する要素同士を足しあわせたリストを返す関数を実装せよ。

  def plus(l1: List[Int], l2: List[Int]): List[Int] = {
    def loop(xs1: List[Int], xs2: List[Int]): List[Int] = {
      xs1 match {
        case Cons(x, xs) =>
          xs2 match {
            case Cons(y, ys) => Cons(x + y, loop(xs, ys))
            case Nil => Nil
          }
        case Nil => Nil
      }
    }
    loop(l1, l2)
  }

なんだか不格好ですね。 matchが入れ子になっていてどうにもみにくい……。

↑を一般化したzipWithを作れ。

  def zipWith[A, B, C](l1: List[A], l2: List[B])(f: (A,B) => C): List[C] = {
    def loop(xs1: List[A], xs2: List[B]): List[C] = {
      xs1 match {
        case Cons(x, xs) =>
          xs2 match {
            case Cons(y, ys) => Cons(f(x, y), loop(xs, ys))
            case Nil => Nil
          }
        case Nil => Nil
      }
    }
    loop(l1, l2)
  }

解説を見ると、2つのListをまとめてmatchで判定しています。なるほど、綺麗。

  def plus2(l1: List[Int], l2: List[Int]): List[Int] = {
    (l1, l2) match {
      case (Nil, _) => Nil
      case (_, Nil) => Nil
      case (Cons(x,xs), Cons(y,ys)) => Cons(x + y, plus2(xs, ys))
    }
  }
  def zipWith2[A](l1: List[A], l2: List[A])(f: (A,A) => A): List[A] = {
    (l1, l2) match {
      case (Nil, _) => Nil
      case (_, Nil) => Nil
      case (Cons(x,xs), Cons(y,ys)) => Cons(f(x, y), zipWith2(xs, ys)(f))
    }
  }

[難問] List (sup)の一部にあるList (sub)が含まれているかを判定する、hasSubsequenceを作れ。効率的なのは難しいかもしれない。5章でもう一度取り上げる。

手前から順番にsub.length個取り出すのを試してみると実現できそうです。まずはtakeを実装し、それを利用して作りました。

  def take[A](l: List[A], n: Int): List[A] = {
    n match {
      case 0 => Nil
      case _ =>
        l match {
          case Cons(x, xs) => Cons(x, take(xs, n-1))
          case Nil => Nil
        }
    }
  }

  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
    // 長さnの配列を前から順に取り出して比較
    def make(l: List[A], n: Int): Boolean = {
      if(take(l, n) == sub)
        true
      else {
        l match {
          case Nil => false
          case Cons(x, xs) => make(xs, n)
        }
      }
    }

    make(sup, length(sub))
  }

挙動は大丈夫そうですが、相変わらず若干不格好です。とりあえず答えがどうなっているか見ると、startsWithをまず作って利用しています。とにかく前方から一致を見てゆく方法です。確かにこれで十分だ。

シンプルな上に両方末尾再帰になっていて何とも凄いです。が、著者的にも「正しい挙動をするかわかりにくい」そうです。 5章で再度取り上げる胸熱展開らしいので、そこまで待機……。

ここまで大量の練習問題が出てきて満身創痍ですが、さらに新しいデータ構造が出てきます。おなじみツリーです。代数的データ型の説明があり、Treeの実装、及び練習問題が出てきます。

2分木のノード数を数えるsize、最大の要素を返すmaximum、二分木のルートから任意のノードへの最長距離を返す関数depth、二分木の各要素を変換するmapを実装せよ。

  def size[A](t: Tree[A]): Int = {
    t match {
      case Leaf(a) => 1
      case Branch(l, r) => size(l) + size(r)
    }
  }

  def maximum(t: Tree[Int]): Int = {
    t match {
      case Leaf(a) => a
      case Branch(l, r) => maximum(l).max(maximum(r))
    }
  }

  def depth[A](t: Tree[A]): Int = {
    t match {
      case Leaf(a) => 1
      case Branch(l, r) => size(l).max(size(r))
    }
  }

  def map[A, B](t: Tree[A])(f: A => B): Tree[B] = {
    t match {
      case Leaf(a) => Leaf(f(a))
      case Branch(l, r) => Branch(map(l)(f), map(r)(f))
    }
  }

上記関数を一般化したfoldを実装せよ。また、それを使って上記関数を再実装せよ。

  def fsize[A](t: Tree[A]): Int = fold(t)(_ => 1)(_ + _)
  def fmaximum(t: Tree[Int]): Int = fold(t)((a:Int) => a)(_ max _)
  def fdepth[A](t: Tree[A]): Int = fold(t)(_ => Tree.fsize(t))(_ max _)
  def fmap[A, B](t: Tree[A])(f: A => B): Tree[B] =
    fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_,_))

いやー、短い実装だ。型にガイドされながら書けます。

ようやくおしまいです。一般化のスキルを磨いてね！という修行を課して本章は締められています。

思ったこと

大量の練習問題がありましたが、それぞれ思ったより短く書けてびっくりしました。沢山解いていると、何となく思考方法が見えてきたような気がしないでもないです。

木の走査など、「めんどくさい……」となる処理でもシンプルに書けるのは、一度体験する価値があると思います。

次章はエラー処理で、普段のプログラミングでも困りがちな箇所にフォーカスしてゆくそうです。

続き https://blog.esplo.net/entry/2016/09/sfdp-4

Scala関数型デザイン&プログラミング 〜3章 (3)

3章

思ったこと

Scala関数型デザイン&プログラミング〜3章 (3)