tote/bag

This module has all the functions you may need to work with bags (if you feel something is missing, please open an issue)!

To quickly browse the documentation you can use this cheatsheet:

Creating bags	new, from_list, from_map
Adding or removing items	insert, remove, remove_all, update
Querying the content of a bag	copies, contains, is_empty, size
Combining bags	intersect, merge, subtract
Transforming the content of a bag	fold, map, filter
Converting a bag into other data structures	to_list, to_set, to_map

Types

Bag

</>

A Bag is a data structure similar to a set with the difference that it can store multiple copies of the same item.

This means that you can efficiently check if an element is inside a bag with the contains function, just like a set. At the same time, you can ask how many copies of an item are contained inside a bag using the copies function.

If you are curious about implementation details, a Bag(a) is nothing more than a handy wrapper around a Map(a, Int) that is used to keep track of the number of occurrences of each item.

pub opaque type Bag(a)

Functions

contains

</>

pub fn contains(bag: Bag(a), item: a) -> Bool

Returns True if the bag contains at least a copy of the given item.

Examples

bag.from_list(["a", "b"]) |> bag.contains("a")
// -> True

bag.from_list(["a", "b"]) |> bag.contains("c")
// -> False

copies

</>

pub fn copies(in bag: Bag(a), of item: a) -> Int

Counts the number of copies of an item inside a bag.

Examples

bag.from_list(["a", "b", "a", "c"]) |> bag.copies(of: "a")
// -> 2

filter

</>

pub fn filter(
  bag: Bag(a),
  keeping predicate: fn(a, Int) -> Bool,
) -> Bag(a)

Only keeps the items of a bag the respect a given predicate that takes as input an item and the number of its copies.

Examples

bag.from_list(["a", "b", "a", "b", "c", "d"])
|> bag.filter(keeping: fn(_, copies) { copies <= 1 })
|> bag.to_list
// -> [#("c", 1), #("d", 1)]

fold

</>

pub fn fold(
  over bag: Bag(a),
  from initial: b,
  with fun: fn(b, a, Int) -> b,
) -> b

Combines all items of a bag into a single value by calling a given function on each one.

The function will receive as input the accumulator, the item and its number of copies.

Examples

let bag = bag.from_list(["a", "b", "b"])
bag.fold(over: bag, from: 0, with: fn(count, _, copies) {
  count + copies
})
// -> 3

from_list

</>

pub fn from_list(list: List(a)) -> Bag(a)

Creates a new bag from the given list by counting its items.

Examples

bag.from_list(["a", "b", "a", "c"])
|> bag.to_list
// -> [#("a", 2), #("b", 1), #("c", 1)]

from_map

</>

pub fn from_map(map: Dict(a, Int)) -> Bag(a)

Creates a new bag from the map where each key/value pair is turned into an item with those many copies inside the bag.

Examples

map.from_list([#("a", 1), #("b", 2)])
|> bag.from_map
|> bag.to_list
// [#("a", 1), #("b", 2)]

insert

</>

pub fn insert(
  into bag: Bag(a),
  copies to_add: Int,
  of item: a,
) -> Bag(a)

Adds n copies of the given item into a bag.

If the number of copies to add is negative, then this is the same as calling remove and will remove that many copies from the bag.

Examples

bag.new() |> bag.insert(2, "a") |> bag.copies(of: "a")
// -> 2

bag.from_list(["a"]) |> bag.insert(-1, "a") |> bag.copies(of: "a")
// -> 0

intersect

</>

pub fn intersect(one: Bag(a), with other: Bag(a)) -> Bag(a)

Intersects two bags keeping the minimum number of copies of each item that appear in both bags.

Examples

let bag1 = bag.from_list(["a", "a", "b", "c"])
let bag2 = bag.from_list(["a", "c", "c"])
bag.intersect(bag1, bag2) |> bag.to_list
// -> [#("a", 1), #("c", 1)]

is_empty

</>

pub fn is_empty(bag: Bag(a)) -> Bool

Returns True if the bag is empty.

⚠️ This is more efficient than checking if the bag’s size is 0. You should always use this function to check that a bag is empty!

Examples

bag.new() |> bag.is_empty()
// -> True

bag.from_list(["a", "b"]) |> bag.is_empty()
// -> False

map

</>

pub fn map(bag: Bag(a), with fun: fn(a, Int) -> b) -> Bag(b)

Updates all values of a bag calling on each a function that takes as argument the item and its number of copies.

If one or more items are mapped to the same item, their occurrences are summed up.

Examples

bag.from_list(["a", "b", "b"])
|> bag.map(fn(item, _) { "c" })
|> bag.to_list
// -> [#("c", 3)]

merge

</>

pub fn merge(one: Bag(a), with other: Bag(a)) -> Bag(a)

Adds all the items of two bags together.

Examples

let bag1 = bag.from_list(["a", "b"])
let bag2 = bag.from_list(["b", "c"])
bag.merge(bag1, bag2) |> bag.to_list
// -> [#("a", 1), #("b", 2), #("c", 1)]

new

</>

pub fn new() -> Bag(a)

Creates a new empty bag.

remove

</>

pub fn remove(
  from bag: Bag(a),
  copies to_remove: Int,
  of item: a,
) -> Bag(a)

Removes n copies of the given item from a bag.

If the quantity to remove is greater than the number of copies in the bag, all copies of that item are removed.

⚠️ Giving a negative quantity to remove doesn’t really make sense, so the sign of the copies argument is always ignored.

Examples

bag.from_list(["a", "a"]) |> bag.remove(1, "a") |> bag.copies(of: "a")
// -> 1

bag.from_list(["a", "a"]) |> bag.remove(-1, "a") |> bag.copies(of: "a")
// -> 1

bag.from_list(["a", "a"]) |> bag.remove(10, "a") |> bag.copies(of: "a")
// -> 0

remove_all

</>

pub fn remove_all(from bag: Bag(a), copies_of item: a) -> Bag(a)

Removes all the copies of a given item from a bag.

Examples

bag.from_list(["a", "b", "a"]) |> bag.remove_all("a") |> bag.to_list
// -> [#(b, 1)]

size

</>

pub fn size(bag: Bag(a)) -> Int

Returns the total number of items inside a bag.

⚠️ This function takes linear time in the number of distinct items in the bag.

If you need to check that a bag is empty, you should always use the is_empty function instead of checking if the size is 0. It’s going to be way more efficient!

Examples

bag.from_list(["a", "b", "a", "c"]) |> bag.size
// -> 4

subtract

</>

pub fn subtract(
  from one: Bag(a),
  items_of other: Bag(a),
) -> Bag(a)

Removes all items of the second bag from the first one.

Examples

let bag1 = bag.from_list(["a", "b", "b"])
let bag2 = bag.from_list(["b", "c"])
bag.subtract(from: one, items_of: other) |> bag.to_list
// -> [#("a", 1), #("b", 1)]

to_list

</>

pub fn to_list(bag: Bag(a)) -> List(#(a, Int))

Turns a Bag into a list of items and their respective number of copies in the bag.

Examples

bag.from_list(["a", "b", "a", "c"])
|> bag.to_list
// -> [#("a", 2), #("b", 1), #("c", 1)]

to_map

</>

pub fn to_map(bag: Bag(a)) -> Dict(a, Int)

Turns a Bag into a map. Each item in the bag becomes a key and the associated value is the number of its copies in the bag.

to_set

</>

pub fn to_set(bag: Bag(a)) -> Set(a)

Turns a Bag into a set of its items, losing all information on their number of copies.

Examples

bag.from_list(["a", "b", "a", "c"])
|> bag.to_set
// -> set.from_list(["a", "b", "c"])

update

</>

pub fn update(
  in bag: Bag(a),
  item item: a,
  with fun: fn(Int) -> Int,
) -> Bag(a)

Updates the number of copies of an item in the bag.

If the function returns 0 or a negative number, the item is removed from the bag.

Examples

bag.from_list(["a"])
|> bag.update("a", fn(n) { n + 1 })
|> bag.copies(of: "a")
// -> 2

bag.new()
|> bag.update("a", fn(_) { 10 })
|> bag.copies(of: "a")
// -> 10

bag.from_list(["a"])
|> bag.update("a", fn(_) { -1 })
|> bag.copies(of: "a")
// -> 0