Haskell. Вернуть индекс первого повторяющегося числа

Question

Дан список целых чисел. Определите, есть ли в списке одинаковые числа, следующие друг за другом. Вернуть индекс первого повторяющегося числа или -1, если повторений нет.

Функция должна вывести:

duplicateIndex [1,8,3,3,4] -> 2
duplicateIndex [7,7,3,2,5] -> 0
duplicateIndex [1,2] -> -1

Я пытался решить следующим образом, но это решение неверно !

let duplicateIndex lst =  [if x ==y then  lst !!x else (-1) |  x:ys <- tails lst, y <- ys]

Помогите исправить код.

Answer 1

Ваше выражение понимания списка возвращает элемент списка, а не индекс списка (как указано). Кроме того, нечего отслеживать текущее значение индекса.

Если мы ищем решение, которое легко визуализировать, мы можем попробовать использовать zip . Когда речь идет о сравнении двух соседних элементов, обычно используется zip xs (tail xs) в качестве вспомогательного списка.

Но он по-прежнему не включает никакой информации об индексах. Для этого мы должны добавить последовательность индексов как [0..].

Поскольку в конечном итоге мы стремимся вернуть индекс, интересное выражение понимания списка будет начинаться следующим образом:

[ ... | ((x,y), idx) <- zip (zip xs (tail xs)) [0..], ... constraints ... ]

Давайте посмотрим как выглядит наш вспомогательный список:

 λ> 
 λ> printAsLines ys = mapM_  (putStrLn . show) ys
 λ> 
 λ> xs = [1,8,3,3,4,7,5,5,2]
 λ> 
 λ> printAsLines $ zip  (zip xs (tail xs))  [0..]
((1,8),0)
((8,3),1)
((3,3),2)
((3,4),3)
((4,7),4)
((7,5),5)
((5,5),6)
((5,2),7)
 λ> 

Кроме того, при поиске повторяющегося числа нам нужно иметь x == y в качестве ограничения; и мы хотим вернуть индекс, поэтому левая часть понимания списка должна быть idx. Это дает:

[ idx | ((x,y), idx) <- zip (zip xs (tail xs)) [0..], x == y ]

Давайте проверим:

 λ> 
 λ> [ idx | ((x,y), idx) <- zip (zip xs (tail xs)) [0..], x == y ]
 [2,6]
 λ> 

Итак, мы почти закончили: нам просто нужно взять первый элемент последнего понимания списка, если, конечно, есть это вообще первый элемент. В противном случае верните -1. ​​

Это дает следующий код:

duplicateIndex :: Eq α => [α] -> Int
duplicateIndex xs =
    let  indexes = [ idx | ((x,y), idx) <- zip (zip xs (tail xs)) [0..], x == y ]
    in
         if (null indexes) then  (-1)
                           else  head indexes

Языковая ленивость гарантирует, что список indexes не будет оцениваться, кроме поиска первого элемента.

РЕДАКТИРОВАТЬ:

Функцию можно записать более компактно, используя zip3 :

duplicateIndex :: Eq α => [α] -> Int
duplicateIndex xs =
    let   idxs = [ idx | (x, y, idx)  <-  zip3  xs  (tail xs)  [0..],  x == y ]
    in    if  (null idxs)  then  (-1)  else  (head idxs)