Looping over Sets using Recursion

Questions / Help
1

Hi! As the title suggests, can someone help in giving an example about how we can loop over sets using recursion? I do know that the Enum functions exist, which are extremely helpful, however, I want to try experimenting with sets in a different way.

I am quite confused over what the base case would be for this and how exactly can we get the values of a set each time we call the recursive function.

Any help will be appreciated :smile:

EDIT: One additional thing I would like to add is that we don’t really know what the contents of the set are so we can’t try doing something like this:

def function({a, b, c} do
2

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.

3

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

4

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.

5

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.

2 Likes
6

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

7

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.

1 Like