为什么这些fixpoint cata/ana morphism定义优于递归定义？

Question

考虑前一个问题的这些定义:

type Algebra f a = f a -> a

cata :: Functor f => Algebra f b -> Fix f -> b
cata alg = alg . fmap (cata alg) . unFix

fixcata :: Functor f => Algebra f b -> Fix f -> b
fixcata alg = fix $ \f -> alg . fmap f . unFix

type CoAlgebra f a = a -> f a

ana :: Functor f => CoAlgebra f a -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg

fixana :: Functor f => CoAlgebra f a -> a -> Fix f
fixana coalg = fix $ \f -> Fix . fmap f . coalg

我运行了一些基准测试,结果令我感到惊讶.criterion报告类似十倍加速,特别O2是启用时.我想知道是什么导致了这么大的改进,并开始严重怀疑我的基准测试能力.

这是criterion我使用的确切代码:

smallWord, largeWord :: Word
smallWord = 2^10
largeWord = 2^20

shortEnv, longEnv :: Fix Maybe
shortEnv = ana coAlg smallWord
longEnv = ana coAlg largeWord

benchCata = nf (cata alg)
benchFixcata = nf (fixcata alg)

benchAna = nf (ana coAlg)
benchFixana = nf (fixana coAlg)

main = defaultMain
    [ bgroup "cata"
        [ bgroup "short input"
            [ env (return shortEnv) $ \x -> bench "cata"    (benchCata x)
            , env (return shortEnv) $ \x -> bench "fixcata" (benchFixcata x)
            ]
        , bgroup "long input"
            [ env (return longEnv) $ \x -> bench "cata"    (benchCata x)
            , env (return longEnv) $ \x -> bench "fixcata" (benchFixcata x)
            ]
        ]
    , bgroup "ana"
        [ bgroup "small word"
            [ bench "ana" $ benchAna smallWord
            , bench "fixana" $ benchFixana smallWord
            ]
        , bgroup "large word"
            [ bench "ana" $ benchAna largeWord
            , bench "fixana" $ benchFixana largeWord
            ]
        ]
    ]

还有一些辅助代码:

alg :: Algebra Maybe Word
alg Nothing = 0
alg (Just x) = succ x

coAlg :: CoAlgebra Maybe Word
coAlg 0 = Nothing
coAlg x = Just (pred x)

编译O0,数字非常均匀.随着O2,fix~功能似乎优于普通的:

benchmarking cata/short input/cata
time                 31.67 ?s   (31.10 ?s .. 32.26 ?s)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 31.20 ?s   (31.05 ?s .. 31.46 ?s)
std dev              633.9 ns   (385.3 ns .. 1.029 ?s)
variance introduced by outliers: 18% (moderately inflated)

benchmarking cata/short input/fixcata
time                 2.422 ?s   (2.407 ?s .. 2.440 ?s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.399 ?s   (2.388 ?s .. 2.410 ?s)
std dev              37.12 ns   (31.44 ns .. 47.06 ns)
variance introduced by outliers: 14% (moderately inflated)

如果有人可以确认或发现缺陷,我将不胜感激.

*我ghc 8.2.2在这个场合编译了东西.)

---

postscriptum

这篇帖子从2012年开始详细阐述fix了相关细节的表现.(感谢@chi链接.)

Answer 1

这是由于如何计算固定点fix.上面的@duplode指出了这一点(我自己在一个相关的问题中).无论如何,我们可以总结如下问题.

我们有

fix f = f (fix f)

有效,但fix f每次递归都会调用一个新的调用.代替,

fix f = go
   where go = f go

计算避免该调用的相同固定点.在库fix中以这种更有效的方式实现.

回到问题,考虑以下三种实现cata:

cata :: Functor f => Algebra f b -> Fix f -> b
cata alg' = alg' . fmap (cata alg') . unFix

cata2 :: Functor f => Algebra f b -> Fix f -> b
cata2 alg' = go
   where
   go = alg' . fmap go . unFix

fixcata :: Functor f => Algebra f b -> Fix f -> b
fixcata alg' = fix $ \f -> alg' . fmap f . unFix

第一个cata alg'在每次递归时都会调用.第二个没有.第三个也没有,因为图书馆fix是有效的.

事实上,即使使用OP使用的相同测试,我们也可以使用Criterion来确认这一点:

benchmarking cata/short input/cata
time                 16.58 us   (16.54 us .. 16.62 us)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.62 us   (16.58 us .. 16.65 us)
std dev              111.6 ns   (89.76 ns .. 144.0 ns)

benchmarking cata/short input/cata2
time                 1.746 us   (1.742 us .. 1.749 us)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.741 us   (1.736 us .. 1.744 us)
std dev              12.69 ns   (10.50 ns .. 17.31 ns)

benchmarking cata/short input/fixcata
time                 2.010 us   (2.003 us .. 2.016 us)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.006 us   (2.001 us .. 2.011 us)
std dev              16.40 ns   (14.05 ns .. 19.27 ns)

长期投入也表明了改善.

benchmarking cata/long input/cata
time                 119.3 ms   (113.4 ms .. 125.8 ms)
                     0.996 R²   (0.992 R² .. 1.000 R²)
mean                 119.8 ms   (117.7 ms .. 121.7 ms)
std dev              2.924 ms   (2.073 ms .. 4.064 ms)
variance introduced by outliers: 11% (moderately inflated)

benchmarking cata/long input/cata2
time                 17.89 ms   (17.43 ms .. 18.36 ms)
                     0.996 R²   (0.992 R² .. 0.999 R²)
mean                 18.02 ms   (17.49 ms .. 18.62 ms)
std dev              1.362 ms   (853.9 us .. 2.022 ms)
variance introduced by outliers: 33% (moderately inflated)

benchmarking cata/long input/fixcata
time                 18.03 ms   (17.56 ms .. 18.50 ms)
                     0.996 R²   (0.992 R² .. 0.999 R²)
mean                 18.17 ms   (17.57 ms .. 18.72 ms)
std dev              1.365 ms   (852.1 us .. 2.045 ms)
variance introduced by outliers: 33% (moderately inflated)

我也进行了实验ana,观察到类似改进的表现ana2同意fixana.那里也没有惊喜.