代码之家 › 专栏 › 技术社区 › Jogger

森林砍伐在一个纯态中

recursion-schemes ghc haskell

7

Jogger · 技术社区 · 8 年前

维基百科写到 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

在阴谋集团文件中,我指示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上升到16664 KB。这比以前多了200倍。因此,我认为,GHC不会像维基百科中提到的那样进行毁林/融合!

这并不奇怪:变形从左到右创建列表项 (从1到n)并且从右到左的相反方向的退化消耗项目 (从n到1)很难看出hylomorphism是如何工作的不创建整个中间列表。

问题: GHC是否能够实施森林砍伐? 如果对 ,我必须在我的代码或阴谋文件中更改什么? 如果对 ,它到底是如何工作的? 如果不 ,问题在哪里:在维基百科、GHC还是在图书馆?

1 回复 | 直到 8 年前

1

14

Li-yao Xia 8 年前

数据结构实际上是融合在一起的,但生成的程序不是尾部递归的。优化后的代码基本上如下所示(没有 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。