我的“重复排列”代码中的递归调用是否会累积而堵塞 RAM？

一些背景知识：

我是一名业余程序员，几个月前，在学习了一段时间的 Mathematica 编程（我的第一语言）之后，我利用业余时间学习了 Haskell。我目前正在阅读 Will Kurt 所著的第二本 Haskell 书，但要让自己对 Haskell 代码感到满意还有很长的路要走。到目前为止，Codeabbey 一直是我进行实验和学习的平台。

我编写了一段代码来生成给定数字的排列，处理可能的重复数字，因此对于 588，它将在内部生成 588、858 和 885。

但是，因为我想扩展到相当大的输入数字（认为可能甚至有一百位数字长），所以我不想输出整个列表，然后对其执行计算，而是当场检查生成的每个数字对于某个属性，如果它有，那么我们就有一个获胜者，该数字作为输出返回，并且无需遍历庞大列表的其余部分。如果不幸的是没有找到所需的数字，并且我们未能成功地完成所有可能的排列，它会输出“0”。

我还选择将其设为命令行程序，通过 gnu parallel 向其提供值，以加快工作速度。

所以这是代码

import System.Environment

import Data.List 

toDigits :: Integer -> [Integer]
toDigits n = map (\n -> read [n]) (show n)

fromDigits :: Integral a => [a] -> Integer
fromDigits list = fromDigitsHelperFunction list 0

fromDigitsHelperFunction :: Integral a => [a] -> Integer -> Integer
fromDigitsHelperFunction [] acc = acc
fromDigitsHelperFunction (x:[]) acc = (fromIntegral x) + acc
fromDigitsHelperFunction digits@(x:xs) acc = fromDigitsHelperFunction xs (acc + ((fromIntegral x) * 10 ^((length digits) - 1 )))

testPermutationsWithRepetition :: ([Integer],Int,[Int],[(Int,Integer)]) -> [Integer]
testPermutationsWithRepetition (digits, index, rotationMap, registeredPositions)
   | index == 0 && rotationMap !! index == 0                                    = [0,0,0] --finish state (no more recursion). Nothing more to do
   | index == digitsLength - 1 && beautyCheck (fromDigits digits)           = digits
   | index == digitsLength - 1                                                  = testPermutationsWithRepetition (digits, index-1, rotationMap, registeredPositions)
   | not ((index,digits!!index) `elem` registeredPositions)                     = testPermutationsWithRepetition (digits, index+1, rotationMap, (index,digits!!index):registeredPositions)
   | rotationMap!!index == 0                                                    = testPermutationsWithRepetition (digits, index-1, restoredRotMap, restoredRegPositions)
   | rotationMap!!index > 0 && (index,digits!!index) `elem` registeredPositions = testPermutationsWithRepetition (shiftLDigits, index, subtractRot, registeredPositions)
   where digitsLength = length digits
         shiftLDigits = (fst splitDigits) ++ (tail $ snd splitDigits) ++ [head $ snd splitDigits]
         splitDigits = splitAt index digits
         restoredRotMap = (fst splitRotMap) ++ [digitsLength - index] ++ (tail $ snd splitRotMap)
         splitRotMap = splitAt index rotationMap
         restoredRegPositions = filter (\pos -> fst pos < index) registeredPositions  --clear everything below the parent index
         subtractRot = (fst splitRotMap) ++ [(head $ snd splitRotMap) - 1] ++ (tail $ snd splitRotMap)


--Frontend function for testing permutations by inputting a single parameter (the number in digit form)
testPermsWithRep :: [Integer] -> [Integer]
testPermsWithRep digits = testPermutationsWithRepetition (digits, 0, [length $ digits, (length $ digits) -1 .. 1], [])

main :: IO ()
main = do
   args <- getArgs
   let number = read (head args) :: Integer
   let checkResult = fromDigits $ testPermsWithRep $ toDigits number
   print checkResult

这实际上是一个顺序过程，其中一个索引变量指向数字列表上的某个数字，并根据我的规则对该列表执行递归调用。这些函数通过数字列表跟踪迄今为止在某些位置访问过的数字的进度（以避免重复遵循已经访问过的路径，直到到达最后一个数字（索引==长度-1）。如果我们到达那里的数字通过了美丽检查，它以产生的数字退出。

现在，在 Mathematica（或者我猜任何命令式语言）中，我可能会使用 While 循环和 Cases 进行检查，并通过程序的逻辑来实现这一点，无论计算需要多长时间（生成排列并检查它们是否有效性）它将需要适量的内存，足以真正保存“registeredPositions”列表（您可以将其称为特定位置中访问过的数字的记录，因此当我们深入索引但被清理时，它是一个变量列表当我们向后移动时向上）。然而在这种情况下，递归调用就像看起来一样堆积起来，整个事情就像一个fork炸弹，对于足够大的数字（例如27777772222222222222222223333）并最终崩溃。这种行为是否可以在 Haskell 中以不同的方式处理，或者是否没有办法避免递归和内存占用？

我真的很喜欢 Haskell，因为这些程序具有逻辑意义，但我也想将它用于像性能（和资源）很重要的情况。

作为旁注，我兄弟指出了这一点通过重复数字打印所有排列的算法在 C 中，速度相当快（虽然只生成一个列表），最重要的是具有最小的内存占用，尽管我可以看出其中还使用了递归。除此之外，我对 C 毫无头绪，而且我想坚持使用 Haskell，如果它最终能做我想做的事的话。

欢迎任何帮助。祝你有美好的一天！

编辑： 根据 Soleil 的建议，我使用评论中提供的附加信息更新我的帖子。具体来说：

1. 使用“ghcchecking_program.hs”编译后，我使用“./checkingprogram 27777772222222222222222223333”运行该程序。在具有 4GB RAM 的 i5 3470 上，它运行大约 10 分钟，然后因分段错误而退出。在我兄弟的 32GB 机器上，他让它运行直到占用 20GB RAM。我想不需要再进一步了。我的测试是通过 Win10 WSL 在 Ubuntu 上进行的。他的是裸Linux

2. testPermsWithRep 只是 testPermutationsWithRepetition 的前端，因此我只能提供数字，而 testPermsWithRep 创建初始参数并使用这些参数调用 testPermutationsWithRepetition。它准确地输出 testPermutationsWithRepetition 的输出，要么是通过测试的数字（以数字形式），要么是 [0,0,0]。现在进行测试，beautyCheck 函数只是测试该数字的个位数除数，返回 True 或 False。我没有包括它，因为它确实无关紧要。它甚至可能只是一个“大于 x 数”的测试。

举个例子，调用“testPermsWithRep [2,6,7,3]”将调用“testPermutationsWithRepetition ([2,6,7,3], 0, [4,3,2,1],[])”等等从该函数中出来， testPermsWithRep 也会返回它。

您的程序的性能问题与递归无关。相反，您似乎在旋转图中遇到了部分评估的惰性数据结构的累积。如果您使用，您的程序将在恒定内存中运行deepseq包以充分强制评估restoredRotMap:

-- Install the `deepseq` package and add this import
import Control.DeepSeq

-- And then change this one case
... | rotationMap!!index == 0 = restoredRotMap `deepseq`
      testPermutationsWithRepetition (digits, index-1, restoredRotMap, restoredRegPositions)

编译为ghc -O2并使用beautyMap _ = False，它以大约 6 兆的固定驻留内存使用量运行。

其他一些绩效目标：

• 您可能想要更换大部分Integer类型与Int，因为这样会更快。我想你只需要Integer对于输入toDigits和输出fromDigits，其他一切都可以Int，因为它都是索引和数字。
• 更大的胜利将是用更好的数据结构替换您的轮换图和注册位置。如果您发现自己拼接了很多列表listpart1 ++ [x] ++ listpart2调用，这将带来巨大的性能成本，并且线性查找(!!)也没有帮助。