Looping over Sets using Recursion

This is how to implement sum with recursion.

def sum(list), do: sum(list, 0)
def sum([], s), do: s
def sum([head|tail], s), do: sum(tail, s + head)

In more complex scenario, You pass the state of the iteration in a recursive way.

That is a tuple.

I get how we can do this using lists. However, how can we implement this with sets or maps?

Sets (MapSet) in Elixir are implemented using Maps.
When you do this:

[1, 2, 3]
|> MapSet.new()
|> Map.to_list()

you will see, that the result is this

[__struct__: MapSet, map: %{1 => [], 2 => [], 3 => []}, version: 2]

That means, that the MapSet is just a map with some special keys (similar to Struct). That means you’re able to pattern match on the map key of the MapSet map.

So some naive implementation could be something like this:

defmodule RecursiveMapSet do
  def sum(%{map: set}) when map_size(set) == 0 do
    0
  end
  
  def sum(set) do
    {[element], rest_of_the_set} = Enum.split(set, 1)
    element + sum(MapSet.new(rest_of_the_set))
  end
end
  
set = MapSet.new([1, 2, 3])
RecursiveMapSet.sum(set) # 6

Anyway, I feel like ergonomics of lists are far better than MapSet, so I would just convert it to list, do the recursive work and then convert back to MapSet.

UPDATE: As @hauleth mentioned below, the fact that MapSet is just a Map is an implementation detail, that you should not rely on, because it can change in the future.

MapSet.t() is @opaque which mean that You cannot rely on it’s internal representation, and that mean that your code can be broken any time (even in patch Elixir version).

The only way to traverse set in the safe way is:

set = MapSet.new([1, 2, 3])

recursive_sum(Enum.to_list(set))

But if you just want a sum, then You can do:

Enum.sum(set)

And it will do all magic automatically.

Yes, sorry. I forgot to mention that in my post. I updated it.

For completeness, I just want to point out that MapSet.to_list (MapSet — Elixir v1.12.3) also exists. That’s my go-to for enumerating sets.