---
layout: default
title: Free Applicative
---

# Free Applicative

## Abstract

applicativeはmonadを抽象化したもの.monadとapplicativeは(Haskellのように純粋な言語で)作用のある計算を表現する.
applicativeはpriori(演繹的)に固定された計算構造の時にmonadより好ましい.それはapplicative valuesの静的解析を可能にする.
free applicative functorを定義し, 適切な法則(applicative laws)を満たすことと, 構造が忘却関手への左随伴であることを示す.
free applicative functorsは静的解析のDSLの実装に使うことができる.

## Introduction

HaskellのFree monadはよく知られており,実践的に使われる構造である.
任意の自己関手fをとり, free monadのfは単純な帰納的定義を得る.
```haskell
data Free f a = Return a | Free (f (Free f a))
```
この構造の代表的な使用例はDSLを作ることである.この文脈でfunctor fは大抵*basic operations*を表現するfunctorの直和型であり, DSLはそれらのoperationを含む小さな組み込み言語となる.
free monad approachのひとつの問題はmonadic DSLで書かれたプログラムが静的解析できないことである.monadic computationの構造を検査することはそれを実行するまで不可能である.
この論文では*free construction*がapplicative functorの文脈で実現可能であることを示す.特に次のことに寄与する.
* haskellで2つのfree applicative functorを定義し, それらが等価であることを示す.
* それは実際applicative functorでかつ厳密なfreeであるという意味で定義が正しいことを証明する.
* コードをエレガントにする, 重複を削除するまたはfree monadを使うときにはできない確かな最適化を有効にする幾つかのapplicative functorを使う例を紹介する.
* この定義とすでにある似たアイデアの実装を比較する
この論文はhaskellを知っているプログラマを対象としている.applicative functorに親しんでいる必要はないがこの仕事のモチベーションを理解するのに役立つ.定義の正当化に圏論の概念を使うがこの論文のhaskellのコードはそれ自身で理解できる.

### Applicative functors

Applicative functorsはまずmonadより軽量な記述を提供する方法として紹介される.それらは, 効果的なparserや正規表現, 双方向ルーティングなど違った種類のアプリケーションで使われる.
Applicative functorsは次のような型クラスで定義される.
```haskell
class Functor f ⇒ Applicative f where
pure::a → f a
( <*> ) :: f (a → b) → f a → f b
```
アイデアはfの値がaを結果として返す作用をもつ計算を表現する.pureは作用なしに自明な計算を作るメソッドであり, <*>は二つの計算を逐次実行し, 最初に返った関数を二番目に返った値に適用する.
Monadはapplicative functorを簡素な方法で作ることができ, 多くの実践的なhaskell programmingにおけるモナドは自然に有意な数の実践的に便利なapplicative functorを結果とする.
applicativeはmonadから生じないが, それは広く普及し, おそらくそれは比較的簡単に存在しているapplicativeと合成し, 構成するテクニックはよく研究された新しいものである.
この論文ではapplicative functor FreeA f(fはFunctor)を定義し, 新しく多様性のあるアプリケーションを作成する体系的な方法を提供する.
FreeAの意味はsection 7で明らかになる.以下の例の利益はFreeA fがfにより作られたもっともシンプルなものになると考えられる.


### Example: option parsesr

free applicativeの構築の解説はコマンドラインツールのオプションのパーサの例を実行する練習に使われる.
単純に一つの引数だけとるオプションを受け付けるだけのインターフェースを制約とする.オプション名に--をつけた物を使う.
たとえばunix systemで新しいユーザを作るツールは次のように使われるだろう.
```
 create_user --username john \
             --fullname "John Doe" \
             --id 1002
```
パーサーは引数リストの上で実行することができ, 次のようなレコード型を返す.
```haskell
data User = User
{ username :: String
, fullname :: String
,id::Int} deriving Show
```
そのうえ得られたパーサはすべてのオプションをサポートするsummaryを自動的に生成し, ツールのユーザーにドキュメントを送ることができる.
独立したオプションのパーサを表現するデータ構造をfunctorとして定義できる.
```haskell
data Option a = Option
{ optName :: String
, optDefault :: Maybe a
, optReader :: String → Maybe a} deriving Functor
```
いま完全なパーサを表現する一つの値を違った型のオプションを合成できるOption functorをベースとしたDSLを作ることを望む.紹介で述べた通り, 通常Free monadを使ってDSLを作成する.しかしながらOption functorを使ったFree monadは便利ではない.まず, オプションの列は独立しており, 後のオプションは前のひとつのパースした値に依存しない.次に, monadはそれを実行するまで調べることができず, 自動的にパーサのオプションを得ることができない.
本当に必要なものは独立したオプションの返す値をApplicativeを使って合成できるparser DSLを構築する方法である.そしてそれはFreeAが提供する.
従って組み込みDSLとしてFreeAを使うなら, 明示されない数のオプションのパーサの型を解釈することができる.実行した時それらのオプションは再びコマンドライン入力に任意の順番でマッチし, 結果の値は最終的な結果をえるために合成される.
具体例として次のようなcreate_userのコマンドラインオプションパーサを表現する.
```haskell
userP :: FreeA Option User userP =
User <$> one (Option "username" Nothing Just) <*> one (Option "fullname" (Just "") Just) <*> one (Option "id" Nothing readInt)
readInt :: String → Maybe Int
```
*generic smart constructor*が必要である.
```haskell
one :: Option a → FreeA Option a
```
これはoptionをparserに持ち上げる.

### Example: limited IO
### Example: applicative parsers

Alternativeのインスタンスは得られない

# Definition

functor fにより生成されたfree applicative functorの適切な定義を得ることは, functorの記述を一般化することを通してapplicativeの定義に自然に到達することを反映していったん休止する.

```haskell

class Functor f ⇒ MultiFunctor f where
fmap0 ::a→fa
fmap1 ::(a→b)→fa→fb fmap1 = fmap
fmap2 ::(a→b→c)→fa→fb→fc
```

**Applicative functorへの布石**

```
h x1 x2···xn 􏰂= pure h<*>x1 <*>x2 <*>···<*>xn
```

pureに対応する`PureL`という構造と<*>に対応する:*:という構造をつかう形式的な表現で作ることができる.

```haskell
PureL h :*: x1 :*: x2 :*: · · · :*: xn
```

対応する機能的な定義は次のようになる.

``haskell
data FreeAL f a =
  PureL a
| ∀b.FreeAL f (b → a):*:f b

infixl 4 :*:
```

***右結合版***

```haskell
data FreeA f a
= Pure a
| ∀b.f (b → a):$:FreeA f b
infixr 4 :$:
```

FreeALとFreeAは同値であり,これからは右結合版を公式な定義として取り上げる.単純なFunctorとApplicativeの定義は次のようになる.

```haskell
instance Functor f ⇒ Functor (FreeA f) where
fmap g (Pure x) = Pure (g x)
fmap g (h:$:x) = fmap (g◦) h:$:x
```

単純な定義の適用でfunctor則は構造的帰納法で証明できる.

```haskell
instance Functor f ⇒ Applicative (FreeA f) where
pure = Pure
Pure g<*>y = fmap g y
(h :$: x) <*> y = fmap uncurry h :$: ((,)<$>x<*>y)
```

Applicativeの最後の節は, hがf (x → y → z)でFreeA f zの値を返す必要がある.
:$:は1引数の関数のアプリケーションを表現することができ, uncurry hはf ((x , y) → z)の値を得, FreeA f (x , y)の値をxとyのペアに<*>を再帰的に使い, 最後に:$:で結果を作成する. Note: <*>とリストの++の定義の間で類推

# Applications

## Example: option parsers (continued)

free applicativeに定義を使って, section 1.2のuserPの定義で見せたcommand line option parserを合成することができる.この言語のtermにoptionを持ち上げるスマートなコンストラクタのoneは次のように実装できる.
```haskell
one :: Option a → FreeA Option a
one opt = fmap const opt :$: Pure ()
```
section 7で任意のfunctorにoneを一般化し, generic functionを使ってparserの定義を静的解析できる随伴の部分を記す.functionは可能なオプションを列挙することができ, 任意の順番でコマンドラインから引数のリストをパースする.

## Example: limited IO (continued)

## Summary of examples

Applicative functorは作用のある計算を記述することに便利である.free applicativeはapplicative operatorにより組み立てられるDSLのtermになる組み込み言語のbasic operationsを記したfunctorの上に構築する.それらのtermは左結合形式(純粋な関数に作用ある引数を適用される)のもっとも助けになる記述をする作用ある計算を表現する可能性がある.引数の計算は作用を必要とするかもしれないが, 最後の引数はpure functionにより合成され, applicative式記すとき作用は固定されることを意味する.
userPの例の場合, pure functionはUserのコンストラクタにより得られ, *basic operation*であるOptionは一つのoptionにより定義している.実行される作用と実行順序はFreeA Optionの式により定義される評価機に依存する.
例えばFreeAを使ってデータベースのクエリ言語を定義したとき, applicative式を解析し独立したデータベースのクエリ情報を集めることができるかもしれない.そのとき, 重複した重いクエリがマージされ, 作用ある計算の実行が一回だけにすることができる.言語の式の制限は評価機によりfreedomになる.
Free monadをつかったDSLの式をFreeAと次のようなfree applicativeをfree monadに持ち上げる関数を使って部分的に定義できるかもしれない.
```haskell
liftA2M::Functor f ⇒ FreeA f a → Free f a
liftA2M (Pure x) = Return x
liftA2M (h :$: x) = Free (fmap (λf → fmap f (liftA2M x)) h)
```
式の一部はfree monadを使って定義し, 作用の順序は固定され, 実行される作用は直前の作用のある計算の結果に依存することができ, free applicativeは他に依存しない作用で固定された構造を持つ.monadicな計算の部分は静的解析の結果に依存することができる.

```haskell
test :: FreeA FileSystem Int → Free FileSystem () test op = do
...
let n = count op -- result of static analysis
n′ ← liftA2M op -- result of applicative computation
max ← read "max"
when (max 􏰃 n + n′) $ write "/tmp/test" "blah"
...
```
手で記述する必要のあるもののかわりに静的解析の結果を使った可能性は余剰が少なくプログラムをつくることができる.

# Parametricity

free applicativeを証明するために定義を観測する必要がある.
:$:は存在型を使って定義される.それはそれ以外にないほどクリアであり, g :$: xの値を与え,隠れたtype bを作ることできる.
より特別に, 幾つかのFreeA fの関数は:$:の定義の存在量化された変数bにより多相的に定義される.
この直感的な明確さはrelational parametricityの記述をアピールする.
```haskell
(:$:)::∀b.f (b → a) → (FreeA f b → FreeA f a)
```
これは半変関手の自然変換である.haskellのnewtypeを使ってcontravariant functorであることを定義できる.

```haskell
newtype F1 f a x = F1 (f (x → a))
newtype F2 f a x = F2 (FreeA f x → FreeA f a)
instance Functor f ⇒ Contravariant (F1 f a) where contramap h (F1 g) = F1$fmap (◦h) g
instance Functor f ⇒ Contravariant (F2 f a) where contramap h (F2 g) = F2$g◦fmap h
```
morphismsのF1とF2のアクションは明白な方法で定義される. Note: FreeA fはFunctorである.
:$:はxとyが与えられ, h : x → yの関数を意味する.
```
∀g::f (y → a),u::FreeA f x.
fmap (◦h) g:$:u ≡ g:$:fmap h u
```
この論文ではF1とF2のcontramapの定義をひろげ, newtypesを削除した.

# Isomorphism of the two definitions
# Applicative laws