すごいHaskellたのしく学ぼう！をScalaでやってみたメモ

00_すごいHaskellたのしく学ぼう！をScalaでやってみたメモ.md

すごいHaskellたのしく学ぼう！をScalaでやってみたメモ

目次

• はじめの第一歩
  • Range
  • for内包表記
  • タプル
• Hello 再帰！
• 高階関数
  • カリー化関数
  • 畳み込み
  • 関数合成
• 型や型クラスを自分で作ろう
  • 長方形と円をつくる
  • 再帰的なデータ構造
  • YesとNoの型クラス
  • Functor型クラス
• もっと入力、もっと出力
  • ToDoリスト
• 関数型問題解決法
  • 逆ポーランド記法
• ファンクターからアプリカティブファンクターへ
  • もう1回ファンクター
  • ファンクター則
  • アプリカティブファンクター
  • アプリカティブの便利な関数
• モノイド
  • Monoid
  • モノイドのインスタンス
• モナドがいっぱい
  • Monad
  • モナドとしてのOption
  • 綱渡り
  • リストモナド
  • モナド則
• Zipper
  • Zipper
  • リストのZipper
  • ZipperにOptionを導入

01.md

Range

1から20までの数からなるリストを作るとき、Rangeを使うとスマートにできる。

scala> (1 to 20).toList
res7: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)

scala> ('a' to 'z').toList
res8: List[Char] = List(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z)

scala> ('K' to 'Z').toList
res9: List[Char] = List(K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z)

1ずつではなく2ずつ増やしたい場合などに、Rangeではステップを指定できる。

scala> (2 to 20 by 2).toList
res11: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

scala> (10 to 0 by -1).toList
res13: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

たとえば13の倍数の最初の24個からなるリストを作ってみる。

scala> (13 to 13 * 24 by 13).toList
res14: List[Int] = List(13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195, 208, 221, 234, 247, 260, 273, 286, 299, 312)

無限リストを使う方法もある。ScalaではStreamを使うことで無限リストを生成できる。fromメソッドの第1引数がスタートになる値で、第2引数がステップの値。

scala> Stream.from(13, 13).take(24).toList
res19: List[Int] = List(13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195, 208, 221, 234, 247, 260, 273, 286, 299, 312)

Streamでは要素が遅延評価されるので、無限リスト全体をすぐには評価しない。その代わりに、無限リストの中の要素が必要とされるまで待つ。上の例では、最初の24個した要求していないので、24個の要素のみを評価する。

無限の長さのリストを生成するために使えるメソッドがいくつかある。

Stream.continuallyは指定された値を繰り返す。

scala> Stream.continually(5).take(10).toList
res28: List[Int] = List(5, 5, 5, 5, 5, 5, 5, 5, 5, 5)

scala> Stream.continually(List(1, 2, 3)).take(10).toList
res24: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3), List(1, 2, 3))

リストを指定するとリストを要素とする無限リストができた。flattenを使うと指定したリストの要素を無限に繰り返す無限リストを生成することができる。

scala> Stream.continually(List(1, 2, 3)).flatten.take(10).toList
res26: List[Int] = List(1, 2, 3, 1, 2, 3, 1, 2, 3, 1)

for内包表記

for内包表記はリストのフィルタリング、変換、組み合わせを行う方法。 これは数学における集合の内包表的記法の概念に近いもの。 集合の内包的記法は、他の集合から別の集合を作るときによく用いられる。単純な例として、{2*x|x∈N, x<=10}のようなmのがある。 これは「10以下のすべての自然数を取ってきて、それぞれ2倍して、その結果を新しい集合としなさい」という意味になる。 同じことをScalaでやりたい場合、Stream.from(2, 2).take(10).toListのように書けるが、for内包表記を使ってこんなふうに書くこともできる。

scala> for (x <- 1 to 10 ) yield x * 2
res35: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

for (x <- 1 to 10 ) yield x*2では、(1 to 10)から要素を取り出す。for (x <- 1 to 10)は、(1 to 10)から取り出した各要素の値をxが受け取るという意味。このx <- 1 to 10の部分をジェネレータと呼ぶ。これは別の表現では、(1 to 10)の各要素をxに束縛していると言える。yield x * 2の部分は、for内包表記の出力を表している。この出力パートでは、取り出した値を使ってどんなリストを作りたいかを指定する。この例だと、(1 to 10)から取り出した各要素を2倍したい、と言ってる。

この例よりもっと複雑なことがやりたくなったらfor内包表記が便利になってくる。

例えば、さっきの内包表記に条件（述語とも呼ぶ）を追加する。述語は、for ()の括弧内にifを使って書く。2倍した値が12以上のものからなるリストを返すようにする。

scala> for (x <- 1 to 10 if x*2 > 12) yield x*2
res38: scala.collection.immutable.IndexedSeq[Int] = Vector(14, 16, 18, 20)

50 から 100 の数のうち、7で割った余りが3であるすべての数が欲しいとき。

scala> for (x <- 50 to 100 if x%7 == 3) yield x
res40: scala.collection.immutable.IndexedSeq[Int] = Vector(52, 59, 66, 73, 80, 87, 94)

10以上のすべての奇数を"BANG!"に置き換え、10より小さいすべての奇数を"BOOM!"に置き換えるメソッドを内包表記を使って書いてみる。

scala> def boomBangs(xs: List[Int]) = for (x <- xs if x%2 == 1) yield if (x < 10) "BOOM!" else "BANG!"
boomBangs: (xs: List[Int])List[String]

scala> boomBangs((7 to 13).toList)
res44: List[String] = List(BOOM!, BOOM!, BANG!, BANG!)

ifをたくさん書けば、たくさんの述語を含めることができる。

scala> for (x <- 10 to 20 if x !=13 if x != 15 if x != 19) yield x

もちろん1つのifの中で&&でつなげることもできる。

scala> for (x <- 10 to 20 if x !=13 && x != 15 && x != 19) yield x
res46: scala.collection.immutable.IndexedSeq[Int] = Vector(10, 11, 12, 14, 16, 17, 18, 20)

述語を複数書くだけでなく、複数のリストから値を取り出すこともできる。

scala> for (x <- List(1, 2, 3); y <- List(10, 100, 1000)) yield x + y
res47: List[Int] = List(11, 101, 1001, 12, 102, 1002, 13, 103, 1003)

2つのリストが次のように組み合わされる。最初にxが1になり、xが1の間に、yが[10, 100, 1000]からすべての値を取る。内包表記の出力パートがx+yなので、結果のリストの先頭が11, 101, 1001の各値になる。その後xが2になり、さっきと同じことが繰り返され、結果のリストに12, 102, 1002が追加される、最後に、xが3のときも同様。

2つのリストの積も同様。

scala> for (x <- List(2, 5, 10); y <- List(8, 10, 11)) yield x * y
res48: List[Int] = List(16, 20, 22, 40, 50, 55, 80, 100, 110)

すべての組み合わせの積のうちで50より大きいものだけ欲しい場合は、述語を追加するだけ。

scala> for (x <- List(2, 5, 10); y <- List(8, 10, 11) if x*y > 50) yield x * y
res49: List[Int] = List(55, 80, 100, 110)

文字列のリスト。

scala> val nouns = List("hobo", "frog", "pope")
nouns: List[String] = List(hobo, frog, pope)

scala> val adjectives = List("lazy", "grounchy", "scheming")
adjectives: List[String] = List(lazy, grounchy, scheming)

scala> for (adjective <- adjectives; noun <- nouns) yield adjective + noun
res50: List[String] = List(lazyhobo, lazyfrog, lazypope, grounchyhobo, grounchyfrog, grounchypope, scheminghobo, schemingfrog, schemingpope)

内包表記を使ってsizeメソッドと同様のメソッドを定義。

scala> def mySize(xs: List[Int]) = (for (_ <- xs) yield 1).sum
mySize: (xs: List[Int])Int

scala> mySize(List(1, 2, 3, 4))
res51: Int = 4

この例ではxsから取り出した値を利用しないので、それを使い捨てるために変数名アンダースコアを使っている。

ジェネレータには文字列を使うこともできる（PredefがStringからStringOpsへの暗黙の型変換を行うためStringもシーケンスになる）

scala> def removeNonUppercase(st: String) = for (c <- st if ('A' to 'Z').contains(c)) yield c
removeNonUppercase: (st: String)String

scala> removeNonUppercase("Hahaha! Ahahaha!")
res53: String = HA

リストを含むリストを操作する場合に、入れ子になった内包表記を考えてみる。

scala> val xxs = List(List(1, 3, 5, 2, 3, 1, 2, 4, 5), List(1, 2, 3, 4, 5, 6, 7, 8, 9), List(1, 2, 4, 2, 1, 6, 3, 1, 3, 2, 3, 6))
xxs: List[List[Int]] = List(List(1, 3, 5, 2, 3, 1, 2, 4, 5), List(1, 2, 3, 4, 5, 6, 7, 8, 9), List(1, 2, 4, 2, 1, 6, 3, 1, 3, 2, 3, 6))

scala> for (xs <- xxs) yield for (x <- xs if x%2 == 0) yield x
res55: List[List[Int]] = List(List(2, 2, 4), List(2, 4, 6, 8), List(2, 4, 2, 6, 2, 6))

外側の内包表記の出力パートが、別の内包表記になっている。内包表記は必ず何らかのリストを返すので、全体の結果は数のリストのリストになる。

タプル

タプルを使う

タプルは複数の違う型の要素を格納して1つの値にするために使う。 タプルは丸括弧で値を囲み、要素をカンマで区切る。

scala> (1, 3)
res77: (Int, Int) = (1,3)

scala> (3, 'a', "hello")
res78: (Int, Char, String) = (3,a,hello)

scala> (50, 50.4, "hello", 'b')
res79: (Int, Double, String, Char) = (50,50.4,hello,b)

2次元ベクトルを表すときにリストを使うと、List(List(1,2), List(8,11,5), List(4,5))というように要素数の異なるリストを混ぜることができてしまう。 これに対し、サイズ2のタプル（ペアとも呼ばれる）とサイズ3のタプルはそれぞれ違う型として扱われる。返り値として期待する型を指定しておくことでコンパイルエラーとすることができる。

scala> List((1,2), (8,11,5), (4,5))
res80: List[Product with Serializable] = List((1,2), (8,11,5), (4,5))

scala> val xs: List[(Int, Int)] = List((1,2), (8,11, 5), (4,5))
<console>:7: error: type mismatch;
 found   : (Int, Int, Int)
 required: (Int, Int)
       val xs: List[(Int, Int)] = List((1,2), (8,11, 5), (4,5))

長さが同じで違う型のタプルも同じ同様。

scala> List((1, 'a'), ('b', 2))
res83: List[(AnyVal, AnyVal)] = List((1,a), (b,2))

scala> val xs: List[Int, Char] = List((1, 'a'), (2, 'b'))
<console>:7: error: wrong number of type arguments for List, should be 1
       val xs: List[Int, Char] = List((1, 'a'), (2, 'b'))
               ^

タプルは固定長。あらかじめ必要とする要素の数が分かっている場合にだけ利用できる。Scalaでは要素数が22個のタプルまでしか作ることができないので注意。

scala> (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
res85: (Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int) = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22)

scala> (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
<console>:8: error: object <none> is not a member of package scala
              (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
              ^

ペアを使う

2要素のタプルをペアと呼ぶ。 _1, _2がペアの最初の要素と2つ目の要素を返す。

scala> (8, 11)._1
res87: Int = 8

scala> (8, 11)._2
res88: Int = 11

zipメソッドは2つのリストから1つのリストを生成する。2つのリストを同時に走査するときにとても便利。

scala> List(1, 2, 3, 4, 5).zip(List(5, 5, 5, 5, 5))
res89: List[(Int, Int)] = List((1,5), (2,5), (3,5), (4,5), (5,5))

scala> (1 to 5).toList.zip(List("one", "two", "three", "four", "five"))
res91: List[(Int, String)] = List((1,one), (2,two), (3,three), (4,four), (5,five))

リストの長さが違う場合は必要な分だけが使われ、余りは無視される。

scala> List(5, 3, 2, 6, 2, 7, 2, 5, 4, 6, 6).zip(List("im", "a", "turtle"))
res92: List[(Int, String)] = List((5,im), (3,a), (2,turtle))

Streamもzipできる。

scala> Stream.from(1).zip(List("apple", "orange", "cherry", "mango")).toList
res96: List[(Int, String)] = List((1,apple), (2,orange), (3,cherry), (4,mango))

直角三角形を見つける

次のすべての条件を満たす直角三角形を見つけるプログラムを書く。

• 3辺の長さはすべて整数である
• 各辺の長さは10以下である
• 周囲の長さは24に等しい

最初のステップとして、各要素が10以下であるようなトリプルをすべて生成してみる。

scala> val triples = for (c <- (1 to 10); a <- (1 to 10); b <- (1 to 10)) yield (a, b, c)

次に直角三角形のみを取得したいので、ピタゴラスの低利が成り立つかを調べる述語を追加。またaが斜辺cを超えないように、bがaを超えないように、それぞれ変更を加える。

scala> val rightTriangles = for (c <- (1 to 10); a <- (1 to c); b <- (1 to a) if a*a + b*b == c*c) yield (a, b, c)

最後に周囲の長さが24を取得するための述語を追加。

scala> val rightTriangles = for (c <- (1 to 10); a <- (1 to c); b <- (1 to a) if a*a + b*b == c*c && a+b+c == 24) yield (a, b, c)
rightTriangles: scala.collection.immutable.IndexedSeq[(Int, Int, Int)] = Vector((8,6,10))

答えが出ました！このように、最初に解の候補となる集合を生成し、それから1つ（もしくは複数）の解にたどり着くまで変換とフィルタリングを行うという手法は関数プログラミングでよく用いられるパターン。

04.md

4章の再帰のところのメモ。ちょろっとだけ。

scala> def maximum(xs: List[Int]): Int = xs match {
     |   case List() => throw new RuntimeException()
     |   case List(x) => x
     |   case x :: ys => val y = maximum(ys); if (x > y) x else y
     | }
maximum: (xs: List[Int])Int

scala> maximum(List(1, 4, 5, 2, 4, 6, 8, 2, 5))
res8: Int = 8

パターンマッチは再帰の定義にもってこい。合致と値の分解ができるので、最大値を見つけるという問題を、関連するいくつかのケースと部分問題に簡単に分解できる。

scala> def quickSort(xs: List[Int]): List[Int] = xs match {
     |   case List() => List()
     |   case y :: ys => {
     |     val smallerOrEqual = for (a <- ys if a <= y) yield a
     |     val larger = for (a <- ys if a > y) yield a
     |     quickSort(smallerOrEqual) ++ List(y) ++ quickSort(larger)
     |   }
     | }
quickSort: (xs: List[Int])List[Int]

scala> quickSort(List(10, 2, 5, 3, 1, 6, 7, 4, 2, 3, 4, 8, 9))
res9: List[Int] = List(1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9, 10)

再帰を書くには定石がある。まず、再帰に頼らない自明な解を持つ基底部から始める。例えば、「空のリストをソートしたものは空のリストである」というもの。 それから、問題を1つもしくはそれ以上の部分問題に分解し、自分自身を適用することによってそれらの部分問題を再帰的に解く。 最後に、最終的な解を部分問題の解から構築する。例えばソートの場合なら、リストを2つのリストとピボットに分解、それらのリストを再帰的にソートして、結果が得られたら、1つの大きなソート済みリストにする。

再帰を使う際の定石は、まず基底部を見極め、次に解くべき問題をより小さな部分問題へと分割する方法を考えること。これは分割統治の考え方になる。

末尾再帰によりプログラムのパフォーマンスを改善できる。 例えば再帰を使って階乗を計算するメソッド。これは最後に評価されるのが*であるため末尾再帰ではない。

scala> def factorial(x: Int): Int = x match {
     |   case 0 => 1
     |   case n => n * factorial(n - 1)
     | }
factorial: (x: Int)Int

末尾再帰で書き直すとこうなる。

scala> def highparomancefactorial(x: Int, p: Int = 1): Int = x match {
     |   case 0 => p
     |   case n => highparomancefactorial(n - 1, p * n)
     | }
highparomancefactorial: (x: Int, p: Int)Int

05.md

カリー化関数

Scalaではカリー化されたメソッドを定義することができる。

例えば、2つの整数のうち、大きい方を返すmaxメソッドをつくってみます。

scala> def max(x: Int, y: Int ) = if (x > y) x else y
max: (x: Int, y: Int)Int

scala> max(4, 6)
res15: Int = 6

これをカリー化された形に書き直してみる。カリー化された形式だとmax(4, 6)という風には呼べないので注意。

scala> def max2(x: Int)(y: Int) = if (x > y) x else y
max2: (x: Int)(y: Int)Int

scala> max2(4, 6)
<console>:11: error: too many arguments for method max2: (x: Int)(y: Int)Int
              max2(4, 6)
                  ^

scala> max2(4)(6)
res19: Int = 6

部分適用された関数を取得するには_を使う必要がある。

scala> max2(4)
<console>:11: error: missing arguments for method max2;
follow this method with `_' if you want to treat it as a partially applied function
              max2(4)
                  ^

scala> val f = max2(4)_
f: Int => Int = <function1>

scala> f(6)
res22: Int = 6

カリー化されていないメソッドに対しても部分適用できる。

scala> max(4, _: Int)
res28: Int => Int = <function1>

scala> val f = max(4, _: Int)
f: Int => Int = <function1>

scala> f(6)
res29: Int = 6

部分適用した結果のfは、関数型。Int => Intというには、Intを引数にとりIntを返す、という意味。 Scalaではメソッドとは別に関数がある。関数はメソッドとは異なりオブジェクトに依存せずに存在できるファーストクラスなオブジェクトである。

関数は、メソッドから部分適用で取得するほかに、関数リテラルで定義することもできる。

scala> val fmax = (x: Int, y: Int) => if (x > y) x else y
fmax: (Int, Int) => Int = <function2>

scala> fmax(4, 6)
res0: Int = 6

scala> val g = fmax(4, _: Int)
g: Int => Int = <function1>

scala> g(6)
res3: Int = 6

関数は、Function型のオブジェクトである。Functionオブジェクトのcurriedメソッドを使うことで、カリー化された関数にすることができる。

scala> val fmax = (x: Int, y: Int) => if (x > y) x else y
fmax: (Int, Int) => Int = <function2>

scala> fmax(4, 6)
res17: Int = 6

scala> fmax.curried
res18: Int => (Int => Int) = <function1>

scala> val curriedMax = fmax.curried
curriedMax: Int => (Int => Int) = <function1>

scala> curriedMax(3, 4)
<console>:10: error: too many arguments for method apply: (v1: Int)Int => Int in trait Function1
              curriedMax(3, 4)
                        ^

scala> curriedMax(3)(4)
res20: Int = 4

scala> val g = curriedMax(3)
g: Int => Int = <function1>

scala> g(4)
res21: Int = 4

畳み込み

リストに対する再帰処理の多くは、「基底部は空リストとし、x::xsパターンを使ってリストを先頭要素と残りのリストに分解する」というパターンがよく出てくる。 このパターンは畳み込みと呼ばれるメソッドたちで処理できる。

畳み込みで登場するのは3つ。畳み込むリスト、畳み込みに用いる値（アキュムレータと呼ぶ）の初期値、2引数を取る関数。

scala> List(3, 5, 2, 1).foldLeft(0)((acc, x) => acc + x)
res4: Int = 11

foldLeftメソッドはリストの左から順番に処理していく。(((3+5)+2)+1)という順。

関数リテラルの引数がそれぞれ1回ずつしか使われていないのでもっと簡単に書ける。

scala> List(3, 5, 2, 1).foldLeft(0)(_ + _)
res5: Int = 11

foldLeftメソッドの別名として/:がある。:で終わってるので右結合の形で書ける。

scala> (0 /: List(3, 5, 2, 1))(_ + _)
res6: Int = 11

foldRightメソッドはリストの右から順番に処理していく。(3+(5+(2+1)))という順。

scala> List(3, 5, 2, 1).foldRight(0)(_ + _)
res7: Int = 11

foldRightメソッドの別名として:\がある。

scala> (List(3, 5, 2, 1) :\ 0)(_ + _)
res8: Int = 11

foldLeftとfoldRightは処理結果は変わらないが、処理速度に差がでる。 :::メソッドの計算量は左側のリストの長さに比例するので、foldRightメソッドを使う。

scala> List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)).foldLeft(List[Int]())(_ ::: _)
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)).foldRight(List[Int]())(_ ::: _)
res3: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

関数合成

数学における関数合成は(f◦g)(x) = f(g(x))のように定義されており、2つの関数を合成したものは、まず1つの関数を呼び出し、それからもう1つの関数にその結果を渡して呼び出したものに等しいという意味。

ScalaでもandThenとcomposeメソッドで関数合成ができる。

関数合成の用途としては、他の関数に渡す関数をその場でつくるというものがある。関数リテラルでもいいが、関数合成の方が簡潔なときがある。

scala> val abs = (x: Int) => if (x < 0) -x else x
abs: Int => Int = <function1>

scala> val negate = (x: Int) => -x
negate: Int => Int = <function1>

scala> List(5, -3, -6, 7, -3, 2, -19, 24).map(x => negate(abs(x)))
res11: List[Int] = List(-5, -3, -6, -7, -3, -2, -19, -24)

scala> List(5, -3, -6, 7, -3, 2, -19, 24).map(negate(abs(_)))
<console>:10: error: missing parameter type for expanded function ((x$1) => abs(x$1))
              List(5, -3, -6, 7, -3, 2, -19, 24).map(negate(abs(_)))
                                                                ^

scala> List(5, -3, -6, 7, -3, 2, -19, 24).map(negate.andThen(abs(_)))
res13: List[Int] = List(5, 3, 6, 7, 3, 2, 19, 24)

07.md

長方形と円をつくる

長方形と円の2種類の図形を扱う型を作ってみる。

sealed trait Shape
case class Circle(x: Double, y: Double, r: Double) extends Shape
case class Rectangle(x1: Double, y1: Double, x2: Double, y2: Double) extends Shape

使ってみる。case classでは自動的に、toStringメソッドが作られるので、REPLにも最初からいい感じで出力される。toStringだけでなく、equals、hashCode、コンストラクタ引数を取得するためのゲッターメソッドも自動生成されている。

scala> val c = Circle(5, 4, 10)
c: Circle = Circle(5.0,4.0,10.0)

scala> c == Circle(5, 4, 10)
res51: Boolean = true

scala> c.r
res52: Double = 10.0

面積を返すメソッドを作ってみる。

sealed trait Shape {
  def area(): Double
}

case class Circle(x: Double, y: Double, r: Double) extends Shape {
  override def area(): Double = Math.PI * r * r
}

case class Rectangle(x1: Double, y1: Double, x2: Double, y2: Double) extends Shape {
  override def area(): Double = Math.abs(x2 - x1) * Math.abs(y2 - y1)
}

使ってみる。

scala> Circle(10, 20, 10).area
res27: Double = 314.1592653589793

scala> Rectangle(0, 0, 100, 100).area
res28: Double = 10000.0

引数がなくて副作用のないメソッドなので、()を省略して、かつdefをvalに置き換えれる。

sealed trait Shape {
  def area: Double
}

case class Circle(x: Double, y: Double, r: Double) extends Shape {
  override val area: Double = Math.PI * r * r
}

case class Rectangle(x1: Double, y1: Double, x2: Double, y2: Double) extends Shape {
  override val area: Double = Math.abs(x2 - x1) * Math.abs(y2 - y1)
}

case classのコンストラクタはメソッド呼び出しといっしょなので、部分適用ができる。

scala> List(4, 5, 6, 6).map(Circle(10, 20, _))
res38: List[Circle] = List(Circle(10.0,20.0,4.0), Circle(10.0,20.0,5.0), Circle(10.0,20.0,6.0), Circle(10.0,20.0,6.0))

Pointデータ型を作る。

case class Point(x: Double, y: Double)

sealed trait Shape {
  def area: Double
}

case class Circle(p: Point, r: Double) extends Shape {
  override val area: Double = Math.PI * r * r
}

case class Rectangle(p1: Point, p2: Point) extends Shape {
  override val area: Double = Math.abs(p2.x - p1.x) * Math.abs(p2.y - p1.y)
}

使ってみる。

scala> Rectangle(Point(0, 0), Point(100, 100)).area
res39: Double = 10000.0

scala> Circle(Point(0, 0), 24).area
res40: Double = 1809.5573684677208

指定したサイズの図形を原点に作るメソッドを作る。図形をつくるメソッドなので図形オブジェクトにはこのメソッドを持たせられない。こういうときはobjectを使う。 クラスやトレイトと同名のobjectをコンパニオンオブジェクトと呼ぶ。コンパニオンオブジェクトは同名のclass, traitと同じファイル内に定義しないといけない。

object Shape {
  def baseCircle(r: Double):Shape = Circle(Point(0, 0), r)
  def baseRect(width: Double, height: Double):Shape = Rectangle(Point(0, 0), Point(width, height))
}

scala> Shape.baseRect(40, 100).nudge(60, 23)
res44: Shape = Rectangle(Point(60.0,23.0),Point(100.0,123.0))

Shapeをモジュールとして考えてみる。info.bati11とpackage名をつける。これを使うスクリプトを書いてみる。

import info.bati11._

object Main {
  def main(args: Array[String]) {
    println(Rectangle(Point(0, 0), Point(100, 100)).area)
  }
}

CircleとRectangleを外部に見せたくない場合はprivateをつける。こうすることで外部からはコンパニオンオブジェクトのbaseCircleメソッド、baseRectメソッド経由以外でShapeオブジェクトをつくれなくなる。

package info.bati11

case class Point(x: Double, y: Double)

sealed trait Shape {
  def area: Double
  def nudge(a: Double, b: Double): Shape
}

private case class Circle(p: Point, r: Double) extends Shape {
  override val area: Double = Math.PI * r * r
  override def nudge(a: Double, b: Double) = Circle(Point(p.x+a, p.y+b), r)
}

private case class Rectangle(p1: Point, p2: Point) extends Shape {
  override val area: Double = Math.abs(p2.x - p1.x) * Math.abs(p2.y - p1.y)
  override def nudge(a: Double, b: Double) = Rectangle(Point(p1.x+a, p1.y+b), Point(p2.x+a, p2.y+b))
}

object Shape {
  def baseCircle(r: Double):Shape = Circle(Point(0, 0), r)
  def baseRect(width: Double, height: Double):Shape = Rectangle(Point(0, 0), Point(width, height))
}

再帰的なデータ構造

二分探索木をcase classで定義してみる。Nodeの定義時に再帰的にTreeを使う。

sealed trait Tree[T]
case class EmptyTree[T]() extends Tree[T]
case class Node[T](v: T, left: Tree[T], right: Tree[T]) extends Tree[T]

EmptyTreeのようにフィールドがない場合、case objectと書いてシングルトンオブジェクトにすることもできる。

要素vを木に挿入するためのメソッドinsertと、値が含まれているかどうかを調べるcontainsメソッドをつくる。 大小比較をしたいので型パラメータをTからT <% Ordered[T]に変更する。

package info.bati11

sealed trait Tree[T] {
  def insert(x: T): Tree[T]
  def contains(x: T): Boolean
}

case class EmptyTree[T <% Ordered[T]]() extends Tree[T] {
  override def insert(x: T): Tree[T] = Node(x, EmptyTree[T](), EmptyTree[T]())
  override def contains(x: T): Boolean = false
}

case class Node[T <% Ordered[T]](v: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def insert(x: T): Tree[T] =
    if (x == v) Node(x, left, right)
    else if(x < v) Node(v, left.insert(x), right)
    else Node(v, left, right.insert(x))

  override def contains(x: T): Boolean =
    if (x == v) true
    else if(x < v) left.contains(x)
    else right.contains(x)
}

scalacしてmainメソッドから使う分には平気なんだけど、REPLで読み込むとエラーになる。なんでかは分かってない。

scala> :lo Tree.scala
Loading Tree.scala...
<console>:1: error: illegal start of definition
       package info.bati11
       ^
defined trait Tree
warning: previously defined object Tree is not a companion to trait Tree.
Companions must be defined together; you may wish to use :paste mode for this.
<console>:18: error: type mismatch;
 found   : EmptyTree[T]
 required: Tree[?]
         override def insert(x: T): Tree[T] = Node(x, EmptyTree[T](), EmptyTree[T]())
                                                                  ^
<console>:18: error: type mismatch;
 found   : EmptyTree[T]
 required: Tree[?]
         override def insert(x: T): Tree[T] = Node(x, EmptyTree[T](), EmptyTree[T]())
                                                                                  ^
defined class Node

YesとNoの型クラス

JavaScriptでは、ifの条件式のところに何でも書くことができる。JavaScriptではこんな風に書いたコードも正常である。

if (0) alert("YEAH!") else alert("NO!")
if ("") alert("YEAH!") else alert("NO!")
if ("WHAT") alert("YEAH!") else alert("NO!")
if (false) alert("YEAH!") else alert("NO!")
if ([2,3,4]) alert("YEAH!") else alert("NO!")

Scalaでは真理値が求められるところに数値や文字列を指定するとコンパイルエラーとなるが、同じように振る舞いを実装してみることにする。

trait YesNo[T] {
  def yesno: Boolean
}

def yesnoIf[T, U](x: YesNo[T], a: U, b: U): U = if (x.yesno) a else b

これで、0やList(2, 3, 4)やtrueがYesNo型のオブジェクトであれば、こんな感じでJavaScriptっぽく振る舞うことができる。

yesnoIf (0, "YEAH!", "NO!")
yesnoIf ("", "YEAH!", "NO!")
yesnoIf ("WHAT", "YEAH!", "NO!")
yesnoIf (false, "YEAH!", "NO!")
yesnoIf (List(2,3,4), "YEAH!", "NO!")

Haskellの型クラスと各型（数値やリスト、真理値）のインスタンスを定義すれば後からそれぞれの型にYesNo型の振る舞いを追加できる。

Scalaでは、traitを継承することで振る舞いを追加できる。しかし、IntはScalaが標準で提供してくれてるクラスであるため、IntがYesNoを継承するようには変えられない。

そこで役立つのがimplicitを使った暗黙のパラメータ（implicit parameter）である。implicit parameterを使うと継承を使わなくても振る舞いを拡張できる。

yesnoIfメソッドを書き換えて、implicit引数で、yesnoメソッドを持つオブジェクトを受け取るようにする。

scala> def yesnoIf[T, U](x: T, a: U, b: U)(implicit yn: YesNo[T]): U = if (yn.yesno(x)) a else b

そして、implicit引数へ渡す値としてimplicitなシングルトンオブジェクトオブジェクトを定義しておく。

trait YesNo[T] {
  def yesno(x: T): Boolean
}

implicit object YesNoInt extends YesNo[Int] {
  override def yesno(x: Int): Boolean = if (x == 0) false else true
}

implicit object YesNoString extends YesNo[String] {
  override def yesno(x: String): Boolean = if (x.size == 0) false else true
}

implicit object YesNoBoolean extends YesNo[Boolean] {
  override def yesno(x: Boolean): Boolean = x
}

あとは上記のimplicitなシングルトンオブジェクトがスコープ内に存在するようにimportしておけば、使える。

scala> :load YesNo.scala

scala> def yesnoIf[T, U](x: T, a: U, b: U)(implicit yn: YesNo[T]): U = if (yn.yesno(x)) a else b
yesnoIf: [T, U](x: T, a: U, b: U)(implicit yn: YesNo[T])U

scala> yesnoIf(0, "YEAH!", "NO!")
res99: String = NO!

scala> yesnoIf("", "YEAH!", "NO!")
res100: String = NO!

scala> yesnoIf("WHAT", "YEAH!", "NO!")
res101: String = YEAH!

scala> yesnoIf(false, "YEAH!", "NO!")
res102: String = NO!

型パラメータを持つリストはどうするのがいいのだろう・・・。Listの場合、型パラメータがとる型によってインスタンスが変わるので、YesNoIntのようにシングルトンオブジェクトにはできない。 シングルトンオブジェクトで対応するとなると各型のListに対応したYesNoオブジェクトをつくることになる・・・。

implicit object YesNoIntList extends YesNo[List[Int]] {
  override def yesno(x: List[Int]): Boolean = if (x.size == 0) false else true
}

implicit object YesNoIntBoolean extends YesNo[List[Boolean]] {
  override def yesno(x: List[Boolean]): Boolean = if (x.size == 0) false else true
}

・・・

これはめんどくさい！

解決方法を模索・・・。 Scalaではimplicit引数へ渡す値を探すときに、スコープ内のimplicitがついた変数やシングルトンオブジェクトだけでなく、同じ型を返すimplicitがついた関数も探してくれる。 それを利用して、型パラメータを解決メソッドをimplicitをつけて定義しておく。

class YesNoList[U] extends YesNo[List[U]] {
  override def yesno(x: List[U]): Boolean = if (x.size == 0) false else true
}
implicit def yesNoList[U]: YesNo[List[U]] = new YesNoList[U]

できた！けど、定石が分からないなぁー。

scala> yesnoIf(List(2,3,4), "YEAH!", "NO!")
res105: String = YEAH!

scala> yesnoIf(List(), "YEAH!", "NO!")
res106: String = NO!

Functor型クラス

Functorは、全体をうつせるものの型クラス。

値を格納する箱のようなクラスはFunctorとしての振る舞いを追加できる。ListとかOptionとか。 Functor[F[_]]は、Funcotorの型パラメータに指定できるのは、「型パラメータを1つもつ型」であるという風に読める。

trait Functor[F[_]] {
  def fmap[A, B](f: A => B, a: F[A]): F[B]
}

implicit object ListFunctor extends Functor[List] {
  override def fmap[A, B](f: A => B, xs: List[A]): List[B] = xs.map(f(_))
}

implicit object OptionFunctor extends Functor[Option] {
  override def fmap[A, B](f: A => B, x: Option[A]): Option[B] = x.match {
    case Some(v) => Some(f(v))
    case _ => None
  }
}

scala> def mymap[A, B, C[A]](f: A => B, xs: C[A])(implicit functor: Functor[C]) = functor.fmap(f, xs)
warning: there were 1 feature warning(s); re-run with -feature for details
mymap: [A, B, C[A]](f: A => B, xs: C[A])(implicit functor: Functor[C])C[B]

scala> mymap((3.+(_:Int)), List(1,2,3))
res11: List[Int] = List(4, 5, 6)

scala> mymap(("hoge".+(_:String)), List("aa", "bb", "cc"))
res12: List[String] = List(hogeaa, hogebb, hogecc)

scala> mymap((3.+(_:Int)), Option(5))
res13: Option[Int] = Some(8)

scala> mymap((3.+(_:Int)), None)
res14: Option[Int] = None

型パラメータを2つとるEitherはどうなるか。

scala> val e: Either[String, Int] = Left("hoge")
e: Either[String,Int] = Left(hoge)

scala> val e: Either[String, Int] = Left(3)
<console>:34: error: type mismatch;
 found   : Int(3)
 required: String
       val e: Either[String, Int] = Left(3)
                                         ^

scala> val e: Either[String, Int] = Right(3)
e: Either[String,Int] = Right(3)

型パラメータに対して部分適用して、型パラメータが1つのEitherを作ってあげれば良い。

type MyEither[X] = Either[_, X]
class EitherFunctor extends Functor[MyEither] {
  override def fmap[A, B](f: A => B, x: MyEither[A]): MyEither[B] = x match {
    case Left(v) => Left(v)
    case Right(v) => Right(f(v))
  }
}
implicit def eitherFunctor: Functor[MyEither] = new EitherFunctor

これだと単純にRight(5)だとエラーになってしまう。。型を明示的に指定すれば大丈夫だけど。。。

scala> mymap((3.+(_:Int)), Right(5))
<console>:140: error: no type parameters for method mymap: (f: A => B, xs: C[A])(implicit functor: Functor[C])C[B] exist
 so that it can be applied to arguments (Int => Int, scala.util.Right[Nothing,Int])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : scala.util.Right[Nothing,Int]
 required: ?C[?A]
              mymap((3.+(_:Int)), Right(5))
              ^
<console>:140: error: type mismatch;
 found   : Int => Int
 required: A => B
              mymap((3.+(_:Int)), Right(5))
                        ^
<console>:140: error: type mismatch;
 found   : scala.util.Right[Nothing,Int]
 required: C[A]
              mymap((3.+(_:Int)), Right(5))
                                       ^

scala> mymap((3.+(_:Int)), Right(5): MyEither[Int])
res38: MyEither[Int] = Right(8)

scala> mymap((3.+(_:Int)), Left("hoge"): MyEither[Int])
res39: MyEither[Int] = Left(hoge)

09.md

ToDoリスト

import java.nio.file._
import java.io._
import scala.io._

object Todo {
  def main(args: Array[String]) {
    args.toList match {
      case "add" :: xs => add(xs)
      case "view" :: xs => view(xs)
      case "remove" :: xs => remove(xs)
      case command :: _ => println "The " + command + " command doesn't exist"
    }
  }

  val add = (args: List[String]) => args match {
    case List(fileName, todoItem) => {
      using(Files.newBufferedWriter(FileSystems.getDefault().getPath(fileName), StandardOpenOption.APPEND)) {
        _.write(todoItem + "\n")
      }
    }
    case _ => println "The add command takes exactly two arguments"
  }

  val view = (args: List[String]) => args match {
    case List(fileName) => {
      val source = Source.fromFile(fileName)
      val todoTasks = source.getLines
      val numberedTasks = todoTasks.zipWithIndex.map { case (line, n) => n.toString + " - " + line }
      numberedTasks.foreach(println(_))
    }
    case _ => println "The add command takes exactly one argument"
  }

  val remove = (args: List[String]) => args match {
    case List(fileName, numberString) => {
      val source = Source.fromFile(fileName)
      val todoTasks = source.getLines.toList
      val numberedTasks = todoTasks.zipWithIndex.map { case (line, n) => n.toString + " - " + line }
      println("These ae your TO-DO items:")
      numberedTasks.foreach(println(_))
      val newTodoItems = todoTasks.toList.splitAt(numberString.toInt) match { case (a, b) => a ++ b.tail }
      val temp = Files.createTempFile(FileSystems.getDefault().getPath("."), "temp", "txt")
      try {
        using(Files.newBufferedWriter(temp, StandardOpenOption.APPEND)) { writer: BufferedWriter =>
          newTodoItems.foreach(s => writer.write(s + "\n"))
          Files.delete(FileSystems.getDefault().getPath(fileName))
          Files.move(temp, FileSystems.getDefault().getPath(fileName))
        }
      } catch {
        case _ => Files.delete(temp)
      }
    }
    case _ => println "The add command takes exactly two arguments"
  }

  private def using[A <% java.io.Closeable](s: A)(f: A=>Any) {
    try f(s) finally s.close()
  }
}

10.md

逆ポーランド記法電卓

def solveRPN(expression: String): Double = expression.split(" ").foldLeft(List[Double]()) {
  case (x :: y :: ys, "*") => (y * x) :: ys
  case (x :: y :: ys, "+") => (y + x) :: ys
  case (x :: y :: ys, "-") => (y - x) :: ys
  case (x :: y :: ys, "/") => (y / x) :: ys
  case (x :: y :: ys, "^") => (Math.pow(x, y)) :: ys
  case (x :: xs, "ln") => (Math.log(x)) :: xs
  case (xs, "sum") => List(xs.sum)
  case (xs, numberString) => numberString.toDouble :: xs
}.head

11.md

もう1回ファンクター

ファンクターは関数で写せるもののこと。リストとかOptionとか。値を入れておける箱のようなもの。

別の見方もできる。

別の見方もできる。

ファンクターは、文脈を持った値だとみなすこともできます。例えば、Maybe値は「計算が失敗したかもしれない」という文脈を、リストは「複数の値を同時にとるかもしれない」という文脈を持ちます。fmapは、こういった文脈を保ったまま関数を値に適用するのです。

文脈！なんかしっくりくる！

ファンクタートレイトを継承するには、型パラメータを1つだけ持つクラスにする必要があった。ListやOptionはそのままで良いけど、Eitherは部分適用する必要があった。

実は関数型もファンクターである。Scalaでは、引数を1つとって1つ値を返す関数リテラル（例えば (x: Int) => 2 *x）は、Function1トレイトをインスタンス化する糖衣構文。 Function1トレイトは、引数の型と返り値の型、2つの型パラメータをとる。そのためファンクターとするには部分適用する必要がある。

trait Functor[F[_]] {
  def fmap[A, B](f: A => B, a: F[A]): F[B]
}

type MyFunc[Y] = Function1[_, Y]
class FunctionFunctor extends Functor[MyFunc] {
  override def fmap[A, B](f: A => B, g: MyFunc[A]): MyFunc[B] = f.compose(g)
}
implicit def functionFunctor: Functor[MyFunc] = new FunctionFunctor

def fmap[A, B, F[A]](f: A => B, xs: F[A])(implicit functor: Functor[F]): F[B] = functor.fmap(f, xs)

関数f(x)、つまり「fという関数を適用する」という文脈を保ったまま、別の関数gをを適用することになるので、f(g(x))になり、これは関数合成と同じことになる。
上の実装で試したら思ったようにエラーになってしまう・・・。未解決・・・。

scala> val f: MyFunc[Int] = 2.*(_:Int)
f: MyFunc[Int] = <function1>

scala> val g = 10.+(_:Int)
g: Int => Int = <function1>

scala> fmap(g: Int => Int, f: MyFunc[Int])
<console>:156: error: no type parameters for method fmap: (f: A => B, xs: F[A])(implicit functor: Functor[F])F[B] exist so that it can be applied to arguments (Int => Int, _$1 => Int)
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : _$1 => Int where type _$1
 required: ?F[?A]
              fmap(g: Int => Int, f: MyFunc[Int])
              ^
<console>:156: error: type mismatch;
 found   : Int => Int
 required: A => B
              fmap(g: Int => Int, f: MyFunc[Int])
                    ^
<console>:156: error: type mismatch;
 found   : _$1 => Int where type _$1
 required: F[A]
              fmap(g: Int => Int, f: MyFunc[Int])
                                   ^

定義したfmapをもう1回見てみる。

def fmap[A, B, C[A]](f: A => B, xs: C[A])(implicit functor: Functor[C]) = functor.fmap(f, xs)

fmapに部分適用してみる。

scala> val f = 2.+(_:Int)
f: Int => Int = <function1>

scala> fmap(f, _: List[Int])
res27: List[Int] => List[Int] = <function1>

Int => Intという関数を引数にとり、List[Int] => List[Int]を返す関数を返却した。 これは、A => Bという関数を引数にとり、Functor[Int] => Functor[Int]を返したということになる。こういう操作を、関数の持ち上げ（lifing）をいう。

fmapについては2通りの考え方ができます。

• fmapは関数とファンクター値を取って、その関数でファンクター値を写して返すものである。
• fmapは値から値への関数を取って、それをファンクター値からファンクター値への関数に持ち上げたものを返す関数である。

そして、どちらの見方も正しいのです。「関数でファンクター値を写す」ことと、「関数を持ち上げてからファンクター値に適用する」ことは等価です。

ファンクター則

ファンクターは関数を適用する以外のことをしてはいけない。 すべてのファンクターは、ファンクター則に従う。自分でファンクターを実装する場合も従う必要がある。 ファンクター則は2つ。

第一の法則は、「idでファンクター値を写した場合、ファンクター値が変化してはいけない」というものです。式で書くと fmap id = id ってことです。別の言い方をすれば、fmap id をファンクター値に適用した場合、それは id をファンクター値に適用したのと同じ結果になる、ということです。

scalaではPredefにidentityメソッドがあり、これがHaskellのid関数と同じ動きをする。

scala> identity(Option(3))
res35: Option[Int] = Some(3)

scala> fmap(identity(_: Int), Option(3))
res36: Option[Int] = Some(3)

scala> identity(List(1,2,3,4,5))
res37: List[Int] = List(1, 2, 3, 4, 5)

scala> fmap(identity(_: Int), List(1,2,3,4,5))
res38: List[Int] = List(1, 2, 3, 4, 5)

scala> identity(List[Int]())
res39: List[Int] = List()

scala> fmap(identity(_: Int), List[Int]())
res40: List[Int] = List()

第二法則は、関数合成と写す操作と間の関係です。第二法則は、2つの関数 f と g について、「f と g の合成関数でファンクター値を写したもの」と「まず g、次に f でファンクター値を写したもの」が等しいことを要求します。

scala> fmap((100.+(_:Int)).compose(2.*(_:Int)), List(1,2,3,4,5))
res45: List[Int] = List(102, 104, 106, 108, 110)

scala> fmap(100.+(_:Int), fmap(2.*(_:Int), List(1,2,3,4,5)))
res46: List[Int] = List(102, 104, 106, 108, 110)

もしある型がファンクター則を両方とも満たすと分かれば、その型の挙動についてある種の信頼がおけます。fmapを使っても、その関数でファンクター値の「中身」が写されるだけで、それ以外のことは何もおこらないと確信できるのです。この前提のおかげで、より抽象的で応用の利くコードが書けます。すべてのファンクターが満たしているはずの法則を根拠に、どんなファンクターに適用しても間違いなく動作する関数を作れるからです。

ScalaのコレクションやOptionは、mapメソッドを使って中に入ってる値を写すことができる。が、ファンクターという型クラスがあるわけではなく、またファンクター則に従ってるか分からないので、mapメソッドがあるからといってファンクターであるとは限らない。

アプリカティブファンクター

ファンクターの強化版であるアプリカティブファンクターについて。

値として関数を持つファンクターを考えてみる。例えばOption(3.+(_:Int))みたいなやつ。これと普通のファンクター値Option(5)があったとして、Option(3.+(_:Int))から関数を取り出して、Option(5)の中身に適用したい場合はどうするか。これは普通のファンクターでは実現できない。

ファンクターは、通常の関数でファンクターの中の値に適用して写す。ファンクターの中にある関数をファンクターの中の値に適用して写すことはできない。

これをできるようにするのがアプリカティブ。アプリカティブはファンクターでないと継承できない。なぜならfmapを使いたいから？

pureメソッドは、普通の値をアプリカティブの中に入れて返す。 <*>メソッドは、アプリカティブの中にある関数を、アプリカティブの中にある値に適用して写す。

Optionはアプリカティブなので、implicitでアプリカティブになるように拡張してみる。

trait Functor[F[_]] {
  def fmap[A, B](f: A => B, a: F[A]): F[B]
}

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](x: A): F[A]
  def <*>[A, B](f: F[A => B], x: F[A]): F[B]
}

implicit object OptionApplicativeFunctor extends Functor[Option] with Applicative[Option] {
  override def fmap[A, B](f: A => B, x: Option[A]): Option[B] = x match {
    case Some(v) => Some(f(v))
    case _ => None
  }
  override def pure[A](x: A): Option[A] = Option(x)
  override def <*>[A, B](f: Option[A => B], x: Option[A]): Option[B] = f match {
    case None => None
    case Some(fx) => fmap(fx, x)
  }
}

def pure[A, F[A]](x: A)(implicit applicative: Applicative[F]): F[A] = applicative.pure(x)
def <*>[A, B, F[A]](f: F[A => B], x: F[A])(implicit applicative: Applicative[F]): F[B] = applicative.<*>(f, x)

使ってみる。

scala> <*>(Option(plus3), Option(9))
res65: Option[Int] = Some(12)

scala> <*>(pure(plus3), Option(10))
res66: Option[Int] = Some(13)

scala> <*>(Option("hahaha".+(_:String)), None)
res68: Option[String] = None

scala> <*>(Option("hahaha".+(_:String)), Option("woot"))
res69: Option[String] = Some(hahahawoot)

scala> <*>(None: Option[Int => Int], Option(9))
res70: Option[Int] = None

Haskellでは<*>を複数組み合わせて使うことができる。これをアプリカティブスタイルと呼ぶみたい。

pure (+) <*> Just 3 <*> Just 5

さっきScalaで定義したやつだと、<*>が受け取れる関数はA => Bという型なので、2引数を取る関数を受け取ることができない。

scala> val pow = Math.pow(_, _)
pow: (Double, Double) => Double = <function2>

scala> <*>(pure(pow), Option(2.0))
<console>:66: error: no type parameters for method <*>: (f: F[A => B], x: F[A])(implicit applicative: Applicative[F])F[B] exist so that it can be applied to arguments (Option[(Double, Double) => Double], Option[Int])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : Option[(Double, Double) => Double]
 required: ?F[?A => ?B]
              <*>(pure(pow), Option(3))
              ^
<console>:66: error: type mismatch;
 found   : Option[(Double, Double) => Double]
 required: F[A => B]
              <*>(pure(pow), Option(3))
                      ^
<console>:66: error: type mismatch;
 found   : Option[Int]
 required: F[A]
              <*>(pure(pow), Option(3))
                                   ^
<console>:66: error: could not find implicit value for parameter applicative: Applicative[F]
              <*>(pure(pow), Option(3))
                 ^

なんでHaskellだとうまくできるんだろう。たぶん関数が全てカリー化された関数になっているからかな。2引数をとる関数でも実際は1引数をとって1引数をとる関数を返す。だからA => Bという型にも2引数をとる関数を渡せる。ということは、Scalaでも関数型のcurriedと使ってから渡せば動くのでは！？

scala> pure(pow.curried)
res23: Option[Double => (Double => Double)] = Some(<function1>)

scala> <*>(pure(pow.curried), Option(3.0))
res24: Option[Double => Double] = Some(<function1>)

scala> <*>(<*>(pure(pow.curried), Option(2.0)), Option(4.0))
res25: Option[Double] = Some(16.0)

動いた！定義した<*>メソッドは演算子のように使えるようになってないから、スマートではないですが・・・。

リストもアプリカティブになれる。

implicit object ListApplicativeFunctor extends Functor[List] with Applicative[List] {
  override def fmap[A, B](f: A => B, xs: List[A]): List[B] = xs.map(f(_))
  override def pure[A](x: A): List[A] = List(x)
  override def <*>[A, B](fs: List[A => B], xs: List[A]): List[B] = for(f <- fs; x <- xs) yield f(x)
}

使ってみる。pureは値をとってデフォルトの文脈の中に入れるもの。

scala> pure("Hey")
<console>:144: error: ambiguous implicit values:
 both object ListApplicativeFunctor of type ListApplicativeFunctor.type
 and object OptionApplicativeFunctor of type OptionApplicativeFunctor.type
 match expected type Applicative[F]
              pure("Hey")
                  ^

implicitパラメータとしてListApplicativeFunctorを使えばいいのか、OptionApplicativeFunctorを使えばいいのか分からない。 Listの文脈に入れるのかOptionの文脈に入れるのかが決められない状態。 どちらかのみをimportするか、明示的に指定するか、どちらかで対応する。

scala> pure("Hey")(ListApplicativeFunctor)
res31: List[String] = List(Hey)

<*>を使ってみる。

scala> <*>(List(0.*(_:Int), 100.+(_:Int), 2.*(_:Int)), List(1, 2, 3))
res32: List[Int] = List(0, 0, 0, 101, 102, 103, 2, 4, 6)

<*>を使うと、for内包表記をうまく置き換えられることがある。

scala> for (x <- List(2.0, 10.0, 100.0); y <- List(2.0, 3.0, 4.0)) yield Math.pow(x, y)
res45: List[Double] = List(4.0, 8.0, 16.0, 100.0, 1000.0, 10000.0, 10000.0, 1000000.0, 1.0E8)

scala> <*>(<*>(pure(pow.curried)(ListApplicativeFunctor), List(2.0, 10.0, 100.0)), List(2.0, 3.0, 4.0))
res46: List[Double] = List(4.0, 8.0, 16.0, 100.0, 1000.0, 10000.0, 10000.0, 1000000.0, 1.0E8)

普通のファンクターのようにアプリカティブファンクターにもいくつかの法則、アプリカティブ則がある。 アプリカティブ則は4つある。

pure id <*> v = v

id関数をアプリカティブの中にいれて、<*>でアプリカティブに適用すると、何も変わらないアプリカティブが返ってくる。

scala> <*>(pure(identity(_:Int))(OptionApplicativeFunctor), Option(3))
res51: Option[Int] = Some(3)

pure (.) <> u <> v <> w = u <> (v <*> w)

fとgを関数結合した関数をアプリカティブの中に入れて<>でアプリカティブに適用した結果と、gをアプリカティブ値にして<>でアプリカティブに適用してからfをアプリカティブ値にして<*>でアプリカティブあに適用した結果が等しくなる。

scala> <*>(pure((100.+(_:Int)).compose(2.*(_:Int)))(ListApplicativeFunctor), List(1,2,3,4,5))
res53: List[Int] = List(102, 104, 106, 108, 110)

scala> <*>(pure(100.+(_:Int))(ListApplicativeFunctor), <*>(pure(2.*(_:Int))(ListApplicativeFunctor), List(1,2,3,4,5)))
res55: List[Int] = List(102, 104, 106, 108, 110)

pure f <*> pure x = pure (f x)

fをアプリカティブの中に入れてから、xを入れたアプリカティブに適用した結果と、fをxに適用してからアプリカティブの中に入れた結果が等しくなる。

scala> <*>(pure(100.+(_:Int))(ListApplicativeFunctor), pure(2)(ListApplicativeFunctor))
res60: List[Int] = List(102)

scala> pure(100.+(2))(ListApplicativeFunctor)
res63: List[Int] = List(102)

u <> pure y = pure ($ y) <> u

これはScalaで書いたやつだとどうやって表現したらいいのかなー・・・。

アプリカティブの便利な関数

「アプリカティブ値のリスト」を取って「リストを返り値として持つ1つのアプリカティブ値」を返す関数を実装してみる。

Optionだけに対応したもの。

def concat[T](x: T, xs: List[T]): List[T] = x :: xs
def sequenceA[T](as: List[Option[T]]): Option[List[T]] = as match {
  case List() => pure(List())(OptionApplicativeFunctor)
  case x :: xs => {
    val f = (concat(_: T, _: List[T])).curried
    val applicative = fmap(f, x)(OptionApplicativeFunctor)
    <*>(applicative, sequenceA(xs))
  }
}

使ってみる。

scala> sequenceA(List(Some(2), Some(3)))
res165: Option[List[Int]] = Some(List(2, 3))

アプリカティブであればsequenceA関数がやったように、アプリカティブ値のリストを、リストを持ってるアプリカティブ値に変えることができる。

例えばHaskellでは関数もアプリカティブなので以下のようなこともできる。

関数のリストがあり、そのすべての要素に同じ引数を食わせて結果をリストとして眺めたい

ScalaのFutureのコンパニオンオブジェクトに、sequenceAに相当するsequenceメソッドが定義されている。他にもあるのかな。

12.md

Monoid

Intオブジェクトの*メソッドを考えてみる。これはメソッドの持ち主である数と引数の数をかけ算する。どちらかが1である場合は、結果はもう一方の値になる。1 * xもx * 1も結果はxになる。次に、Listの++メソッドを考えてみる。これはメソッドの持ち主であるリストと引数のリストを結合する。どちらかが空リストである場合は、結果はもう一方のリストになる。

scala> 4 * 1
res7: Int = 4

scala> 1 * 9
res8: Int = 9

scala> List(1,2,3) ++ List()
res9: List[Int] = List(1, 2, 3)

scala> List() ++ List(0.5, 2.5)
res10: List[Double] = List(0.5, 2.5)

*に1という組み合わせと、++にList()という組み合わせは、共通の性質を持っている。

• 2つの値を演算する
• 2つの値と返り値の型はすべて等しい
• 2つの値を演算しても相手を変えないような特殊な値（1とかList()）が存在する

他にも計算の結合順序を変えても結果が変わらないという性質もある。

scala> (3 * 2) * (8* 5)
res1: Int = 240

scala> 3 * (2 * (8 * 5))
res2: Int = 240

scala> List(1,2) ++ (List(3,4) ++ List(5,6))
res3: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> (List(1,2) ++ List(3,4) ++ List(5,6))
res4: List[Int] = List(1, 2, 3, 4, 5, 6)

これら共通の性質をもったものを抽象化できそう。HaskellにはMonoidという型クラスがある。

モノイドは、結合的な二項演算子（2引数関数）と、その演算に関する単位元からなる構造です。

結合的ってのは、計算の順番を変えても結果が変わらないという意味。

単位元は、ある値と単位元とで演算を行っても結果がある値のままであるようなもの。例えば*であれば0、++であればList()。

Monoid型クラスをScalaで実装してみる。

trait Monoid[M] {
  def mempty: M
  def mappend(m1: M, m2: M): M
  def mconcat(ms: List[M]): M = ms.foldRight(mempty _)(mappend)
}

Monoidのインスタンスになれるのは、具体型（型パラメータを取らない型）だけである。Monoid[M]なので。Functorの場合はFunctor[F[_]]となっていたので型パラメータが1つの型がFunctorのインスタンスになれた。

memptyは単位元を返す。

mappendは二項演算子（2引数関数）を返す。

mconcatはモノイドのリストを取ってmappendを間に挟んだ式を作り、単一の値を計算する関数。mconcatにはデフォルト実装がある。ほとんどのモノイドはこの実装で十分。

FuncotrやApllicativeと同様にMonoid則がある。

• mempty mappend x = x
• x mappend mempty = x
• (x mappend y) mappend z = z mappend (y mappend z)

はじめの2つの法則は、mempty が mappend に関して単位元として振る舞う必要があることを述べています。第三の法則は、mappend が結合的であること、つまり複数の mappend で連結された式から1つの値を計算するとき、mappend を評価する順序は最終結果に影響しないことを述べています。

モノイドのインスタンス

リストはモノイド。

trait Monoid[M] {
  def mempty: M
  def mappend(m1: M, m2: M): M
  def mconcat(ms: List[M]): M = ms.foldRight(mempty)(mappend)
}

class ListMonoid[T] extends Monoid[List[T]] {
  def mempty:List[T] = List[T]()
  def mappend(m1: List[T], m2: List[T]): List[T] = m1 ++ m2
}
implicit def listMonoid[T]: Monoid[List[T]] = new ListMonoid[T]

def mempty[M](implicit monoid: Monoid[M]): M = monoid.mempty
def mappend[M](m1: M, m2: M)(implicit monoid: Monoid[M]): M = monoid.mappend(m1, m2)

使ってみる。

scala> mappend(List(1,2,3), List(4,5,6))
res12: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> mappend(mappend(List(1), List(2)), List(3))
res14: List[Int] = List(1, 2, 3)

scala> mappend(List(1,2,3), mempty)
res16: List[Int] = List(1, 2, 3)

scala> mconcat(List(List(1,2,3), List(4,5,6), List(7,8,9)))
res18: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

数値も*と1でモノイドになる。もう1つの方法があって+と0を使う方法もある。こういう場合は2つの型を新たにつくってしまえばいい。

case class Product(x: Int)
case class Sum(x: Int)

implicit object ProductMonoid extends Monoid[Product] {
  def mempty: Product = Product(1)
  def mappend(m1: Product, m2: Product): Product = Product(m1.x * m2.x)
}

implicit object SumMonoid extends Monoid[Sum] {
  def mempty: Sum = Sum(0)
  def mappend(m1: Sum, m2: Sum): Sum = Sum(m1.x + m2.x)
}

使ってみる。

scala> mappend(Product(3), Product(9))
res24: Product = Product(27)

scala> mappend(Product(3), mempty(ProductMonoid))
res25: Product = Product(3)

scala> mappend(mappend(Product(3), Product(4)), Product(2))
res26: Product = Product(24)

scala> mconcat(List(3,4,2).map(Product(_)))
res27: Product = Product(24)

scala> mappend(Sum(2), Sum(9))
res29: Sum = Sum(11)

scala> mappend(mempty(SumMonoid), Sum(3))
res30: Sum = Sum(3)

scala> mconcat(List(3,4,2).map(Sum(_)))
res31: Sum = Sum(9)

Booleanもモノイドにする方法が2通り考えられる。

• ||をモノイド演算とし、falseを単位元とする方法
• &&をモノイド演算とし、trueを単位元とする方法

前者をAny、後者をAllという型で実装してみる。

scala> mappend(Any(true), Any(false))
res32: Any = Any(true)

scala> mappend(mempty(AnyMonoid), Any(false))
res33: Any = Any(false)

scala> mappend(mempty(AnyMonoid), Any(true))
res34: Any = Any(true)

scala> mconcat(List(false, false, false, true).map(Any(_)))
res35: Any = Any(true)

scala> mappend(mempty(AllMonoid), All(true))
res36: All = All(true)

scala> mappend(mempty(AllMonoid), All(false))
res37: All = All(false)

scala> mconcat(List(true, true, true).map(All(_)))
res38: All = All(true)

scala> mconcat(List(true, true, false).map(All(_)))
res39: All = All(false)

Optionも複数の方法でモノイドになれる。Optionの中に入れる値をMonoidに限定したいが多相にするのがちょっと大変そうなので、とりあえずSumに対応したもの・・・。

implicit object OptionMonoid extends Monoid[Option[Sum]] {
  def mempty: Option[Sum] = None
  def mappend(m1: Option[Sum], m2: Option[Sum]): Option[Sum] = (m1, m2) match {
    case (None, m) => m
    case (m, None) => m
    case (Some(v1), Some(v2)) => Some(SumMonoid.mappend(v1, v2))
  }
}

使ってみる。

scala> mappend(None, Some(Sum(3)))
res40: Option[Sum] = Some(Sum(3))

scala> mappend(Some(Sum(5)), None)
res41: Option[Sum] = Some(Sum(5))

scala> mappend(Option(Sum(3)), Option(Sum(5)))
res42: Option[Sum] = Some(Sum(8))

失敗するかもしれない計算の返り値をモノイドとして扱いたい場合に便利です。このインスタンスがあるおかげで、個々の計算が失敗したかどうかをいちいち覗き込まずに済みます。Nothing か Just かの判定などせずに、そのまま普通のモノイドとして扱ってやればよいのです。

たしかにいちいちOptionから取り出し、Noneかどうかを判定しなくても、モノイドのまま計算を進めれるのは楽だ！

13.md

モナド

第7章で初めてファンクターの話をしたとき、ファンクターは関数で写せる値を表す便利な概念であることを見ました。第11章ではファンクターを一歩拡張してアプリカティブファンクターを導入し、ある種のデータ型は、文脈を持った値だと解釈できるようになりました。アプリカティブファンクターを使えば、そのような文脈を保ったまま、通常の関数をそれらの値に適用できるのでした。

モナドは強化されたアプリカティブファンクターである。

ファンクターを導入したことで、fmapにより、文脈を持った値を関数で写すことができるようになった。関数が始めからファンクターに包まれていた場合に対応するためアプリカティブを導入し、<*>で文脈に包まれた関数を文脈につつまれた値に適用できるようになった。また、アプリカティブのpureにより通常の値を文脈で包めるようにもなった。文脈の中から値や関数を取り出したりしなくても計算ができるようになった、ということ。

さらに、モナドの導入によってできることがある。

モナドはある願いを叶えるための、アプリカティブ値の自然な拡張です。その願いとは、「普通の値 a を取って文脈付きの値を返す関数に、文脈付きの値 m a を渡したい」というものです。言い換えると、a -> m b 型の関数を m a 型の値に適用したい、ということ。ぶっちゃけると、この関数が欲しいってことです。

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

>>=はバインド（bind）と呼ばれる。モナドはバインドをサポートするアプリカティブファンクターである。

普通の関数（A => B）を普通の値（A）に適用するのは、ただの関数適用。普通の関数（A => B）を文脈で包んだ値（F[A]）に適用するにはファンクターのfmapを使う（Scalaだとmapメソッド）。文脈で包んだ関数（F[A => B]）を文脈で包んだ値（F[A]）に適用するにはアプリカティブの<*>を使う（ScalaだとflatMapメソッド）。普通の値を取って文脈で包んだ別の値を返す関数（A => F[B]）を文脈で包んだ値（F[A]）に適用するにはモナドの>>=を使う、ということになるのか。

モナドとしてのOption

Optionはモナドのように使える。

ファンクターとしての振る舞いを思い出す。

scala> fmap(3.+(_:Int), Option(3))
res45: Option[Int] = Some(6)

scala> fmap(3.+(_:Int), None)
res46: Option[Int] = None

アプリカティブファンクターとしての振る舞いを思い出す。

scala> <*>(Option(3.+(_:Int)), Option(3))
res47: Option[Int] = Some(6)

scala> <*>(None: Option[Int=>Int], Option(3))
res48: Option[Int] = None

Optionにおける>>=を考えてみる。関数の型は(Option[T], T => Option[U]) => Option[U]という感じになるはず。

まずは(T, T => Option[U]) => Option[U]という関数を考える。

scala> def hoge[T, U](x: T, f: T => Option[U]): Option[U] = f(x)
hoge: [T, U](x: T, f: T => Option[U])Option[U]

scala> hoge(10, ((x: Int) => Option(x + 10)))
res56: Option[Int] = Some(20)

scala> hoge(10, ((x: Int) => Option(x + "!")))
res57: Option[String] = Some(10!)

これを(Option[T], T => Option[U]) => Option[U]にしたものが>>=になる。

scala> def >>=[T, U](x: Option[T], f: T => Option[U]): Option[U] = x match {
     |   case None => None
     |   case Some(v) => f(v)
     | }
$greater$greater$eq: [T, U](x: Option[T], f: T => Option[U])Option[U]

scala> >>=(Option(10), ((x: Int) => Option(x + 10)))
res59: Option[Int] = Some(20)

scala> >>=(Option(10), ((x: Int) => Option(x + "!")))
res60: Option[String] = Some(10!)

ScalaにはMonadクラスはない。しかし、ListやOptionには、>>=に相当するflatMapメソッドがある。例えばOption[A]のflatMapメソッドの型はflatMap[B](f: (A) => Option[B]: Option[B]であり、さっき定義した>>=に相当する。

綱渡り

綱渡りを題材にプログラミング。

ピエールは綱渡りをする。バランス棒を持ちながら綱渡りをするが、バランス棒に鳥が止まってしまう。バランス棒の左右に止まった鳥の数が同じくらいなら大丈夫だけど、片方に偏るとピエールはバランスを崩して綱から落ちてしまう。左右の鳥の数の差が3以内であればピエールはバランスを取れる。

鳥の数とバランス棒をtypeを使って表現する。バランス棒の左と右に鳥が止まる関数を定義する。

type Birds = Int

case Pole(left: Birds, right: Birds) {
  def landLeft(n: Birds): Pole = (left + n, right)
  def landRight(n: Birds): Pole = (left, right + n)
}

使ってみる。

scala> Pole(0, 0).landLeft(2)
res68: Pole = Pole(2,0)

scala> Pole(1, 2).landRight(1)
res69: Pole = Pole(1,3)

scala> Pole(1, 2).landRight(-1)
res70: Pole = Pole(1,1)

鳥が飛び立つ場合は、負の数の鳥がとまる処理で代用する。

landLeftとlandRightは、Poleを返すので好きなだけメソッド呼び出しをつなげられる。

scala> Pole(0, 0).landLeft(1).landRight(1).landLeft(2)
res71: Pole = Pole(3,1)

片方に一気に10羽の鳥が来たら、綱から落ちる。

scala> Pole(0, 3).landLeft(10)
res72: Pole = Pole(10,3)

こういう順番で鳥が来たらどうか？

scala> Pole(0, 0).landLeft(1).landRight(4).landLeft(-1).landRight(-2)
res73: Pole = Pole(0,2)

最終結果だけ見ると左右の差は2なのでピエールは綱から落ちなくて済みそうだけど、実は最後から2番目に鳥が飛び立ったタイミングで左右の差が4になっている。なので綱渡りは失敗するはず。

このことを考慮に入れてlandLeftとlandRightを書き直す。鳥が偏ってバランスを崩したときは失敗したことにしたい。失敗するかもしれない文脈を取り込みたいのでOptionを使う！

type Birds = Int

case class Pole(left: Birds, right: Birds) {
  def landLeft(n: Birds): Option[Pole] =
    if (Math.abs((left + n) - right) < 4) Some(Pole(left + n, right))
    else None

  def landRight(n: Birds): Option[Pole] =
    if (Math.abs(left - (right + n)) < 4) Some(Pole(left, right + n))
    else None
}

使ってみる。

scala> Pole(0, 0).landLeft(2)
res77: Option[Pole] = Some(Pole(2,0))

scala> Pole(0, 3).landLeft(10)
res78: Option[Pole] = None

これでバランスを崩して綱渡りに失敗したときにNoneが返るようになった！

しかし、landLeft, landRightメソッドの返り値がPoleからOptionになってしまったので、Pole(0, 0).landLeft(1).landRight(4)っていうようにつなげて書けなくなってしまった。

ここで役に立つのがバインド（>>=）、Scalaで言うとflatMap。

scala> Pole(0, 0).landLeft(1).flatMap(x => x.landRight(4)).flatMap(x => x.landLeft(-1)).flatMap(x => x.landRight(-2))
res82: Option[Pole] = None

できた！

_を使えばちょっと短く書ける。

scala> Pole(0, 0).landLeft(1).flatMap(_.landRight(4)).flatMap(_.landLeft(-1)).flatMap(_.landRight(-2))
res83: Option[Pole] = None

失敗するかもしれないという文脈を計算結果に追加したいのでlandLeft,landRightと結果をOptionで包むことにした。Optionで包んだことによりOptionの中に包まれてしまったPoleのメソッドをつなげることができなくなってしまった。しかし、包んだ文脈がモナドであれば、つまりバインド（flatMap）をサポートしていれば、それを使って文脈を保ったまま計算をつなげることができる。

文脈を保ったままというのがポイントな気がする。Optionで包んだまま計算をつなげることができ、途中でNoneが挟まっても気にすることなく処理をつなげることができる。間に1つでもNoneがあれば計算全体の結果がNoneとなる。

これはOptionをアプリカティブ値として扱うだけでは不可能だったこと。

flatMapを使わずに実装したらどうなったか。計算の結果が成功か失敗かを毎回考える必要があったはず。

def routine: Option[Pole] = this.landLeft(1) match {
  case None => None
  case Some(pole1) => pole1.landRight(4) match {
    case None => None
    case Some(pole2) => pole2.landLeft(-1) match {
      case None => None
      case Some(pole3) => pole3.landRight(-2)
    }
  }
}

OptionとflatMapを使うと、失敗するかもしれない処理が連続するコードをとても簡潔に書ける。

リストモナド

リストはモナド。

第11章では、アプリカティブとしてのリストは非決定性計算を表すといいました。

リストをアプリカティブスタイルで使うと、非決定性を表現していることがはっきりします。

ghci> () <$> [1,2,3] <> [10,100,1000] [10,100,1000,20,200,2000,30,300,3000]

左辺リストの要素と右辺リストの要素の、すべてのあり得る組み合わせの積が、答のリストに含まれています。非決定性計算ではたくさんの選択肢に出くわしますが、その都度すべてを試します。すると、最終結果はもっとたくさんの候補値を含んだ非決定的値になるわけです。

うーん。非決定計算というものがよく分からんなぁ。計算のパラメータの取りうる値がたくさんありますよーってことでいいんだろうか・・・。

とりあえず、この非決定計算という文脈は、モナドで表現できる。

Scalaのリストでもバインド、つまりflatMapメソッドが使える。

scala> List(3,4,5).flatMap(x => List(x, -x))
res86: List[Int] = List(3, -3, 4, -4, 5, -5)

OptionのflatMapを使うと、失敗の可能性を考慮しながら、モナド値（Optionの中の値）を関数に供給できる。Listの例だとモナドが非決定性計算を処理してくれる。

非決定性計算は、失敗する可能性のある計算の上位互換。失敗は返すべき値が何もないということ、空リストで表現する。

scala> List().flatMap(x => List("bad", "mad", "rad"))
res87: List[String] = List()

scala> List(1,2,3).flatMap(x => List())
res88: List[Nothing] = List()

flatMapを入れ子で使ったり。

scala> List(1,2).flatMap(n => List('a', 'b').flatMap(ch => List((n, ch))))
res97: List[(Int, Char)] = List((1,a), (1,b), (2,a), (2,b))

Haskellだと入れ子、というか連結して書ける。Scalaだと入れ子にしないとnがスコープ外になってしまって見れない。

> [1,2] >>= \n -> ['a', 'b'] >>= \ch -> return (n, ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

この入れ子のコード、for式に似てる。出力パートではyeildを使っていてList((n, ch))ではなく、(n, ch)になっていることに注意。

scala> for (n <- List(1,2); ch <- List('a', 'b')) yield (n, ch)
res98: List[(Int, Char)] = List((1,a), (1,b), (2,a), (2,b))

for式では、ifを使ってフィルタすることができる。例えば7がつく数だけを選ぶ。

scala> for (x <- (1 to 50) if x.toString contains '7') yield x
res102: scala.collection.immutable.IndexedSeq[Int] = Vector(7, 17, 27, 37, 47)

フィルタはHaskellのリストモナドではどう実現されるのか？ここで出てくるのがMonadPlus型クラスとguard関数。

MonadPlus は、モノイドの性質をあわせ持つモナドを表す型クラスです。

guard関数の定義はこんな感じです。

guard :: (MonadPlus m) => Bool -> m () guard True = return () guard False = mzero

Haskellではguard関数とリスト内包表記でフィルタを使うのは同値である。

> [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)
[7,17,27,37,47]
> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]

ScalaではwithFilterメソッドでフィルタできる。for式の出力パート、つまりyeildのところはmapメソッドで置き換えることができる。

scala> for (x <- (1 to 50) if x.toString contains '7') yield x
res108: scala.collection.immutable.IndexedSeq[Int] = Vector(7, 17, 27, 37, 47)

scala> (1 to 50).withFilter(x => x.toString contains '7').map(x => x)
res109: scala.collection.immutable.IndexedSeq[Int] = Vector(7, 17, 27, 37, 47)

さっきflatMapを入れ子にしたやつと、for式のジェネレータの部分が似てるという話が出てきたが、for式の最後のジェネレータ以外のジェネレータはflatMapに置き換えることができる。

scala> for (n <- (1 to 50);
     |      ch <- List('a', 'b')
     |      if n % 10 == 0)
     |   yield n.toString + ":" + ch
res112: scala.collection.immutable.IndexedSeq[String] = Vector(10:a, 10:b, 20:a, 20:b, 30:a, 30:b, 40:a, 40:b, 50:a, 50:b)

scala> (1 to 50).flatMap{
     |   n => List('a', 'b').withFilter {
     |     _ => n % 10 == 0
     |   }.map {
     |     ch => n.toString + ":" + ch
     |   }
     | }
res1: scala.collection.immutable.IndexedSeq[String] = Vector(10:a, 10:b, 20:a, 20:b, 30:a, 30:b, 40:a, 40:b, 50:a, 50:b)

Scalaでは、withFilter, map, flatMapの他にforeach、この4つのメソッドを定義したオブジェクトに対してはfor式を使うことができる。

モナド則

1つ目は左恒等性というもの。

第一のモナド則が言っているのは、return を使って値をデフォルトの文脈に入れたものを >>= を使って関数に食わせた結果は、単にその値にその関数を適用した結果と等しくなりなさい、ということです。形式的に言えば、 return x >>= f と f x は等価である、ということです。

まぁ自然に理解できる。

2つ目は右恒等性。

モナドの第二法則は、>>= を使ってモナド値を return に食わせた結果は、元のモナド値と不変であると言っています。式で書くと、m >>= return はただの m である、ということです。

これはこんな感じのことかな。

scala> Some(5).flatMap(x => Some(x))
res2: Option[Int] = Some(5)

scala> List(1,2,3,4).flatMap(x => List(x))
res3: List[Int] = List(1, 2, 3, 4)

3つ目は、結合法則

最後のモナド則は、>>= を使ったモナド関数適用の連鎖があるときに、どの順序で評価しても結果は同じであるべき、というものです。式で書くと、(m >>= f) >>= g と m >>= (\ f x >>= g) が等価である、というものです。

こういう感じ。

scala> Option(Pole(0,0)).flatMap(_.landRight(2)).flatMap(_.landLeft(2)).flatMap(_.landRight(2))
res4: Option[Pole] = Some(Pole(2,4))

scala> Option(Pole(0,0)).flatMap(_.landRight(2).flatMap(_.landLeft(2).flatMap(_.landRight(2))))
res5: Option[Pole] = Some(Pole(2,4))

上はflatMapをつなげてて、下は入れ子になってる。

15.md

Zipper

この章では、いくつかのデータ構造に、そのデータ構造の一部分に注目するための Zipper を備える方法を紹介します。Zipper はデータ構造の要素の更新を簡単にし、データ構造を辿るという操作を効率的にしてくれるんです。

こういう木を用意する

sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
case class Node[+A](x: A, l: Tree[A], r: Tree[A]) extends Tree[A]

色々操作するための木を作るメソッドを用意

def freeTree: Tree[Char] =
  Node('P',
    Node('O',
      Node('L',
        Node('N',Empty,Empty),
        Node('T',Empty,Empty)
      ),
      Node('Y',
        Node('S',Empty,Empty),
        Node('A',Empty,Empty)
      )
    ),
    Node('L',
      Node('W',
        Node('C',Empty,Empty),
        Node('R',Empty,Empty)
      ),
      Node('A',
        Node('A',Empty,Empty),
        Node('C',Empty,Empty)
      )
    )
  )

木の中を移動して、移動した場所の値を'P'に置き換えた木を返すメソッドを用意。移動する場所は方向オブジェクトのリストで指示する。

sealed trait Direction
case object L extends Direction
case object R extends Direction

type Directions = List[Direction]

def changeToP(ds: Directions, tree: Tree[Char]): Tree[Char] = (ds, tree) match {
  case (L :: dss, Node(x, l, r)) => Node(x, changeToP(dss, l), r)
  case (R :: dss, Node(x, l, r)) => Node(x, l, changeToP(dss, r))
  case ([], Node(_, l, r)) = Node('P', l, r)
}

方向リストが示すノードの値を返すメソッドを用意

def elemAt[A](ds: Directions, tree: Tree[A]): A = (ds, tree) match {
  case (L :: dss, Node(_, l, _)) => elemAt(dss, l)
  case (R :: dss, Node(_, _, r)) => elemAt(dss, r)
  case (List(), Node(x, _, _)) => x
}

使ってみる

scala> elemAt(List(R,L), freeTree)
res2: Char = W

scala> elemAt(List(R,L), changeToP(List(R,L), freeTree))
res3: Char = P

changeToPメソッドでWがPになってる。

値の書き換えはできるようになったが、このままだと毎回木のルートから移動することになる。最初に置き換えたノードの隣のノードに移ったりできたら効率が上がりそう。

移動するたびに左に行ったのか右に行ったのかを覚えておくためにパンくずを残しておく。

type Breadcrumbs = [Direction]

def goLeft[A](tree: Tree[A], bs: Breadcrumbs): (Tree[A], Breadcrumbs) = tree match {
  case (Node(_, l, _), bs) => (l, L :: bs)
}

def goRight[A](tree: Tree[A], bs: Breadcrumbs): (Tree[A], Breadcrumbs) = tree match {
  case (Node(_, _, r), bs) => (r, R :: bs)
}

使ってみる。

scala> goLeft(goRight(freeTree, List()))
res8: (Tree[Char], Breadcrumbs) = (Node(W,Node(C,Empty,Empty),Node(R,Empty,Empty)),List(L, R))

関数が入れ子になって見づらくなりそうなのでこんな風にしておく。

case class TreeFocus[A](tree: Tree[A], bs: Breadcrumbs) {
  def goLeft: TreeFocus[A] = tree match {
    case Node(_, l, _) => TreeFocus(l, L :: bs)
  }

  def goRight: TreeFocus[A] = tree match {
    case Node(_, _, r) => TreeFocus(r, R :: bs)
  }
}

使ってみる。

scala> TreeFocus(freeTree, List()).goRight.goLeft
res11: TreeFocus[Char] = TreeFocus(Node(W,Node(C,Empty,Empty),Node(R,Empty,Empty)),List(L, R))

どこのノードを辿ってきたか分かるようになった。だけど、これだけでは隣のノードに効率よく移動することはまだできない。辿ってきたノードの逆側の部分木を覚えておく必要がある。

パンくずをDirectionから、辿ったのとは逆の部分木を保持できるようにする。

sealed trait Crumb[A]
case class LeftCrumb[A](x: A, tree: Tree[A]) extends Crumb[A]
case class RightCrumb[A](x: A, tree: Tree[A]) extends Crumb[A]

type Breadcrumbs[A] = List[Crumb[A]]

case class TreeFocus[A](tree: Tree[A], bs: Breadcrumbs[A]) {
  def goLeft: TreeFocus[A] = tree match {
    case Node(x, l, r) => TreeFocus(l, LeftCrumb(x, r) :: bs)
  }

  def goRight: TreeFocus[A] = tree match {
    case Node(x, l, r) => TreeFocus(r, RightCrumb(x, l) :: bs)
  }
}

使ってみる。

scala> TreeFocus(freeTree, List()).goRight.goLeft.bs
res15: Breadcrumbs = List(LeftCrumb(L,Node(A,Node(A,Empty,Empty),Node(C,Empty,Empty))), RightCrumb(P,Node(O,Node(L,Node(N,Empty,Empty),Node(T,Empty,Empty)),Node(Y,Node(S,Empty,Empty),Node(A,Empty,Empty)))))

じゃあ、辿ってきたノードを1個戻るメソッドを追加。

def goUp: TreeFocus[A] = bs match {
  case LeftCrumb(x, r) :: bss => TreeFocus(Node(x, tree, r), bss)
  case RightCrumb(x, l) :: bss => TreeFocus(Node(x, l, tree), bss)
}

使ってみる。うん、1個戻ってる。

scala> TreeFocus(freeTree, List()).goRight.goLeft.goUp.bs
res18: Breadcrumbs[Char] = List(RightCrumb(P,Node(O,Node(L,Node(N,Empty,Empty),Node(T,Empty,Empty)),Node(Y,Node(S,Empty,Empty),Node(A,Empty,Empty)))))

Emptyの場合はまだ対応できてないけど、これで隣のノードに移動したりできるようになった。TreeFocusは、元の木全体を復元するのに必要な情報に加えて、ある部分木に注目した状態というのを表現している。

このようにあるデータ構造の注目点と周辺の情報を含んでいるデータ構造をZipperと呼ぶ。

Zipperが注目しているノードの値を書き換えるメソッド、別のノードで置き換えるメソッド、木のルートへ移動するメソッドを追加する。

case class Zipper[A](tree: Tree[A], bs: Breadcrumbs[A]) {
  def goLeft: Zipper[A] = tree match {
    case Node(x, l, r) => Zipper(l, LeftCrumb(x, r) :: bs)
  }

  def goRight: Zipper[A] = tree match {
    case Node(x, l, r) => Zipper(r, RightCrumb(x, l) :: bs)
  }

  def goUp: Zipper[A] = bs match {
    case LeftCrumb(x, r) :: bss => Zipper(Node(x, tree, r), bss)
    case RightCrumb(x, l) :: bss => Zipper(Node(x, l, tree), bss)
  }

  def modify[A](f: a => a): Zipper[A] = tree match {
    case Node(x, l, r) => Zipper(Node(f(x), l, r), bs)
    case Empty => Zipper(Empty, bs)
  }

  def attach(t: Tree[A]): Zipper[A] = Zipper(t, bs)

  def topMost: Zipper[A] = bs match {
    case List() => Zipper(tree, bs)
    case _ => goUp.topMost
  }
}

使ってみる。

scala> Zipper(freeTree, List()).goRight.goLeft.tree
res24: Tree[Char] = Node(W,Node(C,Empty,Empty),Node(R,Empty,Empty))

scala> Zipper(freeTree, List()).goRight.goLeft.modify(_ => 'P').tree
res25: Tree[Char] = Node(P,Node(C,Empty,Empty),Node(R,Empty,Empty))

scala> Zipper(freeTree, List()).goRight.goLeft.attach(Node('Z', Empty, Empty)).tree
res26: Tree[Char] = Node(Z,Empty,Empty)

scala> Zipper(freeTree, List()).goRight.goLeft.topMost.bs
res27: Breadcrumbs[Char] = List()

リストのZipper

Zipperはほぼどんなデータ構造にも作れる。リストに対しても作れる。

case class ListZipper[A](xs: List[A], bs: List[A]) {
  def goForward: ListZipper[A] = xs match {
    case x :: xss => ListZipper(xss, x :: bs)
  }
  def goBack: ListZipper[A] = bs match {
    case b :: bss => ListZipper(b :: xs, bss)
  }
}

使ってみる。リストのZipperの動作を見てると、Zipperの名前がついてるのに納得がいく。ジッパーが左右に行ったり来たりするのと同じ動きをしている。

scala> val xs = List(1,2,3,4)
xs: List[Int] = List(1, 2, 3, 4)

scala> ListZipper(xs, List()).goForward
res29: ListZipper[Int] = ListZipper(List(2, 3, 4),List(1))

scala> ListZipper(xs, List()).goForward.goForward
res30: ListZipper[Int] = ListZipper(List(3, 4),List(2, 1))

scala> ListZipper(xs, List()).goForward.goForward.goBack
res31: ListZipper[Int] = ListZipper(List(2, 3, 4),List(1))

ZipperにOptionを導入

今まで、移動が失敗になる場合を無視してきた。例えば部分木に移動したときにEmptyである場合に対応していなかった。失敗するかもしれないという文脈を導入したいのでOptionを使う。

case class Zipper[A](tree: Tree[A], bs: Breadcrumbs[A]) {
  def goLeft: Option[Zipper[A]] = tree match {
    case Node(x, l, r) => Some(Zipper(l, LeftCrumb(x, r) :: bs))
    case Empty => None
  }

  def goRight: Option[Zipper[A]] = tree match {
    case Node(x, l, r) => Some(Zipper(r, RightCrumb(x, l) :: bs))
    case Empty => None
  }

  def goUp: Option[Zipper[A]] = bs match {
    case LeftCrumb(x, r) :: bss => Some(Zipper(Node(x, tree, r), bss))
    case RightCrumb(x, l) :: bss => Some(Zipper(Node(x, l, tree), bss))
    case List() => None
  }

  def modify(f: A => A): Zipper[A] = tree match {
    case Node(x, l, r) => Zipper(Node(f(x), l, r), bs)
    case Empty => Zipper(Empty, bs)
  }

  def attach(t: Tree[A]): Zipper[A] = Zipper(t, bs)

  def topMost: Zipper[A] = bs match {
    case List() => Zipper(tree, bs)
    case _ => goUp.map(_.topMost).getOrElse(Zipper(tree, bs))
  }
}

使ってみる。

scala> Zipper(freeTree, List()).goRight.flatMap(_.goLeft).flatMap(_.goRight).map(_.tree)
res1: Option[Tree[Char]] = Some(Node(R,Empty,Empty))

scala> Zipper(freeTree, List()).goRight.flatMap(_.goLeft).flatMap(_.goRight).flatMap(_.goUp).map(_.tree)
res2: Option[Tree[Char]] = Some(Node(W,Node(C,Empty,Empty),Node(R,Empty,Empty)))