5

我不确定如何在定点后推导出函子实例：

data FreeF f a next  = PureF a | FreeF (f next)  deriving (Functor)

data Mu f  = In { out :: f ( Mu f ) }

newtype Free f a = Free(  Mu (FreeF f a)  )

instance Functor f => Functor (Free f) where
     fmap h (Free (out -> PureF a))  = Free (In (PureF (h a)))
     fmap h (Free (out -> FreeF fn)) = Free (In (fmap undefined undefined)) --stuck

如果我修改 Mu 以接受额外的类型参数，我可以继续直到...：

data Mu f a  = In { out :: f ( Mu f a )  } deriving (Functor)

newtype Free f a = Free(  Mu (FreeF f a) a )

instance Functor f => Functor (Free f ) where
     fmap h (Free (out -> PureF a))  = Free . In . PureF $ h a
     fmap h (Free (out -> FreeF fn)) = Free . In . FreeF $ fmap undefined fn

在这里我需要undefined :: Mu (FreeF f a) a -> Mu (FreeF f b) b但mu f它是相同的函子，在f这里它的类型不同。

解决这个问题的正确方法是什么？

4

2 回答 2

4

mu f是相同的函子，在f这里它的类型有所不同。

幸运的是，我们正在定义Functor (Free f)，并且我们实际上使用此Functor实例来映射构造函数a中的 ' PureF。Functor (Free f)对所有“内部”出现的a.

因此，每当我们想要映射 的两个出现时a，例如当我们想要实现 时FreeF f a (Mu (FreeF f a)) -> FreeF f b (Mu (FreeF f b))，我们可以通过将所有内容一直包装回Free、 映射，然后再次展开来做到这一点。

以下检查与您的原始数据定义：

newtype Free f a = Free {unFree :: Mu (FreeF f a)} -- add "unFree"

instance Functor f => Functor (Free f) where
     fmap h (Free (In (PureF a)))  = Free (In (PureF (h a)))
     fmap h (Free (In (FreeF fn))) =
       Free (In (FreeF (fmap (unFree . fmap h . Free) fn)))

一些测试：

{-# LANGUAGE UndecidableInstances, StandaloneDeriving #-}

deriving instance Show (f (Mu f)) => Show (Mu f)
deriving instance Show (Mu (FreeF f a)) => Show (Free f a)       

foo :: Free [] Int
foo = Free $ In $ FreeF [ In $ PureF 100, In $ PureF 200 ]

> fmap (+100) foo
Free {unFree = In {out = FreeF [In {out = PureF 200},In {out = PureF 300}]}}
于 2016-01-14T23:43:54.953 回答
3

我以前没有做过这个建筑，但我想我看到了一些东西。您对添加参数的直觉Mu很好，但是您需要将其传递以使其Free f适合，即f采用两个参数而不是一个参数：

newtype Mu f a = In { out :: f (Mu f a) a }

Mu f应该是Functor在合适的条件下，这会给你你正在寻找的实例。那些条件是什么？我们需要：

fmap' :: (a -> b) -> f (Mu f a) a -> f (Mu f b) b

我们希望f它的第二个参数是函数式的，所以这没问题。所以我们真正需要一种方法来获得

f (Mu f a) b -> f (Mu f b) b
           ^               ^
           +--not varying--+

我们可以递归地使用实例来获取Mu f a -> Mu f b，所以看起来我们也只需要f在它的第一个参数中成为一个仿函数。因此：

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d

然后你应该能够编写合适的实例

instance (Functor f) => Bifunctor (FreeF f) ...
instance (Bifunctor f) => Functor (Mu f) ...
于 2016-01-14T23:21:04.717 回答