Haskell中提取无限重复序列首次迭代子序列的技术问询

嘿，我明白你的需求了——你已经能生成无限的真因子和（aliquot）序列，现在想要从中截取到首次出现重复元素之前的所有元素，也就是拿到序列进入循环前的完整前缀（比如[6,6,...]返回[6]，[23,24,23,...]返回[23,24]）。

核心思路 #

因为Haskell是惰性求值的，我们可以安全地遍历无限序列，同时维护一个已出现元素的集合/列表：每取出一个元素，检查它是否已经在之前的序列中出现过。如果是，就停止遍历并返回已经收集的元素；如果不是，就把它加入收集列表，继续处理下一个元素。

实现方案 #

首先，我们先实现一个通用的辅助函数，用来从任意无限（或有限）序列中截取到首次重复元素前的部分：

基础版本（使用列表跟踪已出现元素）

-- 从序列中截取到第一个重复元素出现前的所有元素
takeUntilDuplicate :: (Eq a) => [a] -> [a]
takeUntilDuplicate = go []
  where
    -- go函数接收已见过的元素列表和剩余待处理序列
    go seen [] = seen  -- 处理有限序列的边界情况，无限序列不会触发
    go seen (x:xs)
      | x `elem` seen = seen  -- 元素已存在，返回已收集的列表
      | otherwise = go (seen ++ [x]) xs  -- 元素不存在，追加后继续遍历

然后把它和你的aliquot函数结合，就能得到想要的结果：

aliquot :: (Integral a) => a -> [a]
aliquot 0 = []
aliquot 1 = [1]
aliquot n = n : (aliquot $ sum $ divisors n)

divisors :: (Integral a) => a -> [a]
divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]

-- 生成aliquot序列的非重复前缀
aliquotCyclePrefix :: (Integral a) => a -> [a]
aliquotCyclePrefix = takeUntilDuplicate . aliquot

优化版本（使用Set提升查找效率）

上面的基础版本中，elem在列表上的查找是O(n)时间复杂度，对于较长的序列来说效率较低。我们可以用Data.Set来存储已出现的元素，把查找时间降到O(log n)：

import qualified Data.Set as Set

takeUntilDuplicate :: (Ord a) => [a] -> [a]
takeUntilDuplicate = go Set.empty []
  where
    go _ seen [] = seen
    go seenSet seenList (x:xs)
      | x `Set.member` seenSet = seenList
      | otherwise = go (Set.insert x seenSet) (seenList ++ [x]) xs

因为Integral类型都实现了Ord接口，所以这个优化版本完全适用于你的aliquot序列场景。

测试示例 #

• 对于aliquotCyclePrefix 6，返回[6]（因为下一个元素就是6，已经在已收集列表中）
• 对于循环序列[23,24,23,24,...]，takeUntilDuplicate会返回[23,24]
• 对于aliquotCyclePrefix 12，返回[12,16,15,9,4,3,1]（因为下一个元素是1，已经存在于列表中）

关键说明 #

Haskell的惰性求值在这里起到了核心作用：我们不需要提前知道序列的长度，程序只会计算到第一个重复元素出现的位置就停止，不会遍历整个无限序列，完全符合你的需求。

内容的提问来源于stack exchange，提问作者schoeberlt