Haskell program for finding the position of an element in a list
I need to write a function to find the position of one specific item in a list. I wrote like this:
findPos list elt | list == [] = -1
| head list == elt = 0
| otherwise = 1 + (findPos (tail list) elt)
but how to do it in case of duplicate item in the list? For example: list= [2,4,9,4,8]
and I want element position "4" then has 2 positions: second and fourth. How would a simple function be for this?
source to share
You should return a lazy-evaluated list of indices for the matching elements.
An easy, functional way to do this is to first index the list with zip [0..]
, then filter that zipped list into the second element, and permanently remove the rest of the elements to preserve the indexes.
-- first version
findPos list elt = map fst $ filter ((elt==).snd) $ zip [0..] list
-- second version, using list comprehensions
findPos list elt = [index | (index, e) <- zip [0..] list, e == elt]
source to share
You can make it return a list of indices. To make this work, you need to change several functions in the function:
- Instead of -1, return an empty list for the empty case (returning -1 is a bad idiom anyway, you should replace "Maybe" instead, since it is more meaningful).
- Instead of
findPos
recursively calling and adding 1 to the result, you should create a helper function that takes a counter (which starts at 0) and increments the counter by 1. - When you find this element, instead of returning 0, you should return the current count value that was added to the recursion result at the tail of the list (with the count up).
However, this functionality already exists in Data.List
and is called elemIndices
. Therefore, unless this is a purely educational exercise or homework assignment, you don't need to completely overestimate it.
source to share
You can also use a fold:
findPos :: Eq a => a -> [a] -> [Int]
findPos elem = reverse . fst . foldl step ([],0) where
step (is,i) e = (if e == elem then i:is else is, succ i)
Writing in such a way that it seems like a while loop in imperative languages is possible, but quite verbose:
findPos elem list = reverse $ thrd $ until finished step (list,0,[]) where
finished (x,_,_) = null x
step (e:es, c, acc) = (es, succ c, if e == elem then c:acc else acc)
thrd (_,_,x) = x
source to share
I think the best answer is from Crewe. I suggest another idea for finding the first position of an element (not all positions) if that element is in the list.
Let's assume the item is in a list:
indexOf elt list = length $ takeWhile (/=elt) list
The list moves from the beginning to the first occurrence of elt, but it stops when elt is found.
source to share