Filtering when an infinite list begins to repeat

Question

I am creating a sequence as a [Integer] in Haskell. The mathematical definition of the sequence is such that it repeats for some positive integers. In such a situation, I want to terminate the sequence and determine the length of the finite list.

My attempt at a solution is to first create an infinite list from the mathematical sequence. Then I want to filter the list for all elements until the first element repeats. The result should not include the repeating head of the list.

I have two questions/concerns here:

1) How do I match the head of the list to an element later in the list? 2) Is this an efficient method of solving my problem? (I will add more details about the exact sequence later if needed. For now I am looking for general comments.)

Answer 1

The algorithm that you described can simply be implemented like this:

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

It does exactly what you describe: it takes the head of some list, and collects the part of the list up until that head element appears again in the list. So, for example:

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

Answer 2

The first element might never repeat in a sequence like 1,2,3,4,5,3,4,5,3,4, ... , where (a !! i) == (a !! j) ==> (a !! (i+1)) == (a !! (j+1)) (like you added in a comment, which is different from what you've asked for in the question).

This is known as cycle detection and was recently discussed e.g. here.