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
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]
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.
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 .
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.
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
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]
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.
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
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
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.
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