haskell - 查找对于内存来说太大的列表的大小？

Question

这里是全新的 Haskell 程序员。刚刚完成“学习 Haskell”...我感兴趣的是具有某些特定属性的集合有多大。我有一些小参数值的工作代码，但我想知道如何处理更大的结构。我知道 Haskell 可以实现“无限数据结构”，但我只是不知道如何从我现在的位置实现这一目标，而 Learn You a Haskell/Google 也无法帮助我解决这个问题。

这是我的 eSet 给定“小”参数 r 和 t 的工作代码

import Control.Monad
import System.Environment
import System.Exit

myPred :: [Int] -> Bool
myPred a = myPred' [] a
    where
        myPred' [] []         = False
        myPred' [] [0]        = True
        myPred' _  []         = True
        myPred' acc (0:aTail) = myPred' acc aTail
        myPred' acc (a:aTail)
             | a `elem` acc   = False
             | otherwise      = myPred' (a:acc) aTail

superSet :: Int -> Int -> [[Int]]
superSet r t = replicateM r [0..t]

eSet :: Int -> Int -> [[Int]]
eSet r t = filter myPred $ superSet r t

main :: IO ()
main = do
    args <- getArgs
    case args of
        [rArg, tArg] ->
            print $ length $ eSet (read rArg) (read tArg)
        [rArg, tArg, "set"] ->
            print $          eSet (read rArg) (read tArg)
        _ ->
            die "Usage: eSet r r set <set optional for printing set itself otherwise just print the size

编译/运行时我得到

$ ghc eSet.hs -rtsopts
[1 of 1] Compiling Main             ( eSet.hs, eSet.o )
Linking eSet ...
$ # Here's is a tiny eSet to illustrate.  It is the set of lists of r integers from zero to t with no repeated nonzero list entries
$ ./eSet 4 2 set
[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,1,0],[0,0,1,2],[0,0,2,0],[0,0,2,1],[0,1,0,0],[0,1,0,2],[0,1,2,0],[0,2,0,0],[0,2,0,1],[0,2,1,0],[1,0,0,0],[1,0,0,2],[1,0,2,0],[1,2,0,0],[2,0,0,0],[2,0,0,1],[2,0,1,0],[2,1,0,0]]
$ ./eSet 8 4 +RTS -sstderr
3393
     174,406,136 bytes allocated in the heap
      29,061,152 bytes copied during GC
       4,382,568 bytes maximum residency (7 sample(s))
         148,664 bytes maximum slop
              14 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0       328 colls,     0 par    0.047s   0.047s     0.0001s    0.0009s
  Gen  1         7 colls,     0 par    0.055s   0.055s     0.0079s    0.0147s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.298s  (  0.301s elapsed)
  GC      time    0.102s  (  0.102s elapsed)
  EXIT    time    0.001s  (  0.001s elapsed)
  Total   time    0.406s  (  0.405s elapsed)

  %GC     time      25.1%  (25.2% elapsed)

  Alloc rate    585,308,888 bytes per MUT second

  Productivity  74.8% of total user, 75.0% of total elapsed

$ ./eSet 10 5 +RTS -sstderr
63591
  27,478,010,744 bytes allocated in the heap
   4,638,903,384 bytes copied during GC
     532,163,096 bytes maximum residency (15 sample(s))
      16,500,072 bytes maximum slop
            1556 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0     52656 colls,     0 par    6.865s   6.864s     0.0001s    0.0055s
  Gen  1        15 colls,     0 par    8.853s   8.997s     0.5998s    1.8617s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time   52.652s  ( 52.796s elapsed)
  GC      time   15.717s  ( 15.861s elapsed)
  EXIT    time    0.193s  (  0.211s elapsed)
  Total   time   68.564s  ( 68.868s elapsed)

  %GC     time      22.9%  (23.0% elapsed)

  Alloc rate    521,883,277 bytes per MUT second

  Productivity  77.1% of total user, 76.7% of total elapsed

我发现我的内存使用率非常高，并且有大量垃圾收集。运行 eSet 12 6 时，我遇到段错误。

我觉得 filter myPred $ superSet r t 阻止我懒惰地一次将子集制作为一部分，这样我就可以处理更大(但有限)的集合，但我不知道如何改变为另一种方法可以做到这一点。我认为这就是我问题的根源。

此外，由于这是我的第一个 Haskell 程序，因此非常感谢有关风格以及如何实现“pythonic”的 Haskell 模拟的要点!

Answer 1

我怀疑这里的罪魁祸首是replicateM，它有 this implementation :

replicateM cnt0 f =
    loop cnt0
  where
    loop cnt
        | cnt <= 0  = pure []
        | otherwise = liftA2 (:) f (loop (cnt - 1))

问题行是liftA2 (:) f (loop (cnt - 1));可能 loop (cnt - 1) 在所有对 (:) 的调用之间共享，部分应用于 f 的元素，因此 loop (cnt - 1) 必须保存在内存中。不幸的是 loop (cnt - 1) 是一个很长的列表......

说服 GHC 不分享某些内容可能有点棘手。下面对 superSet 的重新定义给了我一个很好的平坦内存使用情况；当然，对于适合内存的示例，它可能会慢一些。关键的想法是让它在未经训练的眼睛(即 GHC)看来就像递归单子(monad) Action 取决于之前所做的选择，即使事实并非如此。

superSet :: Int -> Int -> [[Int]]
superSet r t = go r 0 where
    go 0 ignored = if ignored == 0 then [[]] else [[]]
    go r ignored = do
        x <- [0..t]
        xs <- go (r-1) (ignored+x)
        return (x:xs)

如果您不介意避免优化，更自然的定义也可以:

superSet 0 t = [[]]
superSet r t = do
    x <- [0..t]
    xs <- superSet (r-1) t
    return (x:xs)

...但是使用 -O2 GHC 太聪明了，它注意到它可以共享递归调用。