我在玩弄类似于自由的想法,发现了这个:
{-# 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
类型。
以前有没有人见过这样的东西?这种泛化是可能的吗?在我还没有想到的方向上,有没有一个已知的概括?
发布于 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 m
https://stackoverflow.com/questions/14852712
复制相似问题