haskell - アローはアプリカティブ ファンクターとまったく同じですか?

Question

有名な論文Idioms are oblivious, arrows are meticulous, monads are promiscuousによると、arrows の表現力 (追加の型クラスなし) は厳密に applicative functor と monads の間のどこかになければなりませArrowApplyんApplicative:紙は「静的矢印」と呼んでいます。ただし、この「静的」性が意味する制限が何であるかは明確ではありません。

問題の 3 つの型クラスをいじってみると、Applicative Functor と Arrow の間の同等性を構築することができましMonadたArrowApply。この構築は正しいですか？(矢の法則のほとんどは、飽きる前に証明済みです)。ArrowとApplicativeはまったく同じということではないでしょうか。

{-# LANGUAGE TupleSections, NoImplicitPrelude #-}
import Prelude (($), const, uncurry)

-- In the red corner, we have arrows, from the land of * -> * -> *
import Control.Category
import Control.Arrow hiding (Kleisli)

-- In the blue corner, we have applicative functors and monads,
-- the pride of * -> *
import Control.Applicative
import Control.Monad

-- Recall the well-known result that every monad yields an ArrowApply:
newtype Kleisli m a b = Kleisli{ runKleisli :: a -> m b}

instance (Monad m) => Category (Kleisli m) where
    id = Kleisli return
    Kleisli g . Kleisli f = Kleisli $ g <=< f

instance (Monad m) => Arrow (Kleisli m) where
    arr = Kleisli . (return .)
    first (Kleisli f) = Kleisli $ \(x, y) -> liftM (,y) (f x)

instance (Monad m) => ArrowApply (Kleisli m) where
    app = Kleisli $ \(Kleisli f, x) -> f x

-- Every arrow arr can be turned into an applicative functor
-- for any choice of origin o
newtype Arrplicative arr o a = Arrplicative{ runArrplicative :: arr o a }

instance (Arrow arr) => Functor (Arrplicative arr o) where
    fmap f = Arrplicative . (arr f .) . runArrplicative

instance (Arrow arr) => Applicative (Arrplicative arr o) where
    pure = Arrplicative . arr . const

    Arrplicative af <*> Arrplicative ax = Arrplicative $
        arr (uncurry ($)) . (af &&& ax)

-- Arrplicatives over ArrowApply are monads, even
instance (ArrowApply arr) => Monad (Arrplicative arr o) where
    return = pure
    Arrplicative ax >>= f =
        Arrplicative $ (ax >>> arr (runArrplicative . f)) &&& id >>> app

-- Every applicative functor f can be turned into an arrow??
newtype Applicarrow f a b = Applicarrow{ runApplicarrow :: f (a -> b) }

instance (Applicative f) => Category (Applicarrow f) where
    id = Applicarrow $ pure id
    Applicarrow g . Applicarrow f = Applicarrow $ (.) <$> g <*> f

instance (Applicative f) => Arrow (Applicarrow f) where
    arr = Applicarrow . pure
    first (Applicarrow f) = Applicarrow $ first <$> f

Answer 1

すべてのアプリケーションは矢印を生成し、すべての矢印はアプリケーションを生成しますが、それらは同等ではありません。矢印arrと射がある場合、その機能を複製arr a bする射を生成できるということにはなりません。arr o (a \to b)したがって、applicative を往復すると、いくつかの機能が失われます。

Applicative はモノイド関手です。アローは、プロファンクターのカテゴリーのモノイドでもあるプロファンクターです。これら 2 つの概念の間に自然なつながりはありません。私のばかげたことをお許しいただければ: Hask では、矢印の pro-functor の functor 部分が monoidal functor であることがわかりますが、その構造では必然的に "pro" 部分が忘れられます。

矢印からアプリカティブに移行する場合、入力を受け取る矢印の部分を無視し、出力を処理する部分のみを使用しています。多くの興味深い矢印は、何らかの方法で入力部分を使用しているため、それらをアプリケーションに変換することで、有用なものを放棄しています。

とは言うものの、実際には、applicative の方が作業しやすい抽象化であり、ほとんどの場合、私が望むことを実行する抽象化であることがわかります。理論的には矢の方が強力ですが、実際に矢を使っているとは思いません。

Answer 2

IO applicative functor を IO モナドの Kleisli の矢と比較してみましょう。

前の矢印によって読み取られた値を出力する矢印を作成できます。

runKleisli ((Kleisli $ \() -> getLine) >>> Kleisli putStrLn) ()

しかし、アプリカティブ ファンクターではそれができません。アプリカティブ ファンクターでは、ファンクター内関数をファンクター内引数に適用する前に、すべての効果が発生します。function-in-the-functor は、argument-in-the-functor 内の値を使用して、いわばそれ自体の効果を「調整」することはできません。

Answer 3

（私は以下を私のブログに掲載し、紹介を拡張しました）

Tom Ellis は、ファイル I/O を含む具体的な例について考えることを提案したので、3 つの型クラスを使用して 3 つのアプローチを比較してみましょう。簡単にするために、ファイルからの文字列の読み取りと、ファイルへの文字列の書き込みという 2 つの操作だけに注目します。ファイルは、ファイル パスによって識別されます。

type FilePath = String

モナディック I/O

最初の I/O インターフェイスは次のように定義されます。

data IOM ∷ ⋆ → ⋆
instance Monad IOM
readFile ∷ FilePath → IOM String
writeFile ∷ FilePath → String → IOM ()

このインターフェイスを使用すると、たとえば、あるパスから別のパスにファイルをコピーできます。

copy ∷ FilePath → FilePath → IOM ()
copy from to = readFile from >>= writeFile to

ただし、それ以上のことができます。操作するファイルの選択は、上流のエフェクトに依存する可能性があります。たとえば、次の関数は、ファイル名を含むインデックス ファイルを取得し、指定されたターゲット ディレクトリにコピーします。

copyIndirect ∷ FilePath → FilePath → IOM ()
copyIndirect index target = do
    from ← readFile index
    copy from (target ⟨/⟩ to)

反対に、これは、特定の値によって操作される一連のファイル名を事前に知る方法がないことを意味しますaction ∷ IOM α。「事前に」とは、純粋な関数を書く能力を意味しますfileNames :: IOM α → [FilePath]。

もちろん、非 IO ベースのモナド (ある種の抽出関数があるものなどμ α → α) の場合、この区別はもう少しあいまいになりますが、それでも、その効果を評価せずに情報を抽出しようとすることを考えるのは理にかなっています。モナド (例えば、「型の値を手元Reader Γ αに持たずに aについて何がわかるか?」と尋ねることができます)。Γ

モナドに対してこの意味での静的解析を実際に行うことができない理由は、バインドの右側の関数が Haskell 関数の空間にあり、完全に不透明だからです。

それでは、インターフェイスをアプリケーション ファンクタだけに制限してみましょう。

アプリケーション I/O

data IOF ∷ ⋆ → ⋆
instance Applicative IOF
readFile ∷ FilePath → IOF String
writeFile ∷ FilePath → String → IOF ()

IOFはモナドではないため、 and を構成する方法はありません。readFileしたがってwriteFile、このインターフェースでできることは、ファイルから読み取り、その内容を純粋に後処理するか、ファイルに書き込むことだけです。しかし、ファイルの内容を別のファイルに書き込む方法はありません。

の型を変えてみてはどうwriteFileですか？

writeFile′ ∷ FilePath → IOF (String → ())

このインターフェースの主な問題は、次のようなものを書くことができる一方で、

copy ∷ FilePath → FilePath → IOF ()
copy from to = writeFile′ to ⟨*⟩ readFile from

String → ()参照の透過性を壊すため、文字列をファイルに書き込むという恐ろしいモデルであるため、あらゆる種類の厄介な問題につながります。たとえば、out.txtこのプログラムを実行した後の の内容は何だと思いますか?

(λ write → [write "foo", write "bar", write "foo"]) ⟨$⟩ writeFile′ "out.txt"

矢印化された I/O への 2 つのアプローチ

まず最初に、テーブルに新しいものを何ももたらさない (実際、もたらさない) 2 つの矢印ベースの I/O インターフェイスを整理しましょう:Kleisli IOMとApplicarrow IOF.

IOMモジュロカリー化の Kleisli-arrowは次のとおりです。

readFile ∷ Kleisli IOM FilePath String
writeFile ∷ Kleisli IOM (FilePath, String) ()

writeFileの入力にはまだファイル名とコンテンツの両方が含まれているため、(簡単にするために矢印表記を使用して) 書き込むことができますcopyIndirect。ArrowApplyのインスタンスがKleisli IOM使用されていないことに注意してください。

copyIndirect ∷ Kleisli IOM (FilePath, FilePath) ()
copyIndirect = proc (index, target) → do
    from ← readFile ↢ index
    s ← readFile ↢ from
    writeFile ↢ (to, s)

Applicarrowは次のようにIOFなります。

readFile ∷ FilePath → Applicarrow IOF () String
writeFile ∷ FilePath → String → Applicarrow IOF () ()

もちろん、これはまだ構成できないという同じ問題を示していreadFileますwriteFile.

適切な矢印化された I/O インターフェイス

Haskell関数IOMをIOF使用する場所と矢印を作成する場所に関して、ゼロから始めて、その中間の何かを作成しようとするとどうなるでしょうか? 次のインターフェイスを使用します。

data IOA ∷ ⋆ → ⋆ → ⋆
instance Arrow IOA
readFile ∷ FilePath → IOA () String
writeFile ∷ FilePath → IOA String ()

writeFile矢印の入力側からコンテンツを取得するため、引き続き実装できcopyます。

copy ∷ FilePath → FilePath → IOA () ()
copy from to = readFile from >>> writeFile to

ただし、のもう一方の引数writeFileは純粋に機能的なものであるため、eg の出力に依存することはできませんreadFile。したがって、このArrow インターフェイスcopyIndirectでは実装できません。

この議論をひっくり返すと、(完全なIOAパイプライン自体を実行する前に) ファイルに最終的に何が書き込まれるかを事前に知ることはできませんが、変更されるファイル名のセットを静的に決定できることも意味します。 .

結論

モナドは静的解析に対して不透明であり、アプリカティブ ファンクターは動的時間データの依存関係を表現するのが苦手です。矢印は 2 つの間のスイート スポットを提供できることがわかりました。純粋に機能的な入力と矢印化された入力を慎重に選択することで、動的な動作と静的解析への適応性を適切に相互作用させるインターフェイスを作成できます。