列表程序中的空间泄漏

我正在解决Haskell中Project Euler的一些问题.我为它写了一个谜语程序,它没有像我预期的那样工作.

当我在运行程序时查看任务管理器时,我发现它在ghc上使用了> 1 GB的RAM.我的一个朋友在Java中编写了一个具有相同含义的程序,并在7秒内成功完成.

import Data.List

opl = find vw $ map (\x-> fromDigits (x++[0,0,9]) ) 
        $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re]

vw x = hh^2 == x
    where hh = (round.sqrt.fromIntegral) x

re = [0..9]

fromDigits x = foldl1 (\n m->10*n+m) x

我知道这个程序会在给定足够的RAM和时间的情况下输出我想要的数字,但必须有更好的表现方式.

1> Simon Marlow..：

---

这里的主要问题是序列有空间泄漏.它的定义如下:

sequence [] = [[]]
sequence (xs:xss) = [ y:ys | y <- xs, ys <- sequence xss ]

所以问题是递归调用产生的列表sequence xss被重用于每个元素xs,所以直到最后它才能被丢弃.没有空间泄漏的版本是

myseq :: [[a]] -> [[a]]
myseq xs = go (reverse xs) []
 where
  go [] acc = [acc]
  go (xs:xss) acc = concat [ go xss (x:acc) | x <- xs ]

PS.答案似乎是Just 1229314359627783009

编辑版本避免concat:

seqlists :: [[a]] -> [[a]]
seqlists xss = go (reverse xss) [] []
 where
   go []       acc rest = acc : rest
   go (xs:xss) acc rest = foldr (\y r -> go xss (y:acc) r) rest xs

请注意,这两个版本都以与标准不同的顺序生成结果sequence,因此虽然它们适用于此问题,但我们不能将其用作特殊版本sequence.

---

分析将告诉您泄漏是按顺序和/或列表的(>> =)的定义,并且泄漏由列表单元格组成.除此之外,您必须推断列表上的序列如何工作以理解泄漏的原因.但请注意,这种泄漏不是由惰性评估引起的 - 严格语言中的相同功能会以相同的方式泄漏.泄漏不是序列或列表monad固有的,而是两者的组合.也许我们可以将列表上的序列专门化为非泄漏版本,我会考虑这一点.