list - 当无限列表开始重复时过滤

Question

我[Integer]在 Haskell 中创建了一个序列。该序列的数学定义是它对一些正整数重复。在这种情况下，我想终止序列并确定有限列表的长度。

我的解决方案尝试是首先从数学序列中创建一个无限列表。然后我想过滤所有元素的列表，直到第一个元素重复。结果不应包括列表的重复标题。

我在这里有两个问题/疑虑：

1）如何将列表的头部与列表后面的元素匹配？2）这是解决我的问题的有效方法吗？（如果需要，我稍后会添加有关确切顺序的更多详细信息。现在我正在寻找一般性评论。）

Answer 1

您描述的算法可以简单地实现如下：

findPeriodic :: Eq a => [a] -> [a]
findPeriodic [] = error "there are no periodic sequences in the empty list"
findPeriodic (x : xs) = x : takeWhile (/= x) xs

它完全按照您的描述进行：它获取某个列表的头部，并收集列表的一部分，直到该头部元素再次出现在列表中。因此，例如：

list = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, ...]
findPeriodic list => [1, 2, 3, 4, 5]

Answer 2

第一个元素可能永远不会以1,2,3,4,5,3,4,5,3,4, ..., where之类的顺序重复(a !! i) == (a !! j) ==> (a !! (i+1)) == (a !! (j+1))（就像您在评论中添加的那样，这与您在问题中要求的不同）。

这称为循环检测，最近在此处进行了讨论。