performance - Coyoneda类型的NFData实例

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

Coyoneda类型具有构造函数Coyoneda :: (x -> y) -> f x -> Coyoneda f y。这个想法是，通过参数化，更确切地说是通过共同Yooneda引理，类型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为止。

这对时间有很大影响，对空间性能也有很大影响，但我仍然不满意。因此，我想开始使用 deepseq 类型类提供的NFData(或类似的)(间接)。因此，我想为我的仿函数实现NFData，这些仿函数现在在其定义中具有Coyoneda -guards。

问题在于将lambda减少为标准格式不会缩小其关闭时数据的大小。

从数学上讲，将Coyoneda g x简化为Coyoneda id (fmap g x)听起来很合理。我想知道是否存在一些不安全的破解-某种运行时重写规则-来实现这一点。还可以理解其他解决方案。

最佳答案

是的，您可以执行类似的操作，是的，这有点丑陋。

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不安全？它巧妙地破坏了参照透明性。如果有人可以提取包装的f a，那么他们也许可以执行遍历值的操作，从而强制执行所谓的隐藏元素。或者，如果f的伪造fmap改变了其结构，则有可能观察到所谓的纯代码(哎呀)的变化。