phucnh · February 4, 2016 16:48 · Sep 19, 2015 · Sep 15, 2015 · Sep 15, 2015 · Jul 13, 2014
diff --git a/gistfile1.md b/gistfile1.md
@@ -122,15 +122,15 @@ implicit conversion は、あるインスタンスを別の型のインスタン
 
 ```scala
 trait MinValue[A] {
-  def apply[A]: A
+  def apply: A
 }
 def minValue[A](implicit m: MinValue[A]): A = m.apply
 
 implicit val intMin = new MinValue[Int] {
-  def apply[Int]: Int = Int.MinValue
+  def apply: Int = Int.MinValue
 }
 implicit val stringMin = new MinValue[String] {
-  def apply[String]: String = ""
+  def apply: String = ""
 }
 ```
 

diff --git a/gistfile1.md b/gistfile1.md
@@ -107,7 +107,7 @@ case class Organization(name: String) extends ToXml2 {
 
 実は **implicit conversion は 型クラスの特殊形** なのです。
 
-implicit conversionはコンパイラが「別の型に変換することができる」という型パラメータを特別扱いしているのです。
+implicit conversionはコンパイラが「別の型に変換することができる」という型クラスを特別扱いしているのです。
 
 
 ### implicit conversion だと都合が悪い場合

diff --git a/gistfile1.md b/gistfile1.md
@@ -10,7 +10,7 @@
 
 9/6, 9/7 [ScalaMatsuri](http://scalamatsuri.org/) やります！
 
-![ScalaMatsuri2014](http://scalamatsuri.org/assets/2014/img/scala_matsuri_A.png)
+![ScalaMatsuri2014](http://2014.scalamatsuri.org/assets/2014/img/scala_matsuri_A.png)
 
 ## アジェンダ
 
@@ -105,7 +105,7 @@ case class Organization(name: String) extends ToXml2 {
 
 先ほどの例ならば、既存のクラスから `ToXml2` への implicit conversion を提供すれば、型クラスの implicitな値(これ以降、型クラスインスタンスと呼ぶ)を定義するのと何ら変わりません。
 
-実は **implicit conversion は 型パラメータの特殊形** なのです。
+実は **implicit conversion は 型クラスの特殊形** なのです。
 
 implicit conversionはコンパイラが「別の型に変換することができる」という型パラメータを特別扱いしているのです。
 

diff --git a/gistfile1.md b/gistfile1.md
@@ -57,7 +57,7 @@ object Organization {
 
 ```scala
 // 統一的に扱う事ができる
-def toXml[A](a: A)(implicit ev: ToXml[A]): NodeSeq = ev.toXml(a)
+def toXml[A](a: A)(implicit ev: ToXml[A]): NodeSeq = ev(a)
 toXml(Person("John", 20))
 toXml(Organization("scalajp"))
 ```

diff --git a/gistfile1.md b/gistfile1.md
@@ -256,8 +256,8 @@ val b: Option[Int] = ...
 val f: Int => Int => Int = {a => b => a + b}
 
 val af: Option[Int => Int => Int] = Option(f)
-val r1: Option[Int => Int]        = af <*> a
-val r2: Option[Int]               = af <*> a <*> b
+val r1: Option[Int => Int]        = a <*> af
+val r2: Option[Int]               = b <*> (a <*> af)
 ```
 
 さて、先ほどちょっとずるをしましたね？ 関数 f を Apply値にする為に明示的に Option を呼んでしまっていました。
@@ -286,8 +286,8 @@ val b: Option[Int] = ...
 val f: Int => Int => Int = {a => b => a + b}
 
 val af: Option[Int => Int => Int] = point[Option](f)
-val r1: Option[Int => Int]        = point[Option](f) <*> a
-val r2: Option[Int]               = point[Option](f) <*> a <*> b
+val r1: Option[Int => Int]        = a <*> point[Option](f)
+val r2: Option[Int]               = b <*> (a <*> point[Option](f))
 ```
 
 これでめでたく複数の Applicative値と複数の「普通の値を受け取り普通の値を返す関数」を自由に組み合わせて、最終的な一つの Applicative値を得ることがでるようになりました。
@@ -310,7 +310,7 @@ val a: Option[Int] = ...
 val myCoolMethod: Int => Option[String] = ...
 
 val af: Option[Int => Option[String]] = point[Option](myCoolMethod)
-val r1: Option[Option[String]]        = point[Option](myCoolMethod) <*> a
+val r1: Option[Option[String]]        = a <*> point[Option](myCoolMethod)
 ```
 
 最終結果が `Option[Option[String]]` になってしまいました。
@@ -417,7 +417,8 @@ Semigroup の二項演算に単位元が存在するもの
 ```scala
 // ある型 Foo が Monoid だった場合
 val a: Foo = ...
-Monoid[Foo].zero |+| a == a |+| Monoid[Foo].zero
+Monoid[Foo].zero |+| a == a
+                     a == a |+| Monoid[Foo].zero
 ```
 
 これがどんなインスタンスでも常に true となる `zero` が存在するという事
@@ -534,4 +535,4 @@ final class FoldableOps[F[_],A]...(val self: F[A])(implicit val F: Foldable[F]).
 
   ... // 他にもいっぱい
 }
-```
+```
diff --git a/gistfile1.md b/gistfile1.md
@@ -199,7 +199,7 @@ Functor値が内包している値を関数の引数として与え、結果値
 val a: Option[Int] = ...
 val b: Option[Int] = ...
 
-val f: Int => Int => Int
+val f: Int => Int => Int = {a => b => a + b}
 ```
 
 これらを組み合わせて `a` と `b` が内包する値に `f` を適用して一つの `Option[Int]` を作れるでしょうか？
@@ -211,7 +211,11 @@ val f: Int => Int => Int
 
 ## Apply と Applicative
 
-TODO
+そこで登場するのが Apply です。
+
+Apply は Functor を継承して、`ap` というメソッドを提供する型クラスです。
+
+インスタンスに対して `<*>` というエイリアスが提供されています。
 
 ```scala
 trait Apply[F[_]] extends Functor[F] { self =>
@@ -224,9 +228,43 @@ final class ApplyOps[F[_],A]...(val self: F[A])(implicit val F: Apply[F])...{
 }
 ```
 
-この Apply に `point` を足したものが Applicative になります。
+この `ap` は何をするものかというと、Apply値とApplyに包まれた関数を受け取って、内包されている値を内包されている関数に適用して、Applyに内包された結果値を返す処理です。
+
+ちょっと何を言ってるんだか良くわかりませんね。
+
+先ほどの Option の例に戻りましょう。
+
+```scala
+val a: Option[Int] = ...
+val b: Option[Int] = ...
+
+val f: Int => Int => Int = {a => b => a + b}
+```
+
+ここでちょっとずるをします。今、関数 `f` は「普通の値を受け取り普通の値を返す関数」ですが、Applyが受け取れるのはApply値になった関数なので、`f` を Option でくるみたいと思います。
+
+```scala
+val af: Option[Int => Int => Int] = Option(f)
+```
+
+これで準備が整いました。これによって、以下の様なコードで `a` と `b` を使って一つの Option を作ることができます。
+
+```scala
+val a: Option[Int] = ...
+val b: Option[Int] = ...
+
+val f: Int => Int => Int = {a => b => a + b}
+
+val af: Option[Int => Int => Int] = Option(f)
+val r1: Option[Int => Int]        = af <*> a
+val r2: Option[Int]               = af <*> a <*> b
+```
+
+さて、先ほどちょっとずるをしましたね？ 関数 f を Apply値にする為に明示的に Option を呼んでしまっていました。
+
+これでは抽象化して統一的に扱えるというのが嘘になってしまいます。
 
-TODO
+そこでこのような普通の値を Apply値にくるむ操作を Applyに足したものが Applicative になります。
 
 ```
 trait Applicative[F[_]] extends Apply[F] { self =>
@@ -235,11 +273,64 @@ trait Applicative[F[_]] extends Apply[F] { self =>
 }
 ```
 
-TODO
+Apply を継承して、`point` というメソッドが追加されていますね。
+
+この操作は普通の値を受け取り、Applicative値に包んで返すというものです。
+
+したがって、これを使えば「普通の値を受け取り普通の値を返す関数」も Applicativeに包むことができるのです。
+
+```scala
+val a: Option[Int] = ...
+val b: Option[Int] = ...
+
+val f: Int => Int => Int = {a => b => a + b}
+
+val af: Option[Int => Int => Int] = point[Option](f)
+val r1: Option[Int => Int]        = point[Option](f) <*> a
+val r2: Option[Int]               = point[Option](f) <*> a <*> b
+```
+
+これでめでたく複数の Applicative値と複数の「普通の値を受け取り普通の値を返す関数」を自由に組み合わせて、最終的な一つの Applicative値を得ることがでるようになりました。
 
+さて、そんな強力な Applicative なのですが、それでもやっぱり弱点があります。
+
+というのも、「普通の値を受け取りApplicative値を返す関数」が出てきた場合に合成することができなくなるのです。
+
+例として Int を受け取り、それを Option[String] を返す `myCoolMethod` があるとしましょう。
+
+```scala
+val myCoolMethod: Int => Option[String] = ...
+```
+
+これを先ほどの a に適用しようとすると下記のようになってしまいます。
+
+```scala
+val a: Option[Int] = ...
+
+val myCoolMethod: Int => Option[String] = ...
+
+val af: Option[Int => Option[String]] = point[Option](myCoolMethod)
+val r1: Option[Option[String]]        = point[Option](myCoolMethod) <*> a
+```
+
+最終結果が `Option[Option[String]]` になってしまいました。
+
+つまり、Applicative は 「普通の値を受け取りApplicative値を返す関数」に対しては無力なのです。
 
 ## Bind と Monad
 
+そして、それを解決するのがわれらが Monad です。
+
+```scala
+trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
+  ...
+}
+```
+
+Monad の定義を見てみると、独自のメソッドは追加されておりません。その代わり、Applicative と Bind という型クラスを両方継承(mix-in)しています。
+
+この Bind は以下の様な型クラスです。
+
 ```scala
 trait Bind[F[_]] extends Apply[F] { self =>
   def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
@@ -251,16 +342,25 @@ final class BindOps[F[_],A]...(val self: F[A])(implicit val F: Bind[F])...{
   ... 
 ```
 
-TODO
+Applyを継承して、`bind` というメソッドを追加しています。
+
+インスタンスのために `flatMap` と `>=` というエイリアスを提供しています。
+
+この `bind` は Bind値と「普通の値を受け取りBind値を返す関数」を受け取って、Bind値に内包された値を関数に適用して、最終的な Bind値にしてくれる、というものです。
+
+これを使うことで先ほどの `myCoolMethod` を `a` に適用することができます。
 
 ```scala
-trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
-  ...
-}
+val a: Option[Int] = ...
+
+val myCoolMethod: Int => Option[String] = ...
+
+val af: Option[String] = a >>= myCoolMethod
 ```
 
-TODO
+Bind 自体は Apply を継承しているだけなので、通常の値をBind値にする能力はもっていません。したがって、Bind自体は「普通の値を受け取りBind値を返す関数」を合成する能力を持っていますが、「普通の値を受け取り普通の値を返す関数」を合成する能力を持っていないのです。
 
+そこで、Bind と Applicative の両方の力を持ったものが Monad になります。
 
 ## Functor/Applicative/Monad まとめ
 
@@ -434,4 +534,4 @@ final class FoldableOps[F[_],A]...(val self: F[A])(implicit val F: Foldable[F]).
 
   ... // 他にもいっぱい
 }
-```
+```
diff --git a/gistfile1.md b/gistfile1.md
@@ -0,0 +1,437 @@
+# 主要な型クラスの紹介
+
+* 2014/07/13 Scalaz勉強会
+* [@gakuzzzz](https://twitter.com/gakuzzzz)
+* 中村 学
+* 株式会社Tech to Value
+* [play2-auth](https://github.com/t2v/play2-auth) が [scala-awesome](https://github.com/lauris/awesome-scala)に載りました
+
+## 宣伝
+
+9/6, 9/7 [ScalaMatsuri](http://scalamatsuri.org/) やります！
+
+![ScalaMatsuri2014](http://scalamatsuri.org/assets/2014/img/scala_matsuri_A.png)
+
+## アジェンダ
+
+1. 型クラスとは
+1. Scalazにおける型クラス
+1. Functor/Applicative/Monad
+1. Semigroup/Monoid/Foldable
+
+
+## 型クラスとは
+
+異なる型に共通のインターフェイスを持たせて、統一的に扱えるようにするもの
+
+例えば様々なクラスをXML化する `toXml` というメソッドを作りたいとします。
+
+```scala
+trait ToXml[A] {
+  def apply(a: A): NodeSeq
+}
+
+case class Person(name: String, age: Int)
+object Person {
+  implicit val personToXml = new ToXml[Person] {
+    def apply(a: Person): NodeSeq = 
+      <person>
+        <name>{a.name}</name>
+        <age>{a.age.toString}</age>
+      </person>
+  }
+}
+
+case class Organization(name: String)
+object Organization {
+  implicit val orgToXml = new ToXml[Organization] {
+    def apply(a: Organization): NodeSeq = 
+      <organization>
+        <name>{a.name}</name>
+      </organization>
+  }
+}
+```
+
+上記のような trait と、 implicit な値を定義すれば下記のように `toXml` というメソッドを作ることができます。
+
+```scala
+// 統一的に扱う事ができる
+def toXml[A](a: A)(implicit ev: ToXml[A]): NodeSeq = ev.toXml(a)
+toXml(Person("John", 20))
+toXml(Organization("scalajp"))
+```
+
+### 普通に mixin じゃダメなの？
+
+上記の例であれば、普通に mixin した方が簡単ですね
+
+```scala
+trait ToXml2 {
+  def toXml: NodeSeq
+}
+
+case class Person(name: String, age: Int) extends ToXml2 {
+  def toXml: NodeSeq = 
+    <person>
+      <name>{name}</name>
+      <age>{age.toString}</age>
+    </person>
+}
+
+case class Organization(name: String) extends ToXml2 {
+  def toXml: NodeSeq = 
+    <organization>
+      <name>{name}</name>
+    </organization>
+}
+```
+
+### じゃあ何で型クラスを使うのか
+
+普通の trait の mixin は、クラスを定義する時に指定します。
+
+つまり、標準ライブラリや他のライブラリなど、**既存のライブラリが提供するクラスには mixin できません。**
+
+しかし、型クラスであれば、implicit な値を定義すれば良いだけなので、既存のクラスだろうが関係なく定義できます。
+
+すなわち、**拡張に対して開いている** (Open-Closed Principle) のです。
+
+(参考) [Open-Closed Principle とデザインパターン](http://www.objectclub.jp/community/memorial/homepage3.nifty.com/masarl/article/dp-ocp-2.html)
+
+### 既存のクラスを拡張？どっかで聞いた事ある
+
+それって implicit conversion じゃダメなの？
+
+先ほどの例ならば、既存のクラスから `ToXml2` への implicit conversion を提供すれば、型クラスの implicitな値(これ以降、型クラスインスタンスと呼ぶ)を定義するのと何ら変わりません。
+
+実は **implicit conversion は 型パラメータの特殊形** なのです。
+
+implicit conversionはコンパイラが「別の型に変換することができる」という型パラメータを特別扱いしているのです。
+
+
+### implicit conversion だと都合が悪い場合
+
+implicit conversion は、あるインスタンスを別の型のインスタンスとみなしてメソッドを呼び出します。
+
+つまり、インスタンスが先に存在しないと使うことができません。
+
+例として、任意の型の最小値を求める `minValue` というメソッドを考えましょう。
+
+例えば、Int なら Int.MinValue ですし、String なら空文字列を返すようなメソッドです。
+
+```scala
+trait MinValue[A] {
+  def apply[A]: A
+}
+def minValue[A](implicit m: MinValue[A]): A = m.apply
+
+implicit val intMin = new MinValue[Int] {
+  def apply[Int]: Int = Int.MinValue
+}
+implicit val stringMin = new MinValue[String] {
+  def apply[String]: String = ""
+}
+```
+
+`minValue` はあくまでその型の最小値が知りたいだけなので、`toXml` の様に A型のインスタンスを必要としません。あくまで `MinValue[A]` の型クラスインスタンスが見つかれば十分なのです。
+
+この様なインスタンスが不要なメソッドの場合、インスタンスが前提となる implicit conversion では実現するのが難しくなります。
+
+
+### まとめ
+
+* 型クラスはポリモーフィズムを実現するもの
+    * 継承によるポリモーフィズムと異なり、拡張に対し開いている
+    * アドホック ポリモーフィズム
+* implicit conversion は型クラスの特殊形
+* インスタンスを必要としない処理では型クラス使うと便利
+
+
+## Scalazにおける型クラス
+
+Scalaz では型クラスを表す trait は、その型クラス名と同じ名前の scala ファイルに定義されています。
+
+また、Scalaz では利便性のため、インスタンスから型クラスを使用したメソッドが使えるように、サポートクラスとそのimplicit conversionを提供しています。
+
+そのサポートクラスは型クラス名Opsという名前で定義されており、型クラス名Syntax.scala というファイルに書かれています。
+
+```
+Foo.scala
+	Foo
+FooSyntax.scala
+	FooOps
+```
+
+## Functor
+
+```scala
+trait Functor[F[_]] ... { self =>
+  def map[A, B](fa: F[A])(f: A => B): F[B]
+  ...
+}
+
+final class FunctorOps[F[_],A]...(val self: F[A])(implicit val F: Functor[F])...{
+  def map[B](f: A => B): F[B] = F.map(self)(f)
+
+  ... // 他にもいっぱい
+}
+
+```
+
+Functor は型引数を一つ取る型(高階型)に対して、`map` というメソッドを提供する型クラスです。
+
+普段 `scala.collection.Seq#map` や `scala.Option#map` などは普通に使われていると思います。
+
+この `map` を共通インターフェイスとしてくくり出したものが Functor です。
+
+`map` は 一つのFunctor値と「普通の値を取り普通の値を返す関数」を引数にとり Functor値を返す処理です。
+
+Functor値が内包している値を関数の引数として与え、結果値を内包したFunctorを返します。
+
+一つの Functor値に沢山の「普通の値を取り普通の値を返す関数」を map でつなげていく事によって最終的な一つの Functor値を得ることができます。
+
+しかし複数の Functor値が出てくると、話が変わってきます。
+
+例えば `Option[Int]` 型の変数 a, b があるとしましょう。そして「普通の値を取り普通の値を返す関数」としてIntの足し算を行う + があるとします。
+
+```scala
+val a: Option[Int] = ...
+val b: Option[Int] = ...
+
+val f: Int => Int => Int
+```
+
+これらを組み合わせて `a` と `b` が内包する値に `f` を適用して一つの `Option[Int]` を作れるでしょうか？
+
+もちろん `Option` 固有の `getOrElse` などを駆使すれば可能ですが、今は Functorとしての話なので使えるものは `map` のみです。
+
+実はこれは行うことができません。Functorは複数のFunctor値が出てくると無力なのです。
+
+
+## Apply と Applicative
+
+TODO
+
+```scala
+trait Apply[F[_]] extends Functor[F] { self =>
+  def ap[A,B](fa: => F[A])(f: => F[A => B]): F[B]
+  ...
+}
+final class ApplyOps[F[_],A]...(val self: F[A])(implicit val F: Apply[F])...{
+  final def <*>[B](f: F[A => B]): F[B] = F.ap(self)(f)
+  ...
+}
+```
+
+この Apply に `point` を足したものが Applicative になります。
+
+TODO
+
+```
+trait Applicative[F[_]] extends Apply[F] { self =>
+  def point[A](a: => A): F[A]
+  ...
+}
+```
+
+TODO
+
+
+## Bind と Monad
+
+```scala
+trait Bind[F[_]] extends Apply[F] { self =>
+  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
+  ...
+}
+final class BindOps[F[_],A]...(val self: F[A])(implicit val F: Bind[F])...{
+  def flatMap[B](f: A => F[B]) = F.bind(self)(f)
+  def >>=[B](f: A => F[B]) = F.bind(self)(f)
+  ... 
+```
+
+TODO
+
+```scala
+trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
+  ...
+}
+```
+
+TODO
+
+
+## Functor/Applicative/Monad まとめ
+
+* Functor は、一つの Functor値から「普通の値を取り普通の値を返す関数」を使って、一つの Functor値を作ることができます
+    * 複数の Functor値が出てくるとお手上げ
+* Applicative は、複数の Applicative値から「普通の値を取り普通の値を返す関数」を使って、一つの Applicative値を作ることができます
+    * 「普通の値を取り Applicative値を返す関数」が出てくるとお手上げ
+* Monad は、複数の Monad値から「普通の値を取り Monad値を返す関数」を使って、一つの Monad値を作ることができます
+    * Monad は Applicative でもあるので、「普通の値を取り普通の値を返す関数」も適用できます
+* Monad の合成は非常によく使うので、サポート構文が用意されています
+    * それが for comprehension (for内包表記) いわゆる for式です
+
+## Semigroup
+
+日本語で書くと半群
+
+```scala
+trait Semigroup[F]  { self =>
+  def append(f1: F, f2: => F): F
+  ...
+}
+
+final class SemigroupOps[F]...(val self: F)(implicit val ev: Semigroup[F])...{
+  final def |+|(other: => F): F = ev.append(self, other)
+  ...
+}
+```
+
+以下の性質を満たす2項演算と集合の組み合わせ
+
+* 演算が集合に対し閉じている
+    * Scalazでは集合を型で現す
+    * つまり引数の型と戻り値の型が同じという事
+* 演算が結合法則を満たす
+    * つまり `(a |+| b) |+| c == a |+| (b |+| c)` という事
+    * 結合法則を満たさない例は整数の引き算
+    * 交換法則(可換則) ではない事に注意！
+
+
+## Monoid
+
+Monad と名前似てるけど別物
+
+```scala
+trait Monoid[F] extends Semigroup[F] { self =>
+  /** The identity element for `append`. */
+  def zero: F
+  ...
+}
+```
+
+Semigroup の二項演算に単位元が存在するもの
+
+```scala
+// ある型 Foo が Monoid だった場合
+val a: Foo = ...
+Monoid[Foo].zero |+| a == a |+| Monoid[Foo].zero
+```
+
+これがどんなインスタンスでも常に true となる `zero` が存在するという事
+
+#### 具体例
+
+* Int と `+` という演算なら `0` が単位元
+* Seq[A] と `++` という演算なら `Seq.empty` が単位元
+
+
+### 一つの型が複数の演算でMonoidになれる場合がある
+
+例えば
+
+* Int は `+` を演算とし、`0` を単位元としたモノイド
+* Int は `*` を演算とし、`1` を単位元としたモノイド
+* Boolean は `||` を演算とし、`false` を単位元としたモノイド
+* Boolean は `&&` を演算とし、`true` を単位元としたモノイド
+
+Scala の型クラスは一つの型が一つの型クラスについて、型クラスインスタンスを複数定義できるため、
+Int や Boolean のモノイドもそのように複数定義する事も可能。
+
+```scala
+object AddMonoid extends Monoid[Int] {
+  def append(a: Int, b: => Int): Int = a + b
+  def zero: Int = 0
+}
+object MultipleMonoid extends Monoid[Int] {
+  def append(a: Int, b: => Int): Int = a * b
+  def zero: Int = 1
+}
+```
+
+可能だけどぶっちゃけ不便なので、**Tagged type** を使って複数の型クラスインスタンスを実現してる。
+
+Tagged type についてはこの後 @kxbmap さんが詳しく解説してくれるはずなのでここでは省略。
+
+## MonadPlus
+
+Haskell では Monad かつ Monoid な事を表す型クラスとして MonadPlus が定義されています。
+
+Scalaz でも MonadPlus が存在するのですが、実はちょっと定義が Haskell と異なります。
+
+Scalaz の MonadPlus は、Monad を継承しているものの、Monoid は継承しておらず、PlusEmpty という別の型クラスを継承しています。
+
+この PlusEmpty は Monoid とそっくりな型クラスなんですが、型の制限が Functor などと同じように、型引数を1つ取る高階型であるという違いがあります。
+
+## Foldable
+
+畳み込みが可能である事を示す型クラスです。
+
+```scala
+trait Foldable[F[_]]  { self =>
+  def foldMap[A,B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B
+  def foldRight[A, B](fa: F[A], z: => B)(f: (A, => B) => B): B
+  ...
+}
+```
+
+Functor 等と同じように、Foldable の型引数に渡せる型は、高階型である必要があります。
+
+`foldMap` で Monoid が出てきていますね。この Monoid を使うことで `foldMap` の実装は、畳み込みの順序をどうすればいいのかだけを気にすればよくなります。
+
+```scala
+sealed trait Tree[+A]
+object Tree {
+  case class Node[+A](left: Tree[A], value: A, right: Tree[A]) extends Tree[A]
+  case object Empty extends Tree[Nothing]
+
+  implicit val foldable = new Foldable[Tree] {
+    def foldMap[A, B](fa: Tree[A])(f: A => B)(implicit F: Monoid[B]): B = fa match {
+      case Empty         => F.zero
+      case Node(l, v, r) => foldMap(l)(f) |+| f(v) |+| foldMap(r)(f)
+    }
+  }
+}
+```
+
+畳み込みは非常に強力なので、Foldableの型クラスインスタンスを定義するだけで下記のメソッド群が自動で手に入ります。
+
+```scala
+final class FoldableOps[F[_],A]...(val self: F[A])(implicit val F: Foldable[F])...{
+  def foldMap[B: Monoid](f: A => B = (a: A) => a): B = ...
+  def foldRight[B](z: => B)(f: (A, => B) => B): B = ...
+  def foldLeft[B](z: B)(f: (B, A) => B): B =...
+  def fold(implicit A: Monoid[A]): A = ...
+  def length: Int = ...
+  def index(n: Int): Option[A] = ...
+  def indexOr(default: => A, n: Int): A = ...
+  def sumr(implicit A: Monoid[A]): A = ...
+  def suml(implicit A: Monoid[A]): A = ...
+  def toList: List[A] = ...
+  def toIndexedSeq: IndexedSeq[A] = ...
+  def toSet: Set[A] = ...
+  def toIList: IList[A] = ...
+  def toEphemeralStream: EphemeralStream[A] = ...
+  def all(p: A => Boolean): Boolean = ...
+  def any(p: A => Boolean): Boolean = ...
+  def count: Int = ...
+  def maximum(implicit A: Order[A]): Option[A] = ...
+  def maximumOf[B: Order](f: A => B): Option[B] = ...
+  def maximumBy[B: Order](f: A => B): Option[A] = ...
+  def minimum(implicit A: Order[A]): Option[A] = ...
+  def minimumOf[B: Order](f: A => B): Option[B] = ...
+  def minimumBy[B: Order](f: A => B): Option[A] = ...
+  def longDigits(implicit d: A <:< Digit): Long = ...
+  def empty: Boolean = ...
+  def element(a: A)(implicit A: Equal[A]): Boolean = ...
+  def splitWith(p: A => Boolean): List[NonEmptyList[A]] = ...
+  def selectSplit(p: A => Boolean): List[NonEmptyList[A]] = ...
+  def collapse[X[_]](implicit A: ApplicativePlus[X]): X[A] = ...
+  def concatenate(implicit A: Monoid[A]): A = ...
+  def intercalate(a: A)(implicit A: Monoid[A]): A = ...
+
+  ... // 他にもいっぱい
+}
+```