halcat0x15a/free_ap.md

## free_ap.md

      
    Raw
  

              free_ap.md
            
          
    Free Applicative Functors

@halcat0x15a
http://arxiv.org/abs/1403.0749
はなすこと


Applicativeについて
Free Applicativeについて
圏論的な

Applicative

Monadをより一般化したもの
class Functor f ⇒ Applicative f where
  pure :: a → f a
  (<*>) :: f (a → b) → f a → f b
(<*>)は順次計算して1番目の引数に2番目の引数を適用する演算
(<*>)は任意のarityの関数に適用できる
pure f <*> a <*> b
Monadより軽量に記述できる.
do
  x <- a
  y <- b
  return $ f x y
Free Monad

FreeはHaskellではとてもよく知られているデータ構造
data Free f a
  = Return a
  | Free (f (Free f a))
しかし計算構造は実行するまでわからない
Free Applicative

実装は左結合か右結合で異なるが同形
sealed trait Free[F[_], A]

case class Pure[F[_], A](a: A) extends Free[F, A]

abstract case class Apply[F[_], A]() extends Free[F, A] {
  type I
  def f: F[I => A]
  def k: Free[F, I]
}
FがFunctorのときFreeはApplicative
implicit def free[F[_]](implicit F: Functor[F]) =
  new Applicative[({ type G[A] = Free[F, A] })#G] {
    def pure[A](a: A): Free[F, A] = Pure(a)
    override def map[A, B](fa: Free[F, A])(f: A => B): Free[F, B] =
      fa match {
        case Pure(a) => Pure(f(a))
        case Apply(fa: F[A], g: Free[F, A => B]) => Apply(F.map(fa)(f), map(g)(f compose _))
      }
    def apply[A, B](fa: Free[F, A])(f: Free[F, A => B]): Free[F, B] =
      f match {
        case Pure(g) => map(fa)(g)
        case f@Apply() => Apply(f.f, apply(fa)(map(f.k)(g => (a: A) => g(_: B)(a))))
      }
  }
Freeの(<*>)はListの(++)のように定義される
Example: Option parser

Free Monadより有用なFree Applicativeの例
create_user --username halcat0x15a --fullname SanshiroYoshida --id 346
case class User(username: String, fullname: String, id: Int)

case class Opt[A](name: String, default: Option[A], reader: String => Option[A])

def username: Free[Opt, String] = one(Opt("username", None, Some[String]))
def fullname: Free[Opt, String] = one(Opt("fullname", Some(""), Some[String]))
def id: Free[Opt, Int] = one(Opt("id", None, s => allCatch.opt(s.toInt)))

def user: Free[Opt, User] = Applicative.map(username, fullname, id)(User)

作用が独立
解析が可能

Left adjoint

「Free Applicativeは単なるApplicativeの圏から自己関手の圏への忘却関手の左随伴だよ, なにか問題でも?」
trait Nat[F[_], G[_]] {
  def apply[A]: F[A] => G[A]
}

def lift[F[_], G[_]](f: Nat[F, G])(implicit F: Functor[F], G: Functor[G]): Nat[({ type H[A] = Free[F, A] })#H, ({ type H[A] = Free[G, A] })#H] =
  new Nat[({ type H[A] = Free[F, A] })#H, ({ type H[A] = Free[G, A] })#H] {
    def apply[A] = {
      case Pure(x) => Pure(x)
      case a@Apply() => Apply(f[a.I => A](a.f), lift(f).apply[a.I](a.k))
    }
  }
FreeはFunctorからApplicativeを構成できる
def one[F[_], A](fa: F[A])(implicit F: Functor[F]): Free[F, A] =
  Apply(F.map(fa)(const[A, Unit]), Pure(()))
随伴

Hom_A(Free f, g)とHom_F(f, g)が同形
def raise[F[_], G[_]](f: Nat[F, G])(implicit G: Applicative[G]): Nat[({ type H[A] = Free[F, A] })#H, G] =
  new Nat[({ type H[A] = Free[F, A] })#H, G] {
    def apply[A] = {
      case Pure(a) => G.pure(a)
      case a@Apply() => G(raise(f).apply[a.I](a.k))(f[a.I => A](a.f))
    }
  }

def lower[F[_], G[_]](f: Nat[({ type H[A] = Free[F, A] })#H, G])(implicit F: Functor[F], G: Applicative[G]): Nat[F, G] =
  new Nat[F, G] {
    def apply[A] = f[A] compose one[F, A]
  }
raiseはFreeを解析できる
def parserDefault = raise(new Nat[Opt, Option] { def apply[A] = _.default })

def allOptions = raise[Opt, ({ type F[A] = List[String] })#F](new Nat[Opt, ({ type F[A] = List[String] })#F] { def apply[A] = _.name :: Nil })(Monoid.list.applicative)
まとめ


Free Applicativeは構造の解析が可能
Free Applicativeは単なるApplicativeの圏から自己関手の圏への忘却関手の左随伴