Recursive function to iterate over a list

Questions / Help
,
1

How to write a recursive function, which iterates over a list and checks if an element is in that list in elixir?

2

You can use the Enum.any?. There is excellent documentation.

Or you can roll your own.

def do_something([], _item, data), do: data

def do_something([h | t], item, data) do
 data =  
    if h == item, do: [h | data], else: data
 do_something(t, item, data)
end

Essentially, you are doing your check and calling with the remainder of the list. I recommend looking at the Enum library it has everything you need.

1 Like
3

What exactly is data in that code?

4

@CommandoSev it is a list acting as an accumulator. Here are some examples:

  1. Find out if something exists in a list:
list =  [1,2,3,4]

Enum.any?(list, fn item -> item == 3 end)
true
  1. If you want to get the item if it exists:
list =  [1,2,3,4]

Enum.find(list, fn item -> item == 3 end)
3
  1. If you want to find all of the matches and have them returned in a list:
list = [1, 2, 3, 4, 3]

# The second arg is the accumulator which I have named acc in the anonymous function
Enum.reduce(list, [], fn item, acc -> 
  # If true add the item to the acc list, otherwise return the acc as is
  if item == 3, do: [item | acc], else: acc  
end)
[3,3]

You can replicate the Enum.reduce function by writing your own recursive function:

list = [1, 2, 3, 4, 3]

# match on the empty list and return the accumulator
def my_reduce([], acc, _item), do: acc

# match on the head and tail of the list and test if item exists
def my_reduce([h | t], acc, item) do
acc = 
  if h == item do
   [h | acc] # add the matching item to the accumulator 
  else
   acc # no match so return acc as is
  end
 my_reduce(t, acc, item) # recursivly call my_reduce with the tail of the list and the acc
end

# start the recursive function by calling it
my_reduce(list, [], 3)

Hope this helps. If you tell us exactly what you are trying to do I am sure we can help work it out.

Andrew

2 Likes
5

If you are new to list recursion then you might find this a way to understand the concept. Given a arbitrary list [:a, :b, :elixir, :c, :d], recursing over the items in this list is conceptually like saying “process the first element of the list, then process the rest of the list”.

In Elixir that looks like:

def process_list([first | rest]) do
  [process_element(first) | process_list(rest)]
end

Here the recursion is a very obvious implementation of the description. Process the first element, then process the rest of the list. Its recursive because the function is calling itself.

Will this work? It will to an extent. But what happens if the list is empty? Then there is no first and the function will raise an exception. So we need to cater for the empty list. And in this implementation there will always be an empty list because eventually there is no rest when the function recurses to the end. Therefore:

def process_list([]) do
  []
end

def process_list([first | rest]) do
  [process_element(first) | process_list(rest)]
end

def process_element(:elixir), do: true
def process_element(_other), do: false

This is the simplest form of recursion (and I personally think its the most beautiful) but it won’t cater for all requirements. This form will always return a list the same length as the original list. In your case thats not what you want and therefore an accumulator may be required is order to build a new list. Which is what the great examples from @andrewb do.

4 Likes
6

The recursive thinking:

  1. If the list is empty, then the thing you want to find is definitely not in that list.
  2. If the first element is what you want to find, then you found it.
  3. If the first element is not what you want to find, then find that thing in the rest of the list (which is still a list, could be empty, though)

So the code is

def exist?([], _item), do: false

def exist?([item | _tail], item), do: true

def exist?([_something_else | tail], item), do: exist?(tail, item)
5 Likes
7

There is a special case when the list has only one element, where the rest of the list will be []. You don’t need to match against [head] since [head | rest] will work, but just to keep that in mind

iex(1)> [head | rest] = [1, 2]
[1, 2]
iex(2)> head
1
iex(3)> rest
[2]

iex(4)> [head | rest] = [1]   
[1]
iex(5)> head
1
iex(6)> rest
[]

iex(7)> [head] = [1]       
[1]

iex(8)> [head] = [1, 2]
** (MatchError) no match of right hand side value: [1, 2]

Once you learn how to iterate recursively over a list, study how Enum.reduce/3 and Enum.reduce_while/3 work because pretty much everything can be implemented with these two functions. For example, your initial question could be implemented with reduce_while.

1 Like