Coyoneda类型的NFData实例

Question

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

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（或类似）作为NFDatatypeclass 提供的（间接）方法。因此，我想NFData为我的函子实现，这些函子现在Coyoneda在其定义中具有-guards。

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

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

Answer 1

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

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“不安全”？它巧妙地破坏了引用透明度。如果有人可以提取wrapped f a，那么他们也许能够执行诸如遍历该值之类的操作，强制隐藏元素。或者，如果f有一个有点伪造的东西fmap改变了它的结构，那么就有可能观察到所谓的纯代码的变化（哎呀）。