高形态主义中的森林砍伐

Question

维基百科写高胚

在..。函数式程序设计--同胚是一个递归函数，对应于一个非变态(它首先建立一组结果；也称为“展开”)的组合，然后是一个变态(然后将这些结果折叠成一个最终的返回值)。将这两个递归计算融合成一个递归模式，然后避免构建中间数据结构。这是砍伐森林的一个例子，一种程序优化策略。

(我用粗体标记)

使用递归-格式库，我编写了一个非常简单的同胚：

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

在阴谋文件中，我指示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

使用堆栈lts-10.0 (GHC8.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)以相反的方式消耗项目，很难看出不创建整个中间列表，同胚是如何工作的。

问: GHC是否能够完成毁林？如果是，我需要在代码或阴谋文件中更改什么？如果是的话，它到底是如何工作的？如果没有，问题在哪里:维基百科、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)

这样，我看到堆中分配了一个常量51 in。