Ch8: Functoriality を読んでいく

イントロ

前回は、関手(ファンクタ、Functor)の概念や様々な例を学んだ。
今回は、その拡張や仲間を見ていこう。
何故拡張する必要があるのか?
例えば、Either[_, _]のように2つの型でパラメタ化された型はこれまで学んできた関手では表現できない。(関手はF[_]という形だった)
他には、Function1[A, Int]は(共変)関手で表現できるが、Function1[Int, A]は表現できない。(射の対応に注意)

Functoriality, Functrialとは何か?
一言でいうと、何かが関手である(なれる)という事を意味する。

8.0 Functorial(ity) とは

この項では本章のタイトルでもあるFunctoriality について話していく。
ただ、私はまだFunctorialityの正確な定義も日本語訳も見つけられていないため、ざっくりとしたイメージを話すことになる。
これらの正確な定義や日本語訳をご存じの方はぜひ教えてほしい。

おそらく、Functoiral(またはFunctoriality)は日本語で言えば「関手性・関手的」みたいな言葉になると思う。
そして、ここではFuncorialを以下のように理解する。

  • 「ある構成(法)C が Functorial(関手的)である」とは、「元々の関係性に対して構成Cがファンクタ則を満たしている」ことを意味する。

前章でListは関手とみなせる と言ったが、これはまさにListがfunctorialであるということだ。

8.1 Bifunctors

さて、冒頭で述べたように現在我々が持っている関手ではEither[A, B]のようなものは表現できない。
それは、関手が1つの(プログラムの)圏から1つの(プログラムの)圏への対応を考えているからだ。
なので、少しドメインを大きくして、2つの圏から1つの圏への射を考えてみよう。これを、Bifunctor(双関手)と呼ぶ。
f:id:sereronnrot:20210224163645j:plain

これは言い換えると、圏Cと圏Dの直積、C×Dから圏Eへのマッピングを考えている。

f:id:sereronnrot:20210224163704j:plain

  1. 圏Cと圏Dの直積は圏か?
  2. 圏です。
    射は(f, g)で、合成は (f, g) ∘ (f1, g1) = (f ∘ f1, g ∘ g1), idは、 (id, id) TODO: 書く。

f:id:sereronnrot:20210224163733j:plain


双関手のファンクタ則を考えていくときは、圏C×Dから圏Eへのファンクタとみたときのファンクタ則を考えれば良い。
双関手をscalaで定義してみる。

trait Bifunctor[F[_, _]] {
  def bimap[A, B, C, D](f: A => C)(g: B => D): F[A, B] => F[C, D] = 
    first(f) compose second(h)
  def first[A, B, C](f: A => C): F[A, B] => F[C, B] = bimap(f)(identity[B])
  def second[A, B, D](g: B => D): F[A, B] => F[A, D] = bimap(identity[A])(g)
}

ここで、firstsecondが定義されているのはなぜだろうか?
bimapfirstsecondで定義されており、first,secondbimapを使用して定義されているので、「bimap1つ」「firstsecond」のどちらを先に定義しても、もう一方がそれにより自動的に定義されるので、どちらかを実装すれば良いことになる。
これは、圏C×Dの図を見てもらうと分かるように、(f, g) = (f, id) ∘ (id, g)が成り立つことから、bimapもF((f, g) ) = F((f, id) ) ∘ F((id, g) )となり、左辺(bimap)は右辺(first ∘ second)と等しいからだ。

TODO: premonoidal category と Associativity

8.2 Product and Coproduct Bifunctors 直積と直和は双関手

双関手の例を見ていこう。 直積を覚えているだろうか?
忘れた人は、ここを確認してほしい。

もし対象の任意のペアに直積が存在していたら、それら対象から積へのマッピングはbifunctorial(双関手的)であるといえる。
なぜなら、bimapが定義できるからだ。(具体的な実装は後に見ていく)

では、「対象の任意のペアに積が存在している」ということはありうるのだろうか?
少なくともプログラムの圏(Hask, データ型が対象で純粋関数が射の圏)では成り立つ。
(他の圏だとこれが成り立たないものもあるんだろうか?)

では、試しに一番シンプルな積型であるTuple2を双関手にしてみよう。
プログラムの圏をP、特にTuple2のみの圏をTとすると、Tuple2: P x P -> Tと書ける。

implicit val tuple2Bifunctor = new Bifunctor[Tuple2] {
  def bimap[A, B, C, D](f: A => C)(g: B => D): ((A, B)) = {
    case (x, y) => (f(x), g(y))
  }
}

ここでの双関手の働きのイメージは、(,)a b = (a, b)のように型のペアを作る感じだ。

積と直和が双対であるので、直和も双関手だ。

implicit val eitherBifunctor = new Bifunctor[Either] {
  def bimap[A, B, C, D](f: A => C)(g: B => D):
    Either[A, B] => Either[C, D] = {
    case Left(x) => Left(f(x))
    case Right(y) => Right(g(y))
  }
}

(本ではmonoidal category(モノイド圏)に触れているが、言葉が足りないので一旦省略)

8.3 Functorial Algebraic Data Type 関手的代数データ型

私達は前章でパラメータ化されたデータ型(parameterized data types)が関手とみなせる例をいくつか見てきた。
では、ADT(代数的データ構造)はfunctrialだろうか?

この問に答えるために、まずは「どうやったらADTがfunctrialであるといえるか」を整理しよう。
前提として、ADTは簡素な型を直積や直和で組み合わせることによって複雑な型が構成される。
また、関手も合成が可能であり、特に直積と直和は前項で見たように双関手だ。
よって、ADTの基本的な構成物・要素がfunctorialであると示すことができれば、ADTもまたfunctorialであるといえそうだ。

では、ADTの基本的な構成物はどのようなものがあるだろうか?
小さいものから考えると、まず以下の2つが考えられる。

  1. Unit型のように、型パラメタに依存しないもの
  2. Option型Some等の、1つの型パラメータをラップ(カプセル化)したもの

実は、基本的な構成物としてはこれで十分なのである。
なぜなら、2つ以上の型パラメータをラップしたものは、直和や積型を使用して表現が可能であるからだ。
よって、これらがfunctorialであることを確認していこう。


1. Unitがfunctorialである

Unit型は前章の定数関手の項で見たように、関手Unit[_]とみなすことが出来る。  
これはUnit型はfunctorialである、ともいえる。
この時、コドメインの要素は()(あるいは何らかの単一の値)だけであり、ドメインの型パラメタによらない。

また、Unitが関手であることから、それと同型のList型のNilOption型のNoneも関手とみなせる。
NoneNilも、以下のように型パラメータによらない。

// None::Option[_]
val none0:Option[Int] = None
val none1:Option[String] = None
val none2:Option[List[Int]] = None
// Nil::List[_]
val nil0:List[Int] = Nil
val nil1:List[String] = Nil
val nil2:List[List[Int]] = Nil

2. 1つの型パラメータをラップしたものはfunctorialである

さて、Option型のSomeなどはどうだろうか。単一の値をラップしているということは、アンラップ、つまり戻すことも可能であるという事を考慮すると、identity functor(恒等関手)と同型であることが分かる。
注意) ここではラップする際に中の値について何らかの変更を加えるものは想定されていない。何故なら何らかの変更を加えるにはその値の型情報が必要であり、型はパラメタ化されているため決められないからだ。

type Id[A] = A  
implicit val identityFunctor = new Functor[Id] {
    def map[A, B](f: A => B)(x: Id[A]): Id[B] = f(x)
  }

さて、これでADTの基本的な構成物がfunctorialである事がわかった。

この結果を使って、試しにOptionがfunctorialであることを確認してみよう。
Option型の値はNoneSome(a)であるため、これらの直和で構成できるのだった。

// None | Some(a)
sealed trait Option[+A]
case object None extend
case class Some[A](a: A) extends Option[A]

NoneConst ()あるいはUnitと同型であり、SomeIdentityと同型であることを思い出すと、以下のように書ける。

type Option[A] = Either[Unit[A], Id[A]]

よって、OptionはUnit[_] とIdentity[A] の合成であると言えた。

次に、2. 関手2つと双関手は合成が可能である ことを確認する。
具体的には、以下の様な合成方法を採用する。

関手F: A -> C と 関手G: B -> D と 双関手H: C x D -> E を合成したものをH(G, F)とかく。
注意) この表記方法は私が設定した。ちゃんとした記法をご存じの方は教えて下さい。

  • H(F, G)(a, c) = H(F(a), G(c)) a ∈ A, c ∈ B // 対象の対応
  • H(F, G)(f, g) = H(F(f), G(g)) fは圏Aの射 gは圏Bの射 // 射の対応

合成をこの定義にした場合、F, Gの関手であることを仮定した場合ファンクタ則を満たす。


簡易的な証明
圏Aの恒等射id_aと圏Bのid_bは、F, Gによってそれぞれ id_F(a)、id_G(b)に写され、
Hが双関手であることからHによってH(id_F(a), id_G(b)) に写される。
これはまさにid_H(F, G) である。

次に合成則の確認を行う。
j = f ∘ h (jfhは圏Aの射), k = g ∘ i (kgiは圏Bの射)の時、 H(F, G)(j, k) = H(F(j), G(k))
= H(F(f ∘ h), G(g ∘ i))
= H(F(f) ∘ F(h), G(g) ∘ G(i)) // F, Gの関手性
= H(F(f), G(g)) ∘ H(F(h), G(i)) // Hの関手性

よって、H(F, G) は双関手の定義を満たしている。


図で書くと以下のような対応になる。
fig

上図のH(F(f), G(g))をScalaで書くと以下のようになる。

// H(F(f), G(g)) = BiComp
// TODO: 補足説明
// 関手の合成を行った結果がまた双関手である
case class BiComp[BF[_, _], FU[_], GU[_], A, B](v: BF[FU[A], GU[B]])
  implicit def bicompBiFunctor[
    BF[_, _], FU[_], GU[_]](
                           implicit BF: Bifunctor[BF],
                           FU: Functor[FU], GU: Functor[GU]) =
    {
      // partially-applied type BiComp
      type BiCompAB[A, B] = BiComp[BF, FU, GU, A, B]
      new Bifunctor[BiCompAB] {
        override def bimap[A, B, C, D](f: A => C)(g: B => D): BiCompAB[A, B] => BiCompAB[C, D] = {
          case BiComp(x) =>
            BiComp(
              BF.bimap(FU.map(f))(GU.map(g))(x)
            )
        }
      }
    }

とても複雑なコードに見えるが、注目するべきはBF.bimap(FU.map(f))(GU.map(g))(x)が理解できればよい。
新しいデータ型BiCompが双関手であうるのは、fuguが共に関手である場合のみである。

さて、そんなわけで今度こそOptionが双関手であることが分かった。
余談:
前章でOptionが関手である事を等式論証を用いて証明したが、それは不要だったことが分かる。
Optionは2つのfunctorial primitivesの和であるからだ。

TODO: コンパイラで自動で関手かどうか判定する話

8.4 Functors in C++

略。

8.5 The Writer Functor ライター関手

注意) この項は、Ch4を読んでいることを前提としている。飛ばしても良い。

Writer圏を覚えているだろうか?
Writer圏はKleisli圏の一種で、圏の射は通常の関数に何らかの装飾(情報の追加)が合わさったものであった。
まず、定義を復習しよう。

  class Writer[A](val a: A, val log: String) {
    def pure(a: A) = new Writer(a, log="")
    def >=>[B](f: A => Writer[B]):Writer[B] = {
      val w_b = f(a)
      new Writer(w_b.a, log + w_b.log)
    }

    override def toString: String =
      a.toString + "\n" + "="*10 + "\n with log \n" + log + "\n" + "="*10
  }

f:id:sereronnrot:20210224163900j:plain

Writer[_]型コンストラクタはTuple2[_, String]と同型なので関手的である。
では、Writer圏や、より一般にKleisli圏は関手と何らかの関係をもつのだろうか?
まず、Kleisli圏が持つ >=>pure を用いると、以下のようにfmapが作れる事がわかる。

// 実装はWriterで行う  
// シグネチャが正しいか確認してみよう  
// f -> (f, "")   
def fmap[A, B](f: A => B): Writer[A] => Writer[B] = 
identity[Writer[A]] _ >=> (x => pure(f(x)))

簡単そうに見えて、結構複雑な定義である。
流れとしては、identity[Writer[A]]の型コンストラクタは Writer[A] => Writer[A] であり、
(x => pure(f(x)))A => Writer[B]なので、>=> が使用でき、結果的にWriter[A] => Writer[B]が出来る。

よって、Writerは関手とみなせる事がわかった。 更に一般に、Kleisli圏はpureとfmapを持ちファンクタ則も満たすことから関手であることがわかる。
(fmapもpureも実質情報の付与を行っていないため、元の圏の結合律などからファンクタ則が成り立つのは何となく分かると思う)

TODO: parametric polymorphism, Theorem of freeの話

8.6 Covariant and Contravariant Functors 共変関手と反変関手

今まで見てきたWriterを含む殆どの関手は、以下の条件を満たしていた。

  • 条件1: Cの任意の射f, gについて、F(f ∘ g) = F(f) ∘ F(g)

Reader関手も、上の条件を満たしている。

// 今回はIntがドメインのReader関手を作っているが、ドメインは好きなもので良い
type Reader[A] = Int => A
implicit val readerFunctor = new Functor[Reader[A]] {
  def map[A, B](f: A => B)(g: Reader[A]): Reader[B] =
    f compose g
}

ドメインをIntに固定するReader関手(R)のmapは、f: A => Bから、R(f):(Int => A) => (Int => B)であり、 R(A): Int => Aと f ∘ R(A): Int => A => Bという自然な形でR(B)が作成できる。
では、ドメインではなくコドメインを固定したOpという対応を作ってみよう。

  type Op[A] = A => Int
  implicit val opFunctor = new Functor[Op[A]] {
    def map[A, B](f: A => B)(fa: Op[A]): Op[B] = ???
  }

ここで問題が発生する。どう頑張ってもmapが作れない。。。
では、発想を変えて、何だったら作れるだろうかと考えてみると、こんなものが作れる。

def contramap[A, B](f: A => B)(fb: Op[B]): Op[A] = 
  fb compose f

ドメインをIntに固定するOpのcontramapは、f: A => Bから、O(f): (B => Int) => (A => Int)であり、O(B): B => Intと O(B) ∘ f: A => B => Intという自然な形でO(A)が作成できる。

ここで、Reader関手のmapとOp関手?のfmapのシグネチャを比較してみよう。
- Reader.map: (A => B) => Reader[A] => Reader[B]
- Op.contramap: (A => B) => Op[B] => Op[A]

Reader関手は元の圏の射の方向がそのまま受け継がれているが、Op関手?は射の方向を逆にしている事がわかるだろうか。

では、Op関手?の様なものを圏論の言葉で定義していこう。
まず、反対圏の復習をする。(詳しくはCh5.1)

定義: 反対圏 Opposite Category

反対圏 C_opは、圏Cの対象をそのままに、圏Cの射f: A -> Bの定義域(domain)と終域(codomain)を入れ替えたf_op: B -> Aを射とする圏である。
よって、Obj(C) = Obj(C_op) であり、C(A, B) = C_op(B, A)。
合成 ∘op は、 f_op ∘op g_op = (g ∘ f)で与えられる。
また、(C_op)_op = C となる。((C_op)_op)
定義終

Op.contramapは (B => A) => Op[A] => Op[B]と書けるので、圏Cをプログラムの圏とすると、OpはC_opからDへの関手であると言える。(ファンクタ則も満たしている)
Op関手のような関手を反変関手といい、以下のように定義される。

定義: 反変関手 Contravariant Functor

圏Cから圏Dへの反変関手F は、以下の条件を満たす満たす対象、射の対応の組(F1, F2)である。通常、F1,F2を纏めてFと表記する。
F1: Cの対象x -> Dの対象F1(x) への対応
F2: Cにおける射f -> Dにおける射F2(f) への対応
- 条件1: Cの任意の射f, gについて、F(f ∘ g) = F(g) ∘ F(f)
- 条件2: Cの任意の対象xに対して、F(id_x) = id_F(x)
(参考: wikipedia)

条件1が(共変)関手と異なっていることに注意しよう。

f:id:sereronnrot:20210224163949j:plain

また、反変関手FをF: C_op => D、つまりCの反対圏からDへのマッピングとしてみると、普通の関手(共変関手)として扱える。
TODO: 図を書く。

反変関手を定義する型クラスは以下のように書ける。

  trait Contravariant[F[_]] {
    def contramap[A, B](f: B => A)(fa: F[A]): F[B]
  }

これを用いて、Op関手は以下のように反変関手にできる。

  implicit val opContravariant = new Contravariant[Op] {
    override def contramap[A, B](f: B => A)(fa: Op[A]): Op[B] = fa compose f
  }

flip関数を以下のように定義すると、更に簡潔に書けるらしい。(簡潔なんだろうか。。)

  def compose[A, B, C]: (A => B) => (C => A) => C => B = 
    f => g => c => f(g(c))
  def flip[A, B, C]: (A => B => C) => (B => A => C) =
    f => y => x => f(x)(y)
  implicit val opContravariant = new Contravariant[Op] {
    override def contramap[A, B](f: B => A)(fa: Op[A]): Op[B] = flip(compose[A, Int, B])(f)(fa)
  }

ここまでの話を纏めよう。

  • Function1[A, B]Bを固定するとReader関手とみなせ、Aについて共変である。
  • Function1[A, B]Aを固定するとOp関手とみなせ、Bについて反変である。

これは言いかえると、Function1[A, B]は1つ目の型パラメタAに対しては共変であり、2つ目のパラメタBに対しては反変であるといえる。
双関手の記法を用いると以下のように書ける。
Function1: P_op x P => P (Pはプログラミングの圏)

ドメインの直積圏の左側の圏がP_opのように反対圏になっていることに注目してほしい。

8.7 Profunctors プロファンクター

前項で、引数を一つ取って一つの値を返す関数であるFunction1[A, B]型は、1つ目の型パラメタに対しては共変であり、2つ目の型パラメタに対しては反変であることを学んだ。
少し一般化して、2つの圏(C, D)を1つの圏(E) にマッピングする関手Fを考える。
双関手の記法を思い出すと、こういった関手は以下のように書ける。

  • F:: C × D -> E

1つ目の圏C に対して反変にする。

  • F:: C_op × D -> E

この時、圏EがSetならば、以下のように書ける。

  • F:: C_op × D -> Set

この関手Fを、Profunctorと呼ぶ。(Profunctorの訳は?)

プログラムの圏(Hask)の対象は型であり、集合みたいなものだと考えられるので、Profunctorは2つの型パラメタを取る型コンストラクタであると考えられる。
Scalaでは以下のように実装できる。

  trait Profunctor[F[_, _]] {
    // 1つ目のパラメタについて反変であることに注意
    def dimap[A, B, C, D](f: A => B)(g: C => D)(fa: F[B, C]): F[A, D] =
      lmap(f)(rmap(g)(fa))
    // 1つ目のパラメタについて反変であることに注意
    def lmap[A, B, C](f: A => B)(fa: F[B, C]): F[A, C] =
      dimap(f)(identity[C])(fa)
    def rmap[A, C, D](g: C => D)(fa: F[A, C]): F[A, D] =
      dimap(identity[A])(g)(fa)
  }

Bifunctorの時と同じ様に、dimapか、lmaprmapを実装すれば良い。

f:id:sereronnrot:20210224164133j:plain

Function1は以下の様にProfunctorにできる。

  implicit val function1Profunctor = new Profunctor[Function1] {
    override def dimap[A, B, C, D](f: A => B)(g: C => D)(fa: B => C): A => D =
      g compose fa compose f

    override def lmap[A, B, C](f: A => B)(fa: B => C): A => C =
      fa compose f

    override def rmap[A, C, D](g: C => D)(fa: A => C): A => D =
      g compose fa
  }
  import function1Profunctor._
  val f1 = (x: Int) => (x*2).toFloat
  val f2 = (x: Float) => (x*2.5).toString
  val f3 = (x: String) => (x + "!!!").toList

  println(lmap(f1)(f2)(3))
  println(rmap(f2)(f1)(3))
  println(dimap(f1)(f3)(f2)(3))

補足: flipを使った実装
本ではこちらが記載されている。

  trait Profunctor2[F[_, _]] {
    def dimap[A, B, C, D]: (A => B) => (C => D) => F[B, C] =>
       F[A, D] = f => g =>
      lmap(f) compose rmap[B, C, D](g)
    def lmap[A, B, C]: (A => B) => F[B, C] => F[A, C] = f =>
      dimap(f)(identity[C])
    def rmap[A, B, C]: (B => C) => F[A, B] => F[A, C] =
      dimap[A, A, B, C](identity[A])
  }
  implicit val function1Profunctor2 = new Profunctor2[Function1]
   {
    override def dimap[A, B, C, D]: (A => B) => (C => D) => (B
      => C) => (A => D) = ab => cd => bc =>
      cd compose bc compose ab
      override def lmap[A, B, C]: (A => B) => (B => C) => (A =>
         C) =
    flip(compose)
    override def rmap[A, B, C]: (B => C) => (A => B) => (A =>
       C) =
    compose
     }
  import function1Profunctor2._
  println(lmap(f1)(f2)(3))
  println(rmap(f2)(f1)(3))
  println(dimap(f1)(f3)(f2)(3))

ProfunctorはendcoendLensArrowなどの応用先があるが、それはまた本書の後半に扱う。

8.8 The Hom-Functor Hom関手

前項のFunction1の例は、「対象a, bとそれらの間にある射Hom(a, b)のマッピングは、関手(或はProfunctor)である」というより一般的な性質を反映している。
記号的に書くと、Hom-set C(, ) はC_op x C => Set の (Pro)functorということだ。
そんな、「対象a,bとそれらの間にある射Hom(a, b)のマッピング」を、Hom関手 と呼ぶ。

f:id:sereronnrot:20210224164240j:plain

最後に射の関係性を書いてみよう。
C_op × Cの射は以下のような圏Cの射のペアなので、

  • f: a1 -> a
  • g: b -> b1

によるペア(f, g)はHom(a, b)からHom(a1, b1)への射になる。
実際、Hom(a, b)から1つ射hを抜き出した時に、 g ∘ h ∘ fとなり、これはC(a1, b1)の要素である。

Hom関手は非常に重要な関手なので、次の章で重点的に扱う。

TODO: 局所的に小さい県の話

(補足) 関手にならない型コンストラクタはあるのか?

本ではCh10に記載されているが、纏まりを考えてこちらで紹介する。

今まで、関手である型コンストラクタを紹介してきたが、「そもそも関手じゃない型コンストラクタってあるの?」という問に答えていく。
関手じゃないということは、共変でも反変関手でもないということだ。
そんな型コンストラクタは、例えば以下のように作ることができる。

type NotFunctor[A] = A => A

NotFunctor型は、ReaderOp関手を思い出すと、Aに対して共変でもあり反変でもあるようにみえるが、mapcontramapも実装できないので関手にならない。
TODO: 図

8.9 Challenges

Ques 1.
以下に定義されるPairが双関手であることを証明してください。
case class Pair[A, B](a: A, b: B)

Ans 1.
Tuple2と同型なので双関手。
等式論証は省略。

Ques 2.
Option[_]Either[Const[Unit, _], Id[_]]が同型であることを示してください。

type Option[A] = Either[Const[Unit, A], Id[A]]

Hint: Define two mappings between the two implementations. For additional credit, show that they are the inverse of each other using equational reasoning.

Ans 2.
実装の都合上、Const[Unit, A]Const[A]に変更している。

  case class Const[A](v: Unit)
  implicit val constFunctor = new Functor[Const] {
    def map[A, B](f: A => B)(ca: Const[A]): Const[B] =
      Const(ca.v)
  }
  type OptionLike[A] = Either[Const[A], Id[A]]

  def OptionLike2Option[A](a: OptionLike[A]): Option[A] = a match {
    case Left(Const(())) => None
    case Right(a) => Some(a)
  }

  def Option2OptionLike[A](a: Option[A]): OptionLike[A] = a match {
    case None => Left(Const(()))
    case Some(a) => Right(a)
  }
  val opl1:OptionLike[Int] = Left(Const(()))
  val opl2:OptionLike[Int] = Right(2)
  val op1 = Some(5)
  val op2 = None
  println(OptionLike2Option(opl1)) // None
  println(OptionLike2Option(opl2)) // Some(2)
  println(Option2OptionLike(op1)) // Right(5)
  println(Option2OptionLike(op2)) // Left(Const(()))
  assert(op1 == OptionLike2Option(Option2OptionLike(op1)))
  assert(op2 == OptionLike2Option(Option2OptionLike(op2)))

TODO: 等式論証

Ques 3.
以下のようにPreListを定義します。
これは、List型の再帰部分を型パラメタBで置き換えたものになります。
PreListBifunctorインスタンスであることを示してください。
(補足: by recursively applying PreList to itself, you can recover List. くわしくは不動点を学ぶときに解説する)

sealed trait PreList[+A, +B]
case object Nil extends PreList[Nothing, Nothing]
case class Cons[A, B](a: A, b: B) extends PreList[A, B]

Ans 3.
以下のようにしてPreListBifunctorインスタンスに出来る。

implicit val preList2Bifunctor = new Bifunctor[PreList] {
  override def bimap[A, B, C, D](f: A => C)(g: B => D): PreList[A, B] =>
    PreList[C, D] = {
    case Nil => Nil
    case Cons(a, b) => Cons(f(a), g(b))
  }
}

また、Nil, A,BはADTの基本的な構成物であり、PreListはそれらの積和で表現されるため、双関手である。

Ques 4.
これらのデータ型がA, Bの双関手であることを示してください。
TODO: ペンディング そもそもdata K2 c a b = K2 cscalaで書く方法がわからない...

おしまい

参考URL