performance - Coyoneda 类型的 NFData 实例

Question

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

Coyoneda 类型有构造函数 Coyoneda :: (x -> y) -> f x -> Coyoneda f y .这个想法是，通过参数化，更准确地说，通过共同米田引理，类型 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 -守卫在他们的定义中。

问题在于，将 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 “不安全”？它巧妙地破坏了引用透明度。如果有人可以提取包裹的f a ，那么他们也许可以做一些事情，比如遍历值，强制隐藏的元素。或者如果 f有点假fmap这改变了它的结构，那么就可以观察到所谓的纯代码的变化(哎哟)。