Return true if a list has duplicates otherwise false

Andres

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.

14 comments

#lists

0 4862 14

2024-07-07 20:58:56 UTC

Showing Posts 14 to 5

Show Best Posts
Show All (oldest first)
Show All (newest first)

silverdr

Alternatively (ab)using (instead of repurposing) the implementation of Enum.uniq/1

!Enum.empty?(list -- Enum.uniq(list))

Probably wouldn’t use it for huuge lists though

Post #14

mayel

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

Post #13

Andres

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

Post #12

peerreynders

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.

Post #11

Andres

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!

Post #10

Andres

Hi @NobbZ
Thanks so much for your help.

Post #9

alexiss

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

Post #8

NobbZ

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

Post #7

Andres

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!

Post #6