From 5119c2d93326a798380a57ffae65583c7de5a04d Mon Sep 17 00:00:00 2001 From: Louis Pilfold Date: Mon, 25 May 2020 11:49:08 +0100 Subject: set.intersection --- src/gleam/set.gleam | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) (limited to 'src') diff --git a/src/gleam/set.gleam b/src/gleam/set.gleam index ea0d5c6..a023bae 100644 --- a/src/gleam/set.gleam +++ b/src/gleam/set.gleam @@ -169,3 +169,44 @@ pub fn take( ) -> Set(member) { Set(map.take(from: set.map, keeping: desired)) } + +fn order( + first: Set(member), + second: Set(member), +) -> tuple(Set(member), Set(member)) { + case map.size(first.map) > map.size(second.map) { + True -> tuple(first, second) + False -> tuple(second, first) + } +} + +/// Create a new set that contains all members of both given sets. +/// +/// This function runs in loglinear time. +/// +/// ## Examples +/// +/// > union(from_list([1, 2]), from_list([2, 3])) |> to_list +/// [1, 2, 3] +/// +pub fn union(of first: Set(member), and second: Set(member)) -> Set(member) { + let tuple(larger, smaller) = order(first, second) + fold(over: smaller, from: larger, with: fn(m, a) { insert(a, m) }) +} + +/// Create a new set that contains members that are present in both given sets. +/// +/// This function runs in loglinear time. +/// +/// ## Examples +/// +/// > intersection(from_list([1, 2]), from_list([2, 3])) |> to_list +/// [2] +/// +pub fn intersection( + of first: Set(member), + and second: Set(member), +) -> Set(member) { + let tuple(larger, smaller) = order(first, second) + take(from: larger, keeping: to_list(smaller)) +} -- cgit v1.2.3