16

私は自由なアイデアで遊んでいて、これを見つけました：

{-# LANGUAGE RankNTypes #-}

data Monoid m = Monoid { mempty :: m, mappend :: m -> m -> m }
data Generator a m = Generator { monoid :: Monoid m, singleton :: a -> m }

newtype Free f = Free { getFree :: forall s. f s -> s }

mkMonoid :: (forall s. f s -> Monoid s) -> Monoid (Free f)
mkMonoid f = Monoid {
    mempty = Free (mempty . f),
    mappend = \a b -> Free $ \s -> mappend (f s) (getFree a s) (getFree b s)
}

freeMonoid :: Monoid (Free Monoid)
freeMonoid = mkMonoid id

mkGenerator :: (forall s. f s -> Generator a s) -> Generator a (Free f)
mkGenerator f = Generator {
    monoid = mkMonoid (monoid . f),
    singleton = \x -> Free $ \s -> singleton (f s) x
}

freeGenerator :: Generator a (Free (Generator a))
freeGenerator = mkGenerator id

関数を書くことができる条件を見つけたい：

mkFree :: (??? f) => f (Free f)

しかし、この関数を書くことを可能にする意味のある構造を見つけることができませんでした（ のメソッドでfある簡単なものを除く）。特に私の美的センスは、この構造がタイプに言及していないことを好みます。mkFree???Free

誰かが前にこのようなものを見たことがありますか? この一般化は可能ですか？私がまだ考えていない方向への既知の一般化はありますか?

4

1 に答える 1

8

ユニバーサル代数へのリンクは良い出発点であり、それを少し読んだ後、すべてがうまくいきました。探しているのは F 代数です。

type Alg f x = f x -> x

任意の (エンド) ファンクター用f。たとえば、モノイド代数の場合、関手は次のようになります。

data MonoidF m = MEmpty | MAppend m m deriving Functor

どのような場合でもMonoid、明らかなモノイド代数があります。

monoidAlg :: Monoid m => Alg MonoidF m
monoidAlg MEmpty = mempty
monoidAlg (MAppend a b) = mappend a b

free-functors パッケージから free functor 定義を取得し、クラス制約を f 代数に置き換えることができます。

newtype Free f a = Free { runFree :: forall b. Alg f b -> (a -> b) -> b }

a任意の集合を代数に変換するには、ある意味で自由関手が最良の方法です。こうやって：

unit :: a -> Free f a
unit a = Free $ \_ k -> k a

a代数に変換する他の方法についてbは、自由代数から への関数を与えることができるため、これが最良の方法bです。

rightAdjunct :: Functor f => Alg f b -> (a -> b) -> Free f a -> b
rightAdjunct alg k (Free f) = f alg k

残っているのは、自由関手が f 代数を作成することを実際に示すことです (これがあなたが求めていたものです)。

freeAlg :: Functor f => Alg f (Free f a)
freeAlg ff = Free $ \alg k -> alg (fmap (rightAdjunct alg k) ff)

少し説明すると、ffは型f (Free f a)であり、Free f a. b、与えられたalg :: f b -> b、およびを構築できれば、それを行うことができますk :: a -> b。したがって、に含まれるすべてを a にマップできる場合に適用できますalgが、それはまさにand で行うことです。ffFree f abrightAdjunctalgk

お察しのとおり、これFree fはファンクター上のフリー モナドですf(正確には、教会でエンコードされたバージョンです)。

instance Functor f => Monad (Free f) where
  return = unit
  m >>= f = rightAdjunct freeAlg f m
于 2013-02-26T10:22:28.780 に答える