How to get the Index of an element in a list, by not using "list comprehensions"?

Question

I'm new in haskell programming and I try to solve a problem by/not using list comprehensions.

The Problem is to find the index of an element in a list and return a list of the indexes (where the elements in the list was found.)

I already solved the problem by using list comprehensions but now i have some problems to solve the problem without using list comprehensions.

On my recursive way:

I tried to zip a list of [0..(length list)] and the list as it self. then if the element a equals an element in the list -> make a new list with the first element of the Tupel of the zipped list(my index) and after that search the function on a recursive way until the list is [].

That's my list comprehension (works):

positions :: Eq a => a -> [a] -> [Int]
positions a list = [x | (x,y) <- zip [0..(length list)] list, a == y]

That's my recursive way (not working):

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)
    in if (a == m) then n:(positions' a xs)
       else (positions' a xs) 

*sorry I don't know how to highlight words

but ghci says:

*Main> positions' 2 [1,2,3,4,5,6,7,8,8,9,2]
[0,0]

and it should be like that (my list comprehension):

*Main> positions 2 [1,2,3,4,5,6,7,8,8,9,2]
[1,10]

Where is my mistake ?

Answer 1

The problem with your attempt is simply that when you say:

let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)

then n will always be 0. That's because you are matching (n,m) against the first element of zip [0..(length (x:xs))] (x:xs), which will necessarily always be (0,x).

That's not a problem in itself - but it does mean you have to handle the recursive step properly. The way you have it now, positions _ _, if non-empty, will always have 0 as its first element, because the only way you allow it to find a match is if it's at the head of the list, resulting in an index of 0. That means that your result will always be a list of the correct length, but with all elements 0 - as you're seeing.

The problem isn't with your recursion scheme though, it's to do with the fact that you're not modifying the result to account for the fact that you don't always want 0 added to the front of the result list. Since each recursive call just adds 1 to the index you want to find, all you need to do is map the increment function (+1) over the recursive result:

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    let ((0,m):ns) = zip [0..(length (x:xs))] (x:xs)
    in if (a == m) then 0:(map (+1) (positions' a xs))
       else (map (+1) (positions' a xs))

(Note that I've changed your let to be explicit that n will always be 0 - I prefer to be explicit this way but this in itself doesn't change the output.) Since m is always bound to x and ns isn't used at all, we can elide the let, inlining the definition of m:

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    if a == x
    then 0 : map (+1) (positions' a xs)
    else     map (+1) (positions' a xs)

You could go on to factor out the repeated map (+1) (positions' a xs) if you wanted to.

Incidentally, you didn't need explicit recursion to avoid a list comprehension here. For one, list comprehensions are basically a replacement for uses of map and filter. I was going to write this out explicitly, but I see @WillemVanOnsem has given this as an answer so I will simply refer you to his answer.

Another way, although perhaps not acceptable if you were asked to implement this yourself, would be to just use the built-in elemIndices function, which does exactly what you are trying to implement here.

Answer 2

We can make use of a filter :: (a -> Bool) -> [a] -> [a] and map :: (a -> b) -> [a] -> [b] approach, like:

positions  :: Eq a => a -> [a] -> [Int]
positions x = map fst . filter ((x ==) . snd) . zip [0..]

We thus first construct tuples of the form (i, yi), next we filter such that we only retain these tuples for which x == yi, and finally we fetch the first item of these tuples.

For example:

Prelude> positions 'o' "foobaraboof" 
[1,2,8,9]