haskell - 組織型を使用してカタロニア語を実装する場合の大きなオーバーヘッド

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の重要なブランチで割り当てを行うのに大部分の時間を費やしていると思います。最適化の余地がどれだけあるかはわかりません.catalanHistotoListreverse