Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Erlang lists:index_of function?

I'm looking for an Erlang library function that will return the index of a particular element in a list.

So, if

X = [10,30,50,70]
lists:index_of(30, X)

would return 1, etc., just like java.util.List's indexOf() method.

Does such a method exist in the Erlang standard lib? I tried looking in the lists module but no luck. Or should I write it myself?

like image 905
Justin Avatar asked Sep 22 '09 09:09

Justin


People also ask

Is a string a list in Erlang?

A string in Erlang is implemented as a linked list of integers.

How do I split a list in Erlang?

You can use lists:split/2 for this: divide(L, N) -> divide(L, N, []).

How do I find the length of a list in Erlang?

You can use length() to find the length of a list, and can use list comprehensions to filter your list. num(L) -> length([X || X <- L, X < 1]).


3 Answers

You'll have to define it yourself, like this:

index_of(Item, List) -> index_of(Item, List, 1).

index_of(_, [], _)  -> not_found;
index_of(Item, [Item|_], Index) -> Index;
index_of(Item, [_|Tl], Index) -> index_of(Item, Tl, Index+1).

Note however that accesing the Nth element of a list is O(N), so an algorithm that often accesses a list by index will be less efficient than one that iterates through it sequentially.

like image 180
sepp2k Avatar answered Oct 16 '22 11:10

sepp2k


As others noted, there are more efficient ways to solve for this. But if you're looking for something quick, this worked for me:

string:str(List, [Element]).
like image 22
William Luxion Avatar answered Oct 16 '22 11:10

William Luxion


Other solutions (remark that these are base-index=1):

index_of(Value, List) ->
   Map = lists:zip(List, lists:seq(1, length(List))),
   case lists:keyfind(Value, 1, Map) of
      {Value, Index} -> Index;
      false -> notfound
   end.

index_of(Value, List) ->
   Map = lists:zip(List, lists:seq(1, length(List))),
   case dict:find(Value, dict:from_list(Map)) of
      {ok, Index} -> Index;
      error -> notfound
   end.

At some point, when the lists you pass to these functions get long enough, the overhead of constructing the additional list or dict becomes too expensive. If you can avoid doing the construction every time you want to search the list by keeping the list in that format outside of these functions, you eliminate most of the overhead.

Using a dictionary will hash the values in the list and help reduce the index lookup time to O(log N), so it's better to use that for large, singly-keyed lists.

In general, it's up to you, the programmer, to organize your data into structures that suit how you're going to use them. My guess is that the absence of a built-in index_of is to encourage such consideration. If you're doing single-key lookups -- that's really what index_of() is -- use a dictionary. If you're doing multi-key lookups, use a list of tuples with lists:keyfind() et al. If your lists are inordinately large, a less simplistic solution is probably best.

like image 23
user502652 Avatar answered Oct 16 '22 13:10

user502652