haskell 中的双函子在最不固定的类型之后

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 添加参数的直觉是好的，但您需要传递它以便 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) ...

Answer 2

mu f is a functor for the same f and here it varies in type.

幸运的是，我们正在定义 Functor (Free f)，并且我们实际上使用此 Functor 实例来映射 PureF 构造函数中的 a。 Functor (Free f) 抽象了所有 "internal" 次出现的 a。

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

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

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

haskell 中的双函子在最不固定的类型之后

bifunctor in haskell after the least fixed type

haskell

functor

recursive-datastructures

free-monad