Finding the index of an element in a list

Question

I'm a beginner in Haskell and I've been having trouble with my practice programs. For this particular one, I want to find the index of an element in a list (the first element being at 0). If the element given does not appear in the list, I am having the program return -1.

Here is my code:

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

I have experience in both C and Java, so my gut instinct is to get a counter to increment every time I go through the list, but, I keep reminding myself that isn't how Haskell works. I'm aware that my code is shifting the head of the list every time it goes through and when I do "length(xs)", it is merely finding the length of the remainder of the list. Clearly, I'm very stumped here. Can anyone offer any pointers or recommendations on how I can get this piece of code to work?

Answer 1

The way I'd solve it is create another recursive function with the same singature plus additional Int parameter to work as accumulator:

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

Answer 2

Instead of a counter (increment as you go down the list) you can also modify the return value as you go back up again:

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

Answer 3

这个函数已经存在于库（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)使用显式递归进行编码。