Andres
Intersection of two MapSets without using MapSet.intersection
Hello.
In my journey to learning Elixir, I gave myself the task of implementing an
algorithm that obtains the intersection of two MapSets without using the
built-in MapSet.intersection/2 function:
a = MapSet.new([3, 3, 3, 2, 2, 1])
b = MapSet.new([3, 4, 5])
# => Expected result #MapSet<[3]>
def intersection_a(a, b) do
Enum.reduce(b, MapSet.new(), fn x, acc ->
if MapSet.member?(a, x) do
MapSet.put(acc, x)
else
acc
end
end)
end
def intersection_b(a, b) do
# Returns a List[3] instead of #MapSet<[3]>
Enum.filter(b, fn x -> MapSet.member?(a, x) end)
end
The intersection_b function returns a List instead of a MapSet.
Why does this happen? 
Any suggestions to improve the algorithm is welcome.
Thanks.
Marked As Solved
sribe
It’s a quirk of Elixir that most of the Enum functions that return collections return lists rather than the type you start with–it has to do with lack of typing and no good way to definitely determine what the return type should be. You’re looking for Enum.into to turn your list into a map.
As for the first algorithm, that is pretty much the core of what you want to do; my only suggestion would be a modification for performance in some edge cases. Imagine that a has 1,000,000 elements and b has one, what does your code do? Now imagine the opposite, a has one and b has 1,000,000 
Also Liked
LostKobrakai
It’s not so much “lack of types”, but more that there are quite a few Enumerable types out there, which cannot be transformed if you’d like to preserve the type. Especially if you’re looking at lazy or infinite collections things might just not work. But even if you look at something as simple as %Date.Range{}. If you map a date range to only the day of month it’s no longer a date range.
Not keeping the shape of data was a conscious decision, which is explained (in a sadly little hidden place) here: Collectable — Elixir v1.16.0
al2o3cr
The source is a good place to start:
lucaong
I think that @sribe is suggesting to choose which collection you iterate through (a or b in your code) depending on which one is the smallest. You can in fact minimize the number of comparisons necessary to produce the intersection by iterating over the smallest of the two collections.
If a has 1,000,000 elements and b has one, iterating through b instead of a lets you produce the intersection after only one comparison instead of 1,000,000 
This is more efficient by virtue of the fact that MapSet.member? has a performance that grows less than linearly with the size of the collection. So making fewer MapSet.member? checks on bigger collections tends to be better than many checks on smaller collections
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Catch errors, track performance, monitor hosts and more.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Develop your skills with books, videos, and courses.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
Courses that'll move you from confusion to "Aha, now I get it!"