Hylomorphism中的森林砍伐

Question

维基百科写关于Hylomorphism:

在[...]函数式编程中,一个hylomorphism是一个递归函数,对应于一个变形的组成(首先构建一组结果;也称为'展开'),然后是一个变形(然后将这些结果折叠成一个最终回报值).将这两个递归计算融合成单个递归模式然后避免构建中间数据结构.这是砍伐森林的一个例子,这是一种计划优化策略.

(我的大胆加价)

使用递归方案库我写了一个非常简单的hylomorphism:

import Data.Functor.Foldable
main :: IO ()
main = putStrLn $ show $ hylosum 1000

hylosum :: Int -> Int
hylosum end = hylo alg coalg 1
  where 
    -- Create list of Int's from 1 to n
    coalg :: Int -> ListF Int Int
    coalg n 
       | n > end = Nil
       | otherwise = Cons n (n + 1)
    -- Sum up a list of Int's
    alg :: ListF Int Int -> Int
    alg Nil  =  0
    alg (Cons a x) = a + x

在cabal文件中,我指示GHC优化代码:

name:                Hylo
version:             0.1.0.0
synopsis:            Hylomorphisms and Deforestation        
build-type:          Simple
cabal-version:       >=1.10

executable             Hylo
  main-is:             Main.hs
  ghc-options:         -O2
  build-depends:       base >=4.10 && <4.11 , recursion-schemes      
  default-language:    Haskell2010

使用stackage lts-10.0(GHC 8.2.2)我编译stack build并运行,stack exec Hylo -- +RTS -s我得到:

500500
      84,016 bytes allocated in the heap
       3,408 bytes copied during GC
      44,504 bytes maximum residency (1 sample(s))
      25,128 bytes maximum slop
           2 MB total memory in use (0 MB lost due to fragmentation)

现在我hylosum 1000改为hylosum 1000000 (1000倍以上),我得到:

500000500000
  16,664,864 bytes allocated in the heap
      16,928 bytes copied during GC
  15,756,232 bytes maximum residency (4 sample(s))
      29,224 bytes maximum slop
          18 MB total memory in use (0 MB lost due to fragmentation)

因此堆使用率从84 KB增加到16,664 KB.这比以前多200倍.因此我认为,GHC不会做维基百科中提到的森林砍伐/融合!

这并不是一个惊喜:变形从左到右(从1到n)创建列表项,并且变形从右到左(从n到1)以相反的方式消耗项目,并且很难看出如何将hylomorphism无需创建整个中间列表即可工作.

问题:GHC是否能够进行森林砍伐？如果是,我在代码或cabal文件中需要更改什么？如果是的话,它是如何运作的？如果不是,问题出在哪里:在维基百科,GHC或图书馆？

Answer 1

数据结构实际上是融合的,但结果程序不是尾递归的.优化的代码基本上看起来像这样(没有Cons或Nil看不见):

h n | n > end = 0
    | otherwise = n + h (n+1)

要评估结果,必须先h (n+1)递归计算,然后将结果添加到n.在递归调用期间,值n必须保持存储在某处,因此我们观察到增加的内存使用量end增加.

通过使递归调用处于尾部位置可以获得更紧密的循环,并且携带恒定大小的累加器.我们希望代码优化到此:

-- with BangPatterns
h n !acc | n > end = acc
         | otherwise = h (n+1) (n + acc)

在hylosum,调用(+)发生在alg,并且我们用对将要构建的延续的调用替换它hylo.

alg :: ListF Int (Int -> Int) -> Int -> Int
alg Nil acc = acc
alg (Cons n go) !acc = go (n + acc)

有了这个,我看到在堆中分配了一个不变的51kB.