haskell - 过滤无限列表导致 Haskell/GHCI 中内存过载

Question

我正在尝试编写一些 Haskell 代码，它会输出一堆有效的数独谜题。这是我到目前为止的代码:

import Data.List (nub, permutations, transpose)

-- Recursively build list of possible permutations of a certain length, allowing duplicates
genPermutations list length
    | length <= 0 = [[]]
    | length == 1 = [[a] | a <- list]
    | otherwise = [[a]++b | a <- list, b <- genPermutations list $ length - 1]

-- Generate as flat list of length 9, then format
squares = [[take 3 a,take 3 $ drop 3 a, drop 6 a] | a <- permutations [1..9]]
sudokus = [[take 3 a,take 3 $ drop 3 a, drop 6 a] | a <- genPermutations squares 9]

-- Takes a sudoku as a 4d array, return True/Flase based on rules of sudoku
-- Does not check for duplicates within a square because generated sudokus shouldn't have any
checkSudukoValid x = (foldr (==) True $ map screenLineForDuplicates x) && (foldr (==) True $ map screenLineForDuplicates $ transposeSudoku x)
    where transposeSudoku x = transpose(map (\x -> map transpose x )  x)
          screenLineForDuplicates [[],[],[]] = True
          screenLineForDuplicates [a:al,b:bl,c:cl] = check && screenLineForDuplicates [al,bl,cl]
              where check = (length line)  == (length $ nub line)
                    line = concat [a,b,c]


-- Known good sudoku for testing
knownGood = [[[[9,8,3],[6,1,4],[5,2,7]],[[6,5,7],[2,8,9],[4,3,1]],[[2,4,1],[5,7,3],[9,6,8]]],[[[8,6,5],[4,3,1],[7,9,2]],[[3,2,4],[7,9,8],[1,6,5]],[[7,1,9],[6,5,2],[3,8,4]]],[[[2,7,8],[3,5,9],[1,4,6]],[[5,1,3],[8,4,6],[9,7,2]],[[4,9,6],[1,2,7],[8,3,5]]]]

这段代码的重要部分是，它生成一个可能有效的数独谜题列表以及一个方法(如果单个谜题有效)。根据我的理解，我应该能够过滤所述列表以得到一些有效的数独: head $filter checkSudukoValid sudokus

当我运行此命令时，GHCI 终止了我的进程，这似乎是由于内存问题。我不明白的是为什么我会遇到内存问题。 Haskell 不应该一次一个地懒惰地过滤列表中的项目吗？为什么这会比 filter checkSudukoValid $ take 5 sudokus

占用更多的内存

关于 Haskell 如何处理会导致这种情况的无限列表，我缺少什么？是否有一个标准的解决方案可以让这个变得更加懒惰，从而使我不会遇到内存问题？

Answer 1

问题肯定出在生成代码中，而不是检查代码中(尽管两者都有很多东西需要更改)。具体来说，您的 genPermutations 实现似乎使用越来越多的 RAM。我还没弄清楚为什么会这样，但如果你使用

genPermutations xs n = map (take n) $ permutations xs

内存使用量下降到恒定水平。然而，这实际上不会让你的程序正常工作，至少有两个原因。

原因之一是你的有效性测试是错误的；正如我之前提到的，折叠 (==) 并不符合您的想法。你本来想做的是

checkSudukoValid x = (all screenLineForDuplicates x) && (all 
screenLineForDuplicates $ transposeSudoku x)
    where transposeSudoku x = transpose(map (\x -> map transpose x )  x)
          screenLineForDuplicates [[],[],[]] = True
          screenLineForDuplicates [a:al,b:bl,c:cl] = check && screenLineForDuplicates [al,bl,cl]
              where check = (length line)  == (length $ nub line)
                    line = concat [a,b,c]

这效率非常低，但我认为这可能是正确的。

另一个原因更为严重:无论使用我的genPermutations版本还是你的版本，在你遇到第一个有效的谜题之前，你都会遇到大量无效的谜题。我没有足够的耐心等待。