Hofstadter图形序列无限列表依赖问题求助（Haskell）

你的实现中seqA和seqB互相依赖，而filter (notElem seqA)是导致死锁的关键：

• seqA的第n项需要seqB的第n-1项：seqA !! n = (seqA !! (n-1)) + (seqB !! (n-1))
• seqB从[3..]中过滤掉seqA的元素，但notElem会遍历整个seqA来判断元素是否存在。由于seqA是无限懒列表，当检查一个不在seqA中的数时，notElem会无休止地展开seqA的后续元素，永远找不到匹配项，最终导致无限递归挂起。

举个具体例子：计算seqB的第二个元素时，需要检查3是否在seqA里：

1. seqA初始只有[1]，notElem会尝试生成seqA的下一项，这需要seqB的第一项（2），于是seqA的第二项是1+2=3。
2. notElem 3 seqA发现3在seqA里，跳过3去检查4。
3. 要判断4是否在seqA里，notElem需要确认seqA的所有元素都不等于4，但seqA的第三项需要seqB的第二项（也就是我们正在计算的元素），双方互相等待，陷入死循环。

你在GHCI里的操作本质是提前部分初始化seqA，暂时打破了循环依赖：

1. 先定义固定的seqB = [2,4,5,6]，seqA可以基于这个seqB生成前5项：[1, 3, 7, 12, 18]。
2. 重新定义seqB时，filter使用的是已经有具体值的seqA前5项。检查3时能直接找到，跳过；检查4时，4比seqA的下一个元素7小，且不在现有元素里，notElem能快速返回True，把4加入seqB。
3. 再重新定义seqA时，新的seqA会用新的seqB生成更多项，而seqB后续元素又能基于seqA的已生成项继续过滤。

但这个方法有明显局限：当需要seqA的项数超过初始seqB长度对应的项数时，会再次陷入循环依赖死锁——因为seqB的下一个元素需要检查seqA的未生成项，而seqA的这个未生成项又需要seqB的这个元素。

核心是利用seqA严格递增的特性，替换掉会无限遍历的notElem，改用针对有序列表的成员检查函数，这样可以在有限步内判断元素是否在seqA中，避免无限递归。

最终代码：

hof :: Int -> Int
hof = (!!) seqA
  where
    seqA = 1 : zipWith (+) seqA seqB
    seqB = 2 : filter (not . isInSorted seqA) [3..]
    
    -- 针对递增列表的成员检查，x小于当前元素时直接返回False
    isInSorted :: Ord a => [a] -> a -> Bool
    isInSorted [] _ = False
    isInSorted (y:ys) x
      | x == y    = True
      | x < y     = False
      | otherwise = isInSorted ys x

说明：

• isInSorted利用seqA递增的性质，当检查的x小于当前seqA的元素时，直接判定x不可能出现在后续的seqA中（后续元素更大），立即返回False，不会继续遍历seqA的未生成元素。
• 这样filter可以正常生成seqB的元素，seqA也能基于seqB的元素递推生成后续项，形成正确的循环依赖关系。

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