Elixir Tricks: Building a Recursive List#delete_all Function

Elixir's List module provides us with a number of handy functions for operating on lists, including a delete function that works like this:

List.delete([1, 2, 3], 1)  
=> [2, 3]

But what if we want to remove all occurrences of a particular element from our list? The List module doesn't implement such a function, so, let's build our own!

We'll build our function to operate recursively. It will:

  • Look at the head of the list. If that element is equal to the value whose occurrences we want to remove, we will not grab the element to add to our brand new list.
  • If that element is not equal to the value we want to remove, we will add it to our new list.
  • In either case, we'll grab the tail of the list and repeat the previous step.

Let's get started!

defmodule MyList  
  def delete_all(list, el) do 
    _delete_all(list, el, [])
  end
end  

First, we'll define a public #delete_all function which will wrap a call to a private _delete_all function, our workhorse.

The private _delete_all function takes in arguments of our original list, the value that we want to remove, and an empty list which we will populate with our new list, less all occurrences of the undesired element.

def _delete_all([head | tail], el, new_list)  
when head === el do  
  _delete_all(tail, el, new_list)
end  

The _delete_all function's first job is to determine whether or not the first element in the current list, the head of the list, is the same value as the element we want to remove.

If so, we won't add it to our new list. Instead, we'll call _delete_all again with the remainder of the current list, the tail, and pass in our new_list unchanged.

We accomplish this with a guard clause, the when statement following our function signature.

If the head of the current list is not equal to the value we want to remove, however, we do want to add it to our new_list before moving on.

We'll define another _delete_all function, this time without a guard clause, to meet this condition:

def _delete_all([head | tail], el, new_list) do  
  _delete_all(tail, el, [head | new_list])
end  

We add the current head to our new list like this:

[ head | new_list ]

and we call _delete_all again, this time passing it the remainder of the list, tail.

Lastly, once we empty out or original list so that all of the elements we are keeping are in new_list, we need to return new_list. We'll have one final _delete_all function to match this condition:

def _delete_all([], el, new_list) do  
  new_list
end  

The only problem is that this approach builds and returns a new list in which all of the elements we kept from the original list are populated in reverse order.

So, we'll simply use Enum.reverse on the result of our top-level call to _delete_all. Let's put it all together:

defmodule MyList  
  defmodule MyList  do
  def delete_all(list, el) do 
    _delete_all(list, el, [])
    |> Enum.reverse
  end

  def _delete_all([head | tail], el, new_list) when head === el do
    _delete_all(tail, el, new_list)
  end

  def _delete_all([head | tail], el, new_list) do 
    _delete_all(tail, el, [head | new_list])
  end

  def _delete_all([], el, new_list) do 
    new_list
  end  
end  

And that's it!

subscribe and never miss a post!

Blog Logo

Sophie DeBenedetto

comments powered by Disqus
comments powered by Disqus