避免在 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 值。使用提供的智能构造函数，您只能构造与 [a] 同构的 dlist，这就是函子定律成立的原因。

如果您以某种方式破解（引入）构造函数到作用域中，您会发现仿函数法则实际上并不适用于任意函数，例如 fmap id x /= x if x类似于 DList (map negate).

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

Avoiding use of unsafeCoerce in Hughes' list functor instance

haskell

typeclass

functor

coercion

difference-lists