使用组织同态实现加泰罗尼亚数字的巨大开销

Question

我最近正在探索递归方案，想要找到一些组织同态的用例 - 我认为加泰罗尼亚数字可能是一个有趣的例子（我知道有更好的方法来实现加泰罗尼亚数字，这不是本文的重点问题）。我的想法如下：

import Control.Comonad.Cofree
import Control.Monad
import Data.Foldable
import Data.Function.Memoize (memoFix)
import Data.Functor.Foldable
import GHC.Natural

type Nat = Natural

-- unrelated lines omitted

catalanHisto :: Nat -> Nat
catalanHisto = histo \case
  Nothing ->
    1
  Just fs ->
    let xs = toList fs -- this is line 101 in my original code.
        ys = reverse xs
     in sum $ zipWith (*) xs ys

catalanMemo :: Integer -> Integer
catalanMemo = memoFix \q n ->
  if n == 0
    then 1
    else
      let xs = fmap q [0 .. n -1]
          ys = reverse xs
       in sum $ zipWith (*) xs ys

main :: IO ()
main = do
  -- print $ catalanMemo 1000
  print $ catalanHisto 1000

然而，性能会受到影响catalanHisto：

real    49.36s
user    416.48s
sys     99.38s

与以下相比，这是相当糟糕的catalanMemo：

real    0.84s
user    5.09s
sys     2.08s

考虑到至少它终止了，该histo版本肯定会记住一些东西，但是有一个巨大的开销，我不确定我是否误用了histo，或者这只是以这种方式编写程序所付出的代价。当我继续进行一些基本分析时：

    Sat Feb 19 22:58 2022 Time and Allocation Profiling Report  (Final)

       demo +RTS -N -s -p -RTS

    total time  =       20.78 secs   (52462 ticks @ 1000 us, 24 processors)
    total alloc = 122,870,767,920 bytes  (excludes profiling overheads)

COST CENTRE       MODULE                 SRC                                     %time %alloc

catalanHisto.\    Catalan                src/Catalan.hs:(101,5)-(103,31)          68.0   71.5
foldMap.go        Control.Comonad.Cofree src/Control/Comonad/Cofree.hs:301:5-46   28.4   25.0
catalanHisto      Catalan                src/Catalan.hs:(97,1)-(103,31)            1.7    0.0
catalanHisto.\.ys Catalan                src/Catalan.hs:102:9-23                   1.3    3.3

不是解释这些结果的专家，我猜除了 中的一些分配之外Control.Comonad.Cofree，它还花费了大部分时间在 的非平凡分支中进行分配catalanHisto，可能是由于toList和reverse，我不确定有多少优化空间。