LoginSignup
12
13

More than 5 years have passed since last update.

@lyrical_logical(lyrical logical)

たいぱーの気持ちになるですよ！

Last updated at Posted at 2015-12-28

型システムとなかよしになる話

怪しげな Any

Qiita の Scala Advent Calendar 24 日目の記事、@halcat0x15a さんの Scalaで書くFreer Monads, More Extensible Effects はもう見ましたか？まあまだ見てない、見たけどよく分からなかったという人も大丈夫、Freer の話はしません。型の話をします。
前述の記事から今回見る部分だけコードを抜いてくると、こんな感じです。

sealed trait Freer[F[_], A] {
  def map[B](f: A => B): Freer[F, B] = flatMap(a => Pure(f(a)))
  def flatMap[B](f: A => Freer[F, B]): Freer[F, B] =
    this match {
      case Pure(a) => f(a)
      case Impure(fa, g) => Impure(fa, g :+ f)
    }
}
case class Pure[F[_], A](a: A) extends Freer[F, A]
case class Impure[F[_], A, B](fa: F[A], f: Queue[F, A, B]) extends Freer[F, B]

sealed trait Queue[F[_], A, B] {
  def :+[C](f: B => Freer[F, C]): Queue[F, A, C] = Node(this, Leaf(f))
  def ++[C](q: Queue[F, B, C]): Queue[F, A, C] = Node(this, q)

  def apply(a: A): Freer[F, B] = {
    @scala.annotation.tailrec
    def go(q: Queue[F, Any, B], a: Any): Freer[F, B] =
      q.view match {
        case One(f) => f(a)
        case Cons(f, q) =>
          f(a) match {
            case Pure(v) => go(q, v)
            case Impure(f, r) => Impure(f, r ++ q)
          }
      }
    go(this.asInstanceOf[Queue[F, Any, B]], a)
  }

  def view: View[F, A, B] =
    this match {
      case Leaf(f) => One(f)
      case Node(l, r) =>
        @scala.annotation.tailrec
        def go(x: Queue[F, A, Any], y: Queue[F, Any, B]): View[F, A, B] =
          x match {
            case Leaf(f) => Cons(f, y)
            case Node(l, r) => go(l, Node(r, y))
          }
        go(l, r)
    }
}
case class Leaf[F[_], A, B](f: A => Freer[F, B]) extends Queue[F, A, B]
case class Node[F[_], A, B, C](left: Queue[F, A, B], right: Queue[F, B, C]) extends Queue[F, A, C]

sealed trait View[F[_], A, B]
case class One[F[_], A, B](f: A => Freer[F, B]) extends View[F, A, B]
case class Cons[F[_], A, B, C](f: A => Freer[F, B], q: Queue[F, B, C]) extends View[F, A, C]

明らかにやばそうな部分がありますね。

  def apply(a: A): Freer[F, B] = {
    @scala.annotation.tailrec
    def go(q: Queue[F, Any, B], a: Any): Freer[F, B] =
      q.view match {
        case One(f) => f(a)
        case Cons(f, q) =>
          f(a) match {
            case Pure(v) => go(q, v)
            case Impure(f, r) => Impure(f, r ++ q)
          }
      }
    go(this.asInstanceOf[Queue[F, Any, B]], a)
  }

  def view: View[F, A, B] =
    this match {
      case Leaf(f) => One(f)
      case Node(l, r) =>
        @scala.annotation.tailrec
        def go(x: Queue[F, A, Any], y: Queue[F, Any, B]): View[F, A, B] =
          x match {
            case Leaf(f) => Cons(f, y)
            case Node(l, r) => go(l, Node(r, y))
          }
        go(l, r)
    }

Queue#view では Any が、Queue#apply にいたっては asInstanceOf が使われています。すごく怖い！でもなんだか、型以外は正しいように見える…
というわけで、どうしてこんなコードになっているのか調べてみましょう。

パターンマッチと GADT

apply から見ていきます。

  def apply(a: A): Freer[F, B] = {
    @scala.annotation.tailrec
    def go(q: Queue[F, Any, B], a: Any): Freer[F, B] =
      q.view match {
        case One(f) => f(a)
        case Cons(f, q) =>
          f(a) match {
            case Pure(v) => go(q, v)
            case Impure(f, r) => Impure(f, r ++ q)
          }
      }
    go(this.asInstanceOf[Queue[F, Any, B]], a)
  }

第一引数は Queue[F, Any, B] ではなく Queue[F, A, B] 、第二引数は Any ではなく A のはずです。Any を A にかえ、それに伴って asInstanceOf も消してコンパイルしてみます。

freer.scala:26: error: type mismatch;
 found   : Queue[F,Any,B]
 required: Queue[F,A,B]
Note: Any >: A, but trait Queue is invariant in type A.
You may wish to define A as -A instead. (SLS 4.5)
            case Pure(v) => go(q, v)
                               ^
freer.scala:26: error: type mismatch;
 found   : v.type (with underlying type Any)
 required: A
            case Pure(v) => go(q, v)
                                  ^
two errors found

しかられてしまいました。何々、一つ目は、A が必要な箇所で Any が出てきているが、Queue の型パラメタである A が invariant であるためにコンパイルが通らない、contravariant にしてみろ…？
コンパイラの「親切な」エラーメッセージに騙されてはいけません。そもそも Any が出てくるのがおかしな話なのです。というか A は view の定義を見れば分かるように、covariant な位置にも出てくるので contravariant にはできません。

さて何故 Any が出てきてしまっているのか、結論からいうとこれは View クラスのサブクラスである Cons の constructor pattern に起因しています。

      q.view match {
        case One(f) => f(a)
        case Cons(f, q) =>

sealed trait View[F[_], A, B]
case class One[F[_], A, B](f: A => Freer[F, B]) extends View[F, A, B]
case class Cons[F[_], A, B, C](f: A => Freer[F, B], q: Queue[F, B, C]) extends View[F, A, C]

View が型パラメタを三つ持つのに対して、サブクラスである Cons は型パラメタを四つ持っています。
q.view の型は Queue[F, A, B] です。q.view の結果が仮に Cons[F, A, B, C] 型の値であるとして、パターンマッチ時に型パラメタを全て推論することは可能でしょうか？
勿論、これは原理的にできません。Cons[F, A, B, C] は Queue[F, A, C] のサブクラスです。B の型を知ることは出来ません。ここでコンパイラが根をあげてしまうわけです。パターンマッチの結果得られる値の型は、Cons[F, A, Any, B] になってしまいます。
このような、親クラスより型パラメタを多く持つクラスに対して、constructor pattern を適用する時、型パラメタの一部は推論できません。これは仕方のないことです。

Polymorphic recursion

最初のエラーでは、A が Any になれないのが問題だといっていました。なら、以下のように変更してしまってはどうでしょうか？

    def go[A0](q: Queue[F, A0, B], a: A0): Freer[F, B] =

メソッド go に型パラメタ A0 を追加しています。これなら A だろうと Any だろうと扱えるので問題ないはずです。しかし…

freer.scala:22: error: could not optimize @tailrec annotated method go: it contains a recursive call not in tail position
      q.view match {
        ^
one error found

しかられてしまいました。型パラメタを取るメソッド（関数）が、異なる型パラメタを受け取りながら再起呼び出しを行う、このようなものを polymorphic recursion と呼びます。Scala のコンパイラは polymorphic recursion に対する末尾再帰最適化を認めていません。そんなー。ちなみに tailrec アノテーションはずすとちゃんとコンパイルは通ります。

Existential type ～模索編～

こうなったら型パラメタ以外の方法で、多相的にしてやるしかありません…そうです、existential type です。

    def go(q: Queue[F, T forSome { type T }, B], a: T forSome { type T }): Freer[F, B] =

これは駄目です。コンパイラのエラーは長くなるので省略しますが、結局のところ existential type として導入された型 T は、名前は同じでも、引数 q に表れるものと引数 a に表れるものは別の型です。
ならば同じであることを教えてやればいい、とそこそここなれた感じの Scala プログラマなら思うはずです。

    def go(q: Queue[F, T, B] forSome { type T }, a: U forSome { type U })(implicit ev: T =:= U): Freer[F, B] =

implicit パラメタと =:= により、コンパイラに二つの型が同じであることを伝えようとしますが…forSome により導入される existential type は、スコープがその型宣言内に限られます。具体的には以下のようなエラーメッセージで、分かりやすくしかられます。

freer.scala:21: error: not found: type T
    def go(q: Queue[F, T, B] forSome { type T }, a: U forSome { type U })(implicit ev: T =:= U): Freer[F, B] =
                                                                                       ^
freer.scala:21: error: not found: type U
    def go(q: Queue[F, T, B] forSome { type T }, a: U forSome { type U })(implicit ev: T =:= U): Freer[F, B] =
                                                                                             ^

existential type には upper/lower bound 以外の制約も書けるようにして欲しい…元々が Java の wild card に合わせた機能なので、仕方ないですけど…

Existential type ～解決編～

forSome のスコープが狭いなら、その狭いスコープに押し込んでやるしかない…ということで、メソッド go のシグネチャを変更して、引数として Tuple2[Queue[F, T, B], T] forSome { type T } をとるようにしてしまいましょう。

   def go(q_a: (Queue[F, T, B], T) forSome { type T }): Freer[F, B] =

コンパイルが無事通りました！やったぜ、これが existential type の力だ！
Queue#view も同様の方針で、Any を使わない実装に変更することができます。

真っ当な解決方法

実はこれ、後で聞いたところ @halcat0x15a さんも独自に Any や asInstanceOf を使わない実装を既に書いていました。そのコードはちょっと難しくて、Freer の本質ではない部分で、記事の読み手を困らせてしまうかもしれません。それで Any や asInstanceOf を使うバージョンを Qiita の記事で公開したのだと思います。

@halcat0x15a さんの方針はこうです。「サブクラスの型パラメタが多いのが悪い。型パラメタではなく type member にしてしまおう」ものすごく真っ当ですね。言い訳すると、自分も最初はその方針でやってたんですが、途中でエラーと戦うのに飽きて方針転換しました。嘘です本当は普段出番のない forSome を使いたかっただけです…forSome すごいですよ scalac とか sbt で確か二箇所くらいしか使われてませんし、二箇所とも forSome 必要ないですからね…

type member による型パラメタの置き換え

ということで、型パラメタが親クラスより多い Node と Cons 周りの定義を type member を使うように置き換えましょう。

abstract class Node[F[_], A, B] extends Queue[F, A, B] {
  type C
  def left: Queue[F, A, C]
  def right: Queue[F, C, B]
}
object Node {
  def apply[F[_], A, B, C0](l: Queue[F, A, C0], r: Queue[F, C0, B]): Node[F, A, B] = new Node[F, A, B] {
    type C = C0
    def left = l
    def right = r
  }
}

abstract class Cons[F[_], A, C] extends View[F, A, C] {
  type B
  def head: A => Freer[F, B]
  def tail: Queue[F, B, C]
}
object Cons {
  def apply[F[_], A, B0, C](h: A => Freer[F, B0], t: Queue[F, B0, C]): Cons[F, A, C] = new Cons[F, A, C] {
    type B = B0
    def head = h
    def tail = t
  }
}

特にいうこともないですね。case class でなくしたので constructor pattern が使えなくなったことくらいでしょうか。代わりに typed pattern を使います。case class にしたり unapply 実装したりして constructor pattern を使えるようにしてもいいのですが、どの道 as pattern（Scala だと Pattern Binders というらしいと今知った）を使う必要があるので…

path-dependent type による型としての値

準備も整ったので早速 Queue#apply メソッドを修正しましょう。問題は、型情報が足りないために、Any が出てきてしまうことでした。
型情報が足りないというなら、足してやればいいのです。

    def apply(a: A): Freer[F, B] = {
      @scala.annotation.tailrec
      def go(tpe: { type C })(q: Queue[F, tpe.C, B], a: tpe.C): Freer[F, B] =
        q.view match {
          case One(f) => f(a)
          case cons: Cons[F, tpe.C, B] =>
            cons.head(a) match {
              case Pure(v) => go(new { type C = cons.B })(cons.tail, v)
              case Impure(f, r) => Impure(f, r ++ cons.tail)
            }
        }
      go(new { type C = A })(this, a)
    }

メソッド内メソッドの go の第一引数がなにやらよく分からないことになっていますが、これはそのまま「C という名前の type member を持つ型」です。この引数の役割は、型情報を持ちまわることです。
go の第一引数には、コンテキストにあわせて最適な型（を type member として持つ型）が渡されるようにしてやります。polymorphic recursion によってできなかった、型パラメタを使ったジェネリックな定義と、やっていることは同じです。型の変わりに、型を持つ値を渡しているわけです。Scala には path-dependent type がありますから、制限はありますが値から型を取り出すことができます。勿論 path-dependent type と型パラメタではセマンティクスは違うので何でも代替できるわけではありませんが…

ところで、以下のように定義するのは間違いです。

def go(tpe: { type C }, q: Queue[F, tpe.C, B], a: tpe.C): Freer[F, B] =

この場合、引数 q や a の型宣言をする時点で、まだ tpe が見えません。引数 q や a の型宣言で tpe が見えるように、パラメーターリストを分ける必要があるわけです。この手の問題は、Scala では残念ながら稀によくあります。普通のコードを書いてる分には滅多にありませんのでご安心ください。

メソッド view も同じように修正したいところですが、こちらは apply と違い、クラス Queue 内で実装しようとすると type member の扱いに困ります。素直に各サブクラスで定義する形にしましょう。Leaf での定義は自明なので Node だけ。

abstract class Node[F[_], A, B] extends Queue[F, A, B] {
  type C
  def left: Queue[F, A, C]
  def right: Queue[F, C, B]
  def view: View[F, A, B] = {
    @scala.annotation.tailrec
    def go(tpe: { type C })(left: Queue[F, A, tpe.C], right: Queue[F, tpe.C, B]): View[F, A, B] =
      left match {
        case Leaf(value) => Cons(value, right)
        case node: Node[F, A, tpe.C] => {
          go(node)(node.left, Node(node.right, right))
        }
      }
    go(this)(left, right)
  }
}

Queue#apply と大した差はないですね。型情報を伝えるための第一引数に this や node をそのまま渡していることくらいでしょうか。勿論、Queue#apply のように記述することもできます。

まとめ

長々とあれこれ書きましたが、なんというか全体的にめんどくさいとしかいいようがない。これを読んだ人が、この記事で学んだ知識を使わずに済むことを祈っています。type member や path-dependent type は、うまく使うと型パラメタを使うより綺麗に抽象化できることもあるので知っておいたほうが良いですが、existential type はなあ…

コードまとめ

existential type を使ったコード。

freer_with_existential_type.scala
import scala.language.higherKinds
import scala.language.existentials

sealed trait Freer[F[_], A] {
  def map[B](f: A => B): Freer[F, B] = flatMap(a => Pure(f(a)))
  def flatMap[B](f: A => Freer[F, B]): Freer[F, B] =
    this match {
      case Pure(a) => f(a)
      case Impure(fa, g) => Impure(fa, g :+ f)
    }
}

case class Pure[F[_], A](a: A) extends Freer[F, A]
case class Impure[F[_], A, B](fa: F[A], f: Queue[F, A, B]) extends Freer[F, B]

sealed trait Queue[F[_], A, B] {
  def :+[C](f: B => Freer[F, C]): Queue[F, A, C] = Node(this, Leaf(f))
  def ++[C](q: Queue[F, B, C]): Queue[F, A, C] = Node(this, q)
  def apply(a: A): Freer[F, B] = {
    @scala.annotation.tailrec
    def go(q_a: (Queue[F, T, B], T) forSome { type T }): Freer[F, B] =
      q_a match {
        case (q, a) =>
          q.view match {
            case One(f) => f(a)
            case Cons(f, q) =>
              f(a) match {
                case Pure(v) => go(q, v)
                case Impure(f, r) => Impure(f, r ++ q)
              }
          }
      }
    go(this, a)
  }
  def view: View[F, A, B] =
    this match {
      case Leaf(f) => One(f)
      case Node(l, r) =>
        @scala.annotation.tailrec
        def go(x_v: (Queue[F, A, T], Queue[F, T, B]) forSome { type T }): View[F, A, B] =
          x_v match {
            case (Leaf(f), y) => Cons(f, y)
            case (Node(l, r), y) => go(l -> Node(r, y))
          }
        go(l -> r)
    }
}
case class Leaf[F[_], A, B](f: A => Freer[F, B]) extends Queue[F, A, B]
case class Node[F[_], A, B, C](left: Queue[F, A, B], right: Queue[F, B, C]) extends Queue[F, A, C]

sealed trait View[F[_], A, B]
case class One[F[_], A, B](f: A => Freer[F, B]) extends View[F, A, B]
case class Cons[F[_], A, B, C](f: A => Freer[F, B], q: Queue[F, B, C]) extends View[F, A, C]

type member と path-dependent type を使ったコード。

freer_with_type_member.scala
import scala.language.higherKinds
import scala.language.existentials

sealed trait Freer[F[_], A] {
  def map[B](f: A => B): Freer[F, B] = flatMap(a => Pure(f(a)))
  def flatMap[B](f: A => Freer[F, B]): Freer[F, B] =
    this match {
      case Pure(a) => f(a)
      case Impure(fa, g) => Impure(fa, g :+ f)
    }
}
case class Pure[F[_], A](a: A) extends Freer[F, A]
case class Impure[F[_], A, B](fa: F[A], f: Queue[F, A, B]) extends Freer[F, B]

sealed trait Queue[F[_], A, B] {
  def :+[C](f: B => Freer[F, C]): Queue[F, A, C] = Node(this, Leaf(f))
  def ++[C](q: Queue[F, B, C]): Queue[F, A, C] = Node(this, q)

    def apply(a: A): Freer[F, B] = {
      @scala.annotation.tailrec
      def go(tpe: { type C })(q: Queue[F, tpe.C, B], a: tpe.C): Freer[F, B] =
        q.view match {
          case One(f) => f(a)
          case cons: Cons[F, tpe.C, B] =>
            cons.head(a) match {
              case Pure(v) => go(new { type C = cons.B })(cons.tail, v)
              case Impure(f, r) => Impure(f, r ++ cons.tail)
            }
        }
      go(new { type C = A })(this, a)
    }

  def view: View[F, A, B]
}
case class Leaf[F[_], A, B](f: A => Freer[F, B]) extends Queue[F, A, B] {
  def view: View[F, A, B] = One(f)
}
abstract class Node[F[_], A, B] extends Queue[F, A, B] {
  type C
  def left: Queue[F, A, C]
  def right: Queue[F, C, B]

  def view: View[F, A, B] = {
    @scala.annotation.tailrec
    def go(tpe: { type C })(left: Queue[F, A, tpe.C], right: Queue[F, tpe.C, B]): View[F, A, B] =
      left match {
        case Leaf(value) => Cons(value, right)
        case node: Node[F, A, tpe.C] => {
          go(node)(node.left, Node(node.right, right))
        }
      }
    go(this)(left, right)
  }
}
object Node {
  def apply[F[_], A, B, C0](l: Queue[F, A, C0], r: Queue[F, C0, B]): Node[F, A, B] = new Node[F, A, B] {
    self =>
    type C = C0
    def left = l
    def right = r
  }
}

sealed trait View[F[_], A, B]
case class One[F[_], A, B](f: A => Freer[F, B]) extends View[F, A, B]
abstract class Cons[F[_], A, C] extends View[F, A, C] {
  type B
  def head: A => Freer[F, B]
  def tail: Queue[F, B, C]
}
object Cons {
  def apply[F[_], A, B0, C](h: A => Freer[F, B0], t: Queue[F, B0, C]): Cons[F, A, C] = new Cons[F, A, C] {
    type B = B0
    def head = h
    def tail = t
  }
}
12
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
12
13