haskell - Haskell Arrows 中的 Proc 语法会导致严重的性能损失

Question

使用 proc Arrow 的符号似乎在我的项目中扼杀了性能。这是该问题的一个玩具示例:

我们定义 Coroutine newtype(主要是从 Generalizing Streams into Coroutines 复制)来表示带有 Category 实例的 Mealy 机器(即携带某种状态的函数)。和 Arrow ，写scan包装函数和 evalList列表的 runner 函数。

然后我们有 sumArr和 sumArr'后者是前者在 proc 中调用的函数堵塞。

使用 stack ghc -- --make test.hs -O2 编译在 OS X 上使用 ghc-8.0.2，sumArr 的运行时间为 0.087 秒sumArr' 为 3.263 秒(内存占用很大)。

我想知道这是否真的是由使用 proc 引起的如果我可以在使用 proc 时做一些事情来获得正常的运行时行为符号(没有它编写箭头代码很痛苦)。谢谢你。

{-# LANGUAGE Arrows #-}
{-# LANGUAGE BangPatterns #-}

import Prelude hiding (id, (.))
import Control.Arrow
import Control.Category
import qualified Data.List as L

newtype Coroutine i o = Coroutine { runC :: i -> (o, Coroutine i o) }

instance Category Coroutine where
    id = Coroutine $ \i -> (i, id)

    cof . cog = Coroutine $ \i ->
        let (x, cog') = runC cog i
            (y, cof') = runC cof x
        in (y, cof' . cog')

instance Arrow Coroutine where
    arr f = Coroutine $ \i -> (f i, arr f)

    first co = Coroutine $ \(a,b) ->
        let (c, co') = runC co a in ((c,b), first co')

scan :: (o -> t -> o) -> o -> Coroutine t o
scan f = go where
    go i = Coroutine $ step i where
            step a b = let !a' = f a b in (a', go a')

evalList :: Coroutine a b -> [a] -> [b]
evalList a = L.map fst . L.drop 1 . L.scanl' (\(_, acc) v -> let !x = runC acc v in x) (undefined, a)

sumArr, sumArr' :: Coroutine Int Int
sumArr = scan (\acc x -> let !newAcc = acc + x in newAcc) 0
sumArr' = proc v -> do sumArr -< v

testData :: [Int]
testData = [1..1000000]

main = print $ L.last $ evalList sumArr' testData

Answer 1

是的，这可能是由 proc 引起的符号。脱糖是很低级的，引入了很多(没必要)arr s 而没有利用 &&&或 ***一点也不。

例如，上次我检查过，这个:

mulA f g = proc x -> do
  a <- f -< x
  b <- g -< x
  returnA -< a * b

被脱糖成这样的东西:

mulA f g = arr dup
  >>> first f
  >>> arr swap
  >>> first g
  >>> arr mul
  where
    dup x = (x, x)
    swap (x, y) = (y, x)
    mul = uncurry (*)

当它可能只是这样:

mulA f g = f &&& g >>> arr mul

和这个:

proc x -> do
  a <- f -< x
  b <- g -< a
  returnA -< b

变成这样:

arr id
  >>> f
  >>> arr id
  >>> g
  >>> arr id
  >>> returnA

而不是这个:

f >>> g

此外，我认为没有任何 GHC 重写规则可以利用箭头法则来帮助解决这一问题。