Coyoneda 类型的 NFData 实例

Question

我有一个 Haskell 项目，在数据结构上非常大量使用 fmap。为了避免一次又一次遍历相同的数据结构，同时保留自由使用fmap的可能性，我决定使用Coyoneda类型来保护一些更大的结构。

Coyoneda 类型具有构造函数 Coyoneda :: (x -> y) -> f x -> Coyoneda f y。这个想法是，通过参数化，更准确地说，通过 co-Yoneda 引理，类型 f a 和 Coyoneda f a 是同构的，但是 Coyoneda 类型的优点是它推迟了实际结构遍历.

例如，在下面的代码中，第一个表达式遍历底层结构3次，而第二个只遍历一次：

fmap k $ fmap h $ fmap g $ (x :: f a)
lowerCoyoneda $ fmap k $ fmap h $ fmap g $ liftCoyoneda $ (x :: f a)

的确，第二行缩减如下：

lowerCoyoneda $ fmap k $ fmap h $ fmap g $ liftCoyoneda $ x
lowerCoyoneda $ fmap k $ fmap h $ fmap g $ Coyoneda id x
lowerCoyoneda $ fmap k $ fmap h $ Coyoneda g x
lowerCoyoneda $ fmap k $ Coyoneda (h . g) x
lowerCoyoneda $ Coyoneda (k . h . g) x
fmap (k . h . g) x

因此它有效地推迟了实际的结构遍历，直到您应用 lowerCoyoneda。

这对时间和space性能影响很大，但我仍然不满意。出于这个原因，我想开始使用 NFData 类型类（间接）提供的 deepseq （或类似的）。所以我想为我的仿函数实现 NFData，现在它们的定义中有 Coyoneda-guards。

问题在于将 lambda 简化为标准形式并不会缩小闭包中数据的大小。

从数学上讲，将 Coyoneda g x 简单地减少到 Coyoneda id (fmap g x) 是合理的。我想知道是否有一些不安全的 hack - 某种运行时重写规则 - 来实现这一点。其他解决方案也很受欢迎。

Answer 1

The trouble is that reducing lambdas to normal form doesn't reduce the thunk in their body

函数不包含 "thunks"。它们包含指向不可变代码的指针，可能还包含捕获变量值的闭包。 Thunk 可能会评估函数，但函数本身始终被视为已完全评估。

此外，由于函数包含指向不可变机器代码的指针，因此无法在运行时以任何方式更新或修改函数体。 rnf 有点用词不当，因为 GHC 无法在函数绑定器下求值，因此无法还原为 lambda 演算理论中通常意义上的范式。

rnf 在函数上的作用与 seq 完全相同，而 seq 本身只会在你有一个缩减为函数的 thunk 时做任何值得注意的事情。这在 Haskell 代码中并不常见；一个这样的例子是从包含函数的结构中进行惰性查找。

rnf 应该谨慎使用，因为它完全遍历数据结构。人们通常使用 rnf 的原因是为了消除 space 泄漏，而不是（直接）让事情变得更快。

总而言之，您可以尝试在 Coyoneda 的函数部分使用 seq，并且可能不应该使用 rnf，但我怀疑 seq 是否有帮助以可衡量的方式。

Answer 2

是的，你可以做类似的事情，是的，它有点丑。

module Data.Functor.Coyoneda.NF where

import qualified Data.Functor.Coyoneda as S
import Data.IORef
import Control.DeepSeq
import System.IO.Unsafe
import Control.Exception

newtype Coyoneda f a =
  UnsafeCoyonedaFromRef {unsafeCoyonedaToRef :: IORef (S.Coyoneda f a)}

newCoyonedaIO :: S.Coyoneda f a -> IO (Coyoneda f a)
newCoyonedaIO c = UnsafeCoyonedaFromRef <$> newIORef c

newCoyoneda :: S.Coyoneda f a -> Coyoneda f a
newCoyoneda = unsafePerformIO . newCoyonedaIO

unsafeReadCoyonedaIO :: Coyoneda f a -> IO (S.Coyoneda f a)
unsafeReadCoyonedaIO (UnsafeCoyonedaFromRef ref) = readIORef ref

unsafeReadCoyoneda :: Coyoneda f a -> S.Coyoneda f a
unsafeReadCoyoneda = unsafePerformIO . unsafeReadCoyonedaIO

{-| `fmap` happens under the reference, but does NOT traverse `f`. -}
instance Functor (Coyoneda f) where
  fmap f c = unsafePerformIO $ do
    q <- unsafeReadCoyonedaIO c
    newCoyonedaIO $ fmap f q

instance (Functor f, NFData (f a)) => NFData (Coyoneda f a) where
  rnf (UnsafeCoyonedaFromRef ref) = unsafePerformIO $ do
    co <- readIORef ref
    let fx = S.lowerCoyoneda co
    -- We use evaluate because we want to be really sure the reduction to NF
    -- succeeds and we don't install bottom in the IORef.
    evaluate (rnf fx)
    writeIORef ref (S.liftCoyoneda fx)

liftCoyoneda :: f a -> Coyoneda f a
liftCoyoneda = newCoyoneda . S.liftCoyoneda

lowerCoyoneda :: Functor f => Coyoneda f a -> f a
lowerCoyoneda = S.lowerCoyoneda . unsafeReadCoyoneda

是什么让 unsafeReadCoyoneda "unsafe"？它巧妙地打破了引用透明性。如果有人可以提取包装的 f a，那么他们可能会做一些事情，比如遍历值，强制隐藏元素。或者，如果 f 有一些伪造的 fmap 改变了它的结构，那么就有可能从所谓的纯代码中观察到变化（哎哟）。

Coyoneda 类型的 NFData 实例

NFData instance for the Coyoneda type

performance

haskell

unsafe

parametric-polymorphism