Нахождение индекса элемента в списке - PullRequest
Новая
       7

Нахождение индекса элемента в списке

2 голосов
/ 24 сентября 2019

Я новичок в Хаскеле, и у меня возникли проблемы с тренировочными программами.Для этого конкретного я хочу найти индекс элемента в списке (первый элемент в 0).Если данный элемент не появляется в списке, у меня есть программа возврата -1.

Вот мой код: 

indexOf :: (Eq a) => a -> [a] -> Int
indexOf n [] = (-1)
indexOf n (x:xs)
    | n == x    = length(xs)
    | otherwise = n `indexOf` xs

У меня есть опыт работы как с C, так и с Java, поэтому мой инстинкт инстинкта заключается в том, чтобы получать счетчик приращений каждый раз, когда я прохожу список, но,Я продолжаю напоминать себе, что Хаскелл работает не так.Я знаю, что мой код перемещает заголовок списка каждый раз, когда он проходит, и когда я делаю "length (xs)", он просто находит длину оставшейся части списка.Понятно, я здесь очень тупой.Может кто-нибудь предложить какие-либо указатели или рекомендации о том, как я могу заставить этот кусок кода работать?

Ответы [ 4 ]

5 голосов
/ 24 сентября 2019

Эта функция уже присутствует в библиотеке (elemIndex), но давайте все равно ее реализуем.

Учитывая xs = [x0,x1,...], мы имеем zip xs [0..] = [(x0,0),(x1,1),...].Затем мы можем найти в последнем списке пару, удовлетворяющую предикату \(x,_) -> x==n. 

import Data.List

indexOf :: (Eq a) => a -> [a] -> Maybe Int
indexOf n xs = fmap snd . find (\(x,_) -> x==n) $ zip xs [0..]

Выше, zip добавляет индексы, find вернет Just (n,index) в случае успеха и fmap snd преобразует это в Just index.

Обратите внимание, что мы предпочитаем возвращать Nothing вместо -1, что не является идиоматическим в Haskell, где мы предпочитаем использовать Maybe вместо

Наконец, обратите внимание, что приведенный выше код не является неэффективным: благодаря лени, zip будет добавлять индексы только к тем элементам, которые требуются find, поэтому он не будет сканировать весь список, если нужный элемент не найден..

В качестве упражнения может потребоваться кодировать fmap snd . find (\(x,_) -> x==n) с явной рекурсией.

5 голосов
/ 24 сентября 2019

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

indexOf :: (Eq a) => a -> [a] -> Int
indexOf n [] = -1
indexOf n (x:xs)
    | n == x    = 0
    | otherwise = case n `indexOf` xs of
        -1 -> -1
        i  -> i + 1
5 голосов
/ 24 сентября 2019

Я решил бы создать другую рекурсивную функцию с той же характеристикой и дополнительным параметром Int для работы в качестве аккумулятора: 

indexOf :: (Eq a) => a -> [a] -> Int
indexOf n xs = go 0 n xs
    where
        go i n [] = (-1)
        go i n (x:xs)
             | n == x    = i
             | otherwise = go (i+1) n xs
4 голосов
/ 24 сентября 2019

В Haskell обычно используют Maybe a для возврата значения a, но если не все входные данные как таковые действительны.Для неверного ввода мы возвращаем Nothing, для действительного, мы возвращаем Just x с x результатом.

Таким образом, мы можем реализовать indexOf, где мы сопоставляем пустой список с Nothing.Если первый элемент списка равен элементу, который мы ищем, мы возвращаем Just 0.Если первый элемент не совпадает с искомым, мы возвращаемся к концу списка и увеличиваем значение, заключенное в Just, если есть такое значение: 

indexOf :: Eq a => a -> [a] -> <b>Maybe Int</b>
indexOf y = go
    where go [] = Nothing
          go (x:xs) | x == y = Just 0
                    | otherwise = (1+) <$> go xs
...