1

我尝试编写一个函数来获取整数列表并对其进行过滤，以便返回的列表仅包含与特定模式匹配的数字。不幸的是，顺序必须保持不变。我已经实现了一个无限列表，它按有序序列返回所有有效数字并在列表理解中使用它。这在 ghci 中工作得很好而且很快，但我的问题是，我们需要在我的大学课程中使用更大的拥抱列表，它会导致控制堆栈溢出，我不理解。

我写了最少的例子来证明我的问题：

import Data.List
aList = map (1000*) [0..] -- a example list...

-- works only with lists with a max length of 4093 e.g. [0..4092]  but is fast.
-- (with [0..4093] it results in a Control stack overflow)
inaList :: [Integer] -> [Integer] 
inaList list = [x| x<-list,elem x cap_aList]
    where list_max = maximum list
          cap_aList = takeWhile (<=list_max) aList -- should be computed only once?

-- seems to works even with [0..100000] but is really really slow
-- does not exactly what i want.
inaList_working :: [Integer] -> [Integer] 
inaList_working list = [x| x<-list,elem x $take 1000 aList ]

-- works  with max [0..4092] and is slow.
inaList_2 :: [Integer] -> [Integer] 
inaList_2 list = [x| x<-list,elem x $takeWhile (<=(fromIntegral $maximum list)) aList ]

-- works fast but with max [0..4091].
inaList_3 :: [Integer] -> [Integer] 
inaList_3 list = [x| x<-list,elem x cap_aList ]
    where   list_max = maximum list
            toTake = findPos list_max aList
            cap_aList = take toTake aList

findPos :: Integer -> [Integer] -> Int
findPos i (n:nx)
    | i>=n = 1 + findPos i nx
    | otherwise = 0

如果我使用aList = map (8*) [0..]而不是aList = map (1000*) [0..]. 完成只需要更长的时间，因为它必须进行更多的比较，但不会导致崩溃。因此，列表的长度elem似乎不会影响控制堆栈的长度？

我不知道为什么会发生控制堆栈溢出。甚至[x| x<-liste,foldl' (||) False $map (==x) cap_aList]导致相同的错误。

如果它与普通列表一起使用，列表推导完美无瑕，但如果与takeWhile（参见inaList和inaList_2）一起使用，它会遇到控制堆栈溢出或分段错误。如果take与计算值一起使用（请参阅inaList_3参考资料），它也会崩溃。使用“静态” take（请参阅​​ 参考资料inaList_working）它会突然起作用。我想，where 子句通常应该只计算一次或从不计算。那么为什么列表的构建方式会有所不同呢？如果控制堆栈已满，拥抱不应该尝试减少/计算控制堆栈吗？不幸的是，大多数文档似乎只适用于 ghc。

那么为什么在这种情况下会发生这种控制堆栈溢出，如何避免它以及如何确定控制堆栈的外观/填充方式？是否有多个控制堆栈？

我希望有人能解释发生了什么。

4

0 回答 0