haskell - 使用无限列表管理内存使用

Question

所以我想方设法用数字 15 制作数字 5

import Data.List
import Control.Monad
import Control.Monad.Omega
import System.IO

data Expr = X | Sub Expr Expr | Div Expr Expr | Pow Expr Expr
          deriving Show

eval x X = x
eval x (Sub a b) = eval x a -  eval x b
eval x (Div a b) = eval x a /  eval x b
eval x (Pow a b) = eval x a ** eval x b

exprs | v <- each exprs
      = (X:) . concat $ transpose
      [ runOmega $ liftM2 Div v v
      , runOmega $ liftM2 Sub v v
      , runOmega $ liftM2 Pow v v
      ]

main = do
  hSetBuffering stdout LineBuffering
  mapM_ print $ filter ((==5).eval 15) exprs

但是，第一个结果是列表中的第 118588079 个元素，Haskell 在到达那里之前很久就耗尽了内存。我怎么知道第一个是118588079？因为如果我只是计算它并请求索引，Haskell 根本不使用内存:

run x | v <- each $ run x
      = (x:) . concat $ transpose
      [ runOmega $ liftM2 (/ ) v v
      , runOmega $ liftM2 (- ) v v
      , runOmega $ liftM2 (**) v v
      ]

main = print . map snd . filter ((==5).fst) $ zip (run 15) [0..]

在第一种情况下我的内存到底去了哪里，我该如何绕过它？

Answer 1

像这样的顶级绑定(bind)

list = [1..1000000]

将延迟生成列表一次，并将其保存在内存中以供后续使用。

一个函数，而不是，

fun x = [1..1000000]

将在每次调用时分配一个新列表，每次都(懒惰地)从头开始重新计算它。因为它是由顶级绑定(bind)引用的，所以它永远不会被垃圾回收。

请注意，这不是 Haskell 强制要求的——只是 GHC 以这种方式工作。

为了比较，试试这个变体:

run x | v <- each $ run x
      = (x:) . concat $ transpose
      [ runOmega $ liftM2 (/ ) v v
      , runOmega $ liftM2 (- ) v v
      , runOmega $ liftM2 (**) v v
      ]
run15 = run 15
main = print . map snd . filter ((==5).fst) $ zip run15 [0..]

您应该会看到大量内存被消耗，因为不会发生垃圾回收。相反，

main = print . map snd . filter ((==5).fst) $ zip run15 [0..]
   where 
   run15 = run 15

应该允许垃圾收集并在少量内存中运行。

(顺便说一句，使用模式绑定(bind)而不是 let/where 让我困惑了一段时间。)