Hylomorphism中的森林砍伐

Question

维基百科写关于Hylomorphism：

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

（我的大胆加价）

使用recursion-schemes库我写了一个非常简单的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。