在最不固定类型之后的haskell中的bifunctor

Question

我不确定如何在定点之后派生出函数实例:

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这里它的类型不同.

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

Answer 1

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}]}}