34

無料のモナドが便利であることはわかっています。Operationalのようなパッケージを使用すると、モナド構造自体ではなく、アプリケーション固有の効果だけを気にすることで、新しいモナドを簡単に定義できます。

フリーモナドの定義方法に類似した「フリーアロー」を簡単に定義できます。

{-# LANGUAGE GADTs #-}
module FreeA
       ( FreeA, effect
       ) where

import Prelude hiding ((.), id)
import Control.Category
import Control.Arrow
import Control.Applicative
import Data.Monoid

data FreeA eff a b where
    Pure :: (a -> b) -> FreeA eff a b
    Effect :: eff a b -> FreeA eff a b
    Seq :: FreeA eff a b -> FreeA eff b c -> FreeA eff a c
    Par :: FreeA eff a₁ b₁ -> FreeA eff a₂ b₂ -> FreeA eff (a₁, a₂) (b₁, b₂)

effect :: eff a b -> FreeA eff a b
effect = Effect

instance Category (FreeA eff) where
    id = Pure id
    (.) = flip Seq

instance Arrow (FreeA eff) where
    arr = Pure
    first f = Par f id
    second f = Par id f
    (***) = Par

私の質問は、フリーアローで最も有用な一般的な操作は何でしょうか？私の特定のアプリケーションでは、次の2つの特別なケースが必要でした。

{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ScopedTypeVariables #-}
analyze :: forall f eff a₀ b₀ r. (Applicative f, Monoid r)
        => (forall a b. eff a b -> f r)
        -> FreeA eff a₀ b₀ -> f r
analyze visit = go
  where
    go :: forall a b. FreeA eff a b -> f r
    go arr = case arr of
        Pure _ -> pure mempty
        Seq f₁ f₂ -> mappend <$> go f₁ <*> go f₂
        Par f₁ f₂ -> mappend <$> go f₁ <*> go f₂
        Effect eff -> visit eff

evalA :: forall eff arr a₀ b₀. (Arrow arr) => (forall a b. eff a b -> arr a b) -> FreeA eff a₀ b₀ -> arr a₀ b₀
evalA exec = go
  where
    go :: forall a b. FreeA eff a b -> arr a b
    go freeA = case freeA of
        Pure f -> arr f
        Seq f₁ f₂ -> go f₂ . go f₁
        Par f₁ f₂ -> go f₁ *** go f₂
        Effect eff -> exec eff

しかし、なぜこれら（そして他のものではない）が有用なものになるのかについての理論的な議論はありません。

4

1 に答える 1

29

自由関手は忘却関手と随伴したままです。付属物については、同形性が必要です (xとで自然y):

(Free y :~> x) <-> (y :~> Forget x)

これはどのカテゴリーにあるべきですか？忘却ファンクターはArrowインスタンスを忘れるため、インスタンスArrowのカテゴリからすべてのバイファンクターのカテゴリに移動します。フリー ファンクターはその逆で、任意のバイファンクターをフリーArrowインスタンスに変換します。

バイファンクターのカテゴリに含まれる Haskell タイプの矢印は次のとおりです。

type x :~> y = forall a b. x a b -> y a b

Arrowインスタンスのカテゴリの矢印も同じですが、Arrow制約が追加されています。忘却ファンクターは制約を忘れるだけなので、Haskell で表現する必要はありません。これにより、上記の同型が 2 つの関数に変換されます。

leftAdjunct :: (FreeA x :~> y) -> x :~> y
rightAdjunct :: Arrow y => (x :~> y) -> FreeA x :~> y

leftAdjunctにも制約があるはずArrow yですが、実装ではまったく必要ないことがわかりました。より便利な という点で、実際には非常に単純な実装がありますunit。

unit :: x :~> FreeA x

leftAdjunct f = f . unit

unitはあなたのものeffectでrightAdjunctあり、あなたのものevalAです。したがって、付属品に必要な機能が正確に備わっています。それを示す必要がleftAdjunctありrightAdjunct、同形です。rightAdjunct unit = idそれを行う最も簡単な方法は、あなたの場合は簡単であることを証明することですevalA effect = id。

どうanalyzeですか？これevalAは定数アローに特化されており、結果のMonoid制約は適用可能なモノイドに特化されています。いえ

analyze visit = getApp . getConstArr . evalA (ConstArr . Ap . visit)

と

newtype ConstArr m a b = ConstArr { getConstArr :: m }

およびreducers パッケージApから。(編集: GHC 8.6 以降では、ベースにもあります)Data.Monoid

編集: FreeA は高次のファンクターであることをほとんど忘れていました! Edit2:これは、考え直して、rightAdjunctandで実装することもできますunit。

hfmap :: (x :~> y) -> FreeA x :~> FreeA y
hfmap f = evalA (effect . f)

ところで、フリー ファンクターを定義する別の方法があり、最近Hackage にパッケージを置きました。kind はサポートしていません* -> * -> *(編集: 現在はサポートしています!) が、コードは自由矢印に適応させることができます:

newtype FreeA eff a b = FreeA { runFreeA :: forall arr. Arrow arr => (eff :~> arr) -> arr a b }
evalA f a = runFreeA a f
effect a = FreeA $ \k -> k a

instance Category (FreeA f) where
  id = FreeA $ const id
  FreeA f . FreeA g = FreeA $ \k -> f k . g k

instance Arrow (FreeA f) where
  arr f = FreeA $ const (arr f)
  first (FreeA f) = FreeA $ \k -> first (f k)
  second (FreeA f) = FreeA $ \k -> second (f k)
  FreeA f *** FreeA g = FreeA $ \k -> f k *** g k
  FreeA f &&& FreeA g = FreeA $ \k -> f k &&& g k

提供するイントロスペクションが必要ない場合はFreeA、おそらくこちらのFreeA方が高速です。

于 2012-08-24T22:26:35.393 に答える