避免在Hughes的列表仿函数实例中使用unsafeCoerce

Question

我有一个新类型来表示Hughes的列表(即列表构造):

newtype Hughes a = Hughes {unHughes :: [a] -> [a]}

有一些功能可以解决它:

mkHughes :: [a] -> Hughes a
mkHughes = Hughes . (++)

runHughes :: Hughes a -> [a]
runHughes h = unHughes h []

的Monoid实例是一样容易与上述功能是:

instance Monoid (Hughes a) where
    mempty = Hughes id
    mappend (Hughes f) (Hughes g) = Hughes (f . g)

......但是当我到达Functor和Applicative实例时出现了麻烦.这是我到目前为止所提出的:

instance Functor Hughes where
    fmap f (Hughes h) = Hughes $ unsafeCoerce $ fmap f . h

instance Applicative Hughes where
    pure = Hughes . (:)
    (<*>) (Hughes f) (Hughes v) = Hughes $ unsafeCoerce $
                                  (<*>) <$> f <*> unsafeCoerce v

我遇到的问题是我不喜欢使用unsafeCoerce.有没有办法在Functor不使用它的情况下设计实例,或者它是不可避免的？

此外,我将如何实现Monad此数据类型的实例？

编辑:与DList包中不同,我希望保持性能改进,即不评估[a] -> [a]但映射它.

Answer 1

无法实现Functor Hughes实例.

让我们来看看Hughes:

data Hughes a = Hughes ([a] -> [a])
                         ^

我们可以看到参数a在标记的位置显示逆变.一Functor,当最后一个类型参数的所有出场是协变的实例只能存在.

基本上,您被要求定义一个函数fmap :: (a -> b) -> ([a] -> [a]) -> [b] -> [b].问题是你不能做任何事情[b],没有接受[b]或的功能b.你可以忽略它,但然后算子法则fmap id = id不会成立.

至于DList,Functor实例是有效的,因为实现不导出实际的数据构造函数,只导出智能构造函数.因此,您无法构造作为任意列表处理函数的dlist值.使用提供的智能构造函数,您只能构造同构的dlists [a],这就是函数法所持有的原因.

如果你以某种方式将构造函数破解(带入)作用域,你会发现函子法则实际上并不适用于任意函数,例如,fmap id x /= x如果x类似的话DList (map negate).