Return true if a list has duplicates otherwise false

Questions / Help
1

Hello.
I’m trying to check if a list has duplicates.
I didn’t have problems doing it with length and size:

def duplicate(list) do
    a = length(list)
    b = MapSet.size(MapSet.new(list))
    a !== b
end

I also did it with Enum and pattern matching but I’m pretty sure there is a better way:

defmodule Checker do
    def check(x) when is_boolean(x), do: x
    def check(x), do: false
end

def main(list) do
    list
    |> Enum.reduce_while(%MapSet{}, fn x, acc ->
      if x not in acc, do: {:cont, MapSet.put(acc, x)}, else: {:halt, true}
    end)
    |> Checker.check()
end

Could you help me to improve the last implementation in a more idiomatic way?

Thanks.

2 
def has_duplicates?(list) do
  list
  |> Enum.reduce_while([], fn x, acc ->
    if x in acc, do: {:halt, 0}, else: {:cont, [x | acc]}
  end)
  |> is_integer()
end
1 Like
3

Welcome,

Maybe You can compare the length of original list with the one You get from Enum.uniq

4

Maybe something like this:

def has_duplicates?(list), do: Enum.uniq(list) != list
2 Likes
5

@l00ker in your case list will be iterated twice - first to make uniq and second to compare with original list

1 Like
6

Hi @l00ker
Very nice one liner!
Thanks so much!

7

Thanks so much @alexiss.
I really liked:

if x in acc, do: {:halt, 0}, else: {:cont, [x | acc]}

and

|> is_integer()

I changed my code like this:

def has_duplicates?(list) do
    list
    |> Enum.reduce_while([], fn x, acc ->
      if x in acc, do: {:halt, false}, else: {:cont, [x | acc]}
    end)
    |> is_boolean()
  end

Thanks so much for your help and ideas!

8

But reducing and finding the elements in a list again results in a runtime of O(n log n), using a MapSet is O(n).

3 Likes
9

Agree, I miss it. The final proposal whould be:

def has_duplicates?(list) do
  list
  |> Enum.reduce_while(%MapSet{}, fn x, acc ->
    if MapSet.member?(acc, x), do: {:halt, false}, else: {:cont, MapSet.put(acc, x)}
  end)
  |> is_boolean()
end
6 Likes
10

Hi @NobbZ
Thanks so much for your help.

11

Beautiful @alexiss

def has_duplicates?(list) do
  list
  |> Enum.reduce_while(%MapSet{}, fn x, acc ->
    if MapSet.member?(acc, x), do: {:halt, false}, else: {:cont, MapSet.put(acc, x)}
  end)
  |> is_boolean()
end

I learned so much!
Thanks so much @NobbZ and @alexiss!

12

Alternately shamelessly repurposing the implementation (uniq_list/3) of Enum.uniq/1:

defmodule Demo do
  def duplicates?(list),
    do: duplicates?(list, %{})

  defp duplicates?([], _) do
    false
  end

  defp duplicates?([head|tail], set) do
    case set do
      %{^head => true} ->
        true
      _ ->
        duplicates?(tail, Map.put(set, head, true))
    end
  end

  def run(list) do
    list
    |> duplicates?()
    |> inspect()
    |> IO.puts()
  end
end

list = [1, 2, 3, 3, 2, 1]
uniq_list = Enum.uniq(list)
Demo.run(list)      # true
Demo.run(uniq_list) # false

A lot can be learned by scouring through Elixir’s source code. The important thing is to understand how it works.

6 Likes
13

This is amazing!

defmodule Demo do
  def duplicates?(list),
    do: duplicates?(list, %{})

  defp duplicates?([], _) do
    false
  end

  defp duplicates?([head|tail], set) do
    case set do
      %{^head => true} ->
        true
      _ ->
        duplicates?(tail, Map.put(set, head, true))
    end
  end

  def run(list) do
    list
    |> duplicates?()
    |> inspect()
    |> IO.puts()
  end
end

Thanks so much @peerreynders

14

Found this useful and adapted it to be able to use a function to compare elements:

  def has_duplicates?(list, fun \\ nil),
    do: check_has_duplicates?(list, %{}, fun || fn x -> x end)
  
  defp check_has_duplicates?([], _, _) do
    false
  end

  defp check_has_duplicates?([head|tail], set, fun) do
    value = fun.(head)

    case set do
      %{^value => true} ->
        true
      _ ->
        check_has_duplicates?(tail, Map.put(set, value, true), fun)
    end
  end