How can we write our own filter function?

Suppose there is a list of numbers and I want to filter the list.

sample input

3
10
9
8
2
7
5
1
3
0

output

2
1
0

I want to take this input and filter out the list which is less than 3

In a nutshell:

input = [3, 10, 2, 7, 1]
Enum.reject(input, fn e -> e >= 3 end)
#⇒ [2, 1]
Enum.filter(input, & &1 < 3)
#⇒ [2, 1]
2 Likes

Writing a filter function is usually the second exercise under the recursion topic, straight after having implemented map.

If you do not want to do it using explicit recursion, you can of course use Enum.reduce/3 as well.

You can even use your already written map/2 as a starter. All you need to add is branching of the predicate and the false branch.

1 Like

I don’t want to use Enum.filter function. I want to write my own.

By using recursion and taking advantage of the cons operator we can implement the function by ourselves.

First, the cons operator lets us pattern match on lists:

# Our head equals 3 and our tail to the rest of the list
iex> [head | tail] = [1, 2, 3]
[1,2,3]
iex> head
1
iex> tail
[2,3]

By using recursion we should be able to traverse a list:

defmodule Recurr do

  def traverse(list) do
    [head|tail] = list
    IO.puts(head)   
    traverse(tail)
  end

end

The function above would print numbers just fine:

iex> Recurr.traverse [1,2,3]
1
2
3
** (MatchError) no match of right hand side value: []
    iex:8: Recurr.traverse/1

But fails at the end, this is because we have an empty list and we’re trying to match:

defmodule Recurr do

  def traverse(list) do
    [head|tail] = list
    # Changed printing, just to be more instructive
    IO.puts("[ #{inspect(head)} | #{inspect(tail)} ] = #{inspect(list)} ")
    traverse(tail)
  end

end

iex> Recurr.traverse [1,2,3]                                                
[ 1 | [2, 3] ] = [1, 2, 3] 
[ 2 | [3] ] = [2, 3] 
[ 3 | [] ] = [3] 
** (MatchError) no match of right hand side value: []

# Because we're sending an empty list [] to traverse(list) it cannot 
# further match with the cons operator

We just need to state our base case, the function that should match when our list is empty:

defmodule Recurr do

  def traverse([]) do
    IO.puts "end"
  end

  def traverse(list) do
    [head|tail] = list
    IO.puts("[ #{inspect(head)} | #{inspect(tail)} ] = #{inspect(list)} ")
    traverse(tail)
  end

end

iex> Recurr.traverse [1,2,3]                                                
[ 1 | [2, 3] ] = [1, 2, 3] 
[ 2 | [3] ] = [2, 3] 
[ 3 | [] ] = [3] 
end
:ok

Now… filtering is a matter of following this recursion pattern. You could try something very similar that filters say “pair numbers”.

defmodule Recurr do

  def filter_pairs([]) do
    
  end

  def filter_pairs([head | tail] = list) do
    # filter logic
    filter_pairs(list) # recursion
  end

end

After that you could make it more generic by passing/injecting a function into a more generic filter(list, fun) function :slight_smile:.

I hope I didn’t overexplained too much, any doubts just let me know.

In this case the input was a linked list, therefore the cons [ | ] = list operator is a natural fit. Other data structures would require a different approach.

6 Likes

You can always read the source code for how it’s done in Elixir: https://github.com/elixir-lang/elixir/blob/cc8093aad9b58f32a2300e31838434275ec3664a/lib/elixir/lib/enum.ex#L3290-L3300

5 Likes

As others above have mentioned using recursion will get the job done. You can define a function filter_numbers(list, fun) that takes a list and a function and returns a new list of filtered numbers. Using recursion you can write it like this.

defmodule MyFilter do

  def filter_numbers(list, fun) do
    filter_numbers(list, fun, [])
  end

  def filter_numbers([], _fun, acc) do
    Enum.reverse(acc)
  end

  def filter_numbers([h|t], fun, acc) do
    case fun.(h) do
      true ->
        filter_numbers(t, fun, [h|acc])

      false ->
        filter_numbers(t, fun, acc)
    end
  end

end
iex> numbers = [3, 10, 9, 8, 2, 7, 5, 1, 3, 0]
[3, 10, 9, 8, 2, 7, 5, 1, 3, 0]

iex> MyFilter.filter_numbers(numbers, & &1 < 3)
[2, 1, 0]

iex> MyFilter.filter_numbers(numbers, & &1 > 3)
[10, 9, 8, 7, 5]
4 Likes

It would help me if you could explain me about acc.

Its used to make the function tail-recursive.

A technique to safe against fast growing stacks. It’s one of those premature optimisations that many functional programmers do intuitively after they passed a certain point without really thinking about it.

In most cases it does not matter much in terms of speed if you implement body- or tail-recursive list-to-list functions, as the “cons” operator gets some special treatement on the BEAM.

If though you construct values that are not lists in a recursive function, tail recursiveness can give you a lot.

1 Like

The examples are in Erlang, but I do like the explanations of recursion/tail recursion/why reverse is needed etc here: https://learnyousomeerlang.com/recursion#hello-recursion

2 Likes

Please note some off topic replies have been removed.

@siddhant3030 it isn’t really clear from your original post what you want from readers of your thread - a solution or just some guidance in getting there? It would be helpful to include more info when posting such threads, thanks :smiley:

2 Likes

Using Enum.reduce/3 suggested by @NobbZ you can do something like this:

defmodule FilteringWithReduce do
  def filter(list, func) do
    Enum.reduce(list, [], fn elem, acc ->
      if func.(elem) do
        acc ++ [elem]
      else
        acc
      end
    end)
  end
end

less_than_three = fn arg1 -> arg1 < 3 end
input = [3, 10, 9, 8, 2, 7, 5, 1, 3, 0]

input
|> FilteringWithReduce.filter(less_than_three)
|> Enum.map(&IO.puts/1)

Appending to the accumulator is not only an antipattern but also makes your function quadratic in runtime.

For a twice as long result list the function will take 4 times as long.

1 Like

Learn about elixir comprehensions yesterday, and just tried it:

input = [3,10,9,8,2,7,5,1,3,0]
for n <- input, n < 3, do: n
1 Like