这些类Free结构有没有一个泛化？
我在玩弄类似于自由的想法，发现了这个：
{-# 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类型。
以前有没有人见过这样的东西？这种泛化是可能的吗？在我还没有想到的方向上，有没有一个已知的概括？
回答 1
Stack Overflow用户
发布于 2013-02-26 18:22:29
到通用代数的链接是一个很好的起点，在阅读了一下之后，一切都变得井然有序。我们要找的是一个F-代数：
type Alg f x = f x -> x对于任何(Endo)函数式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剩下的就是实际展示free functor创建了一个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。如果我们能在给定alg :: f b -> b和k :: a -> b的情况下构建一个b，我们就可以做到这一点。因此，如果我们可以将它包含的每个Free f a映射到一个b，我们就可以将alg应用于ff，但这正是rightAdjunct对alg和k所做的事情。
正如您可能已经猜到的，此Free f是函数器f (准确地说是church encoded version )上的免费monad。
instance Functor f => Monad (Free f) where
return = unit
m >>= f = rightAdjunct freeAlg f mhttps://stackoverflow.com/questions/14852712
复制相似问题