10000 Perform immut/{set, sparse_array} by FlyCloudC · Pull Request #2272 · moonbitlang/core · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Perform immut/{set, sparse_array} #2272

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 9 commits into from
Jul 1, 2025
Merged

Perform immut/{set, sparse_array} #2272

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
9 commits
Select commit Hold shift + click to select a range
3d82b75
removing redundant function signatures in doc
FlyCloudC Jun 14, 2025
8b03d30
refactor(sparse_array): remove `has` and simplify tests
FlyCloudC Jun 14, 2025
554e103
refactor(HAMT): using Path
FlyCloudC Jun 14, 2025
8d460c7
refactor(HAMT): using @list and remove single-element Leaf optimization
FlyCloudC Jun 14, 2025
fa7ae35
refactor(HAMT): separate representation of empty set
FlyCloudC Jun 14, 2025
418f34a
perf(HAMT): flatten nested Branch structure
FlyCloudC Jun 14, 2025
5123628
perf(HAMT): `union`, `difference`, `intersection`
FlyCloudC Jun 17, 2025
5ea93cc
fix(HAMT): duplicate execution of add operation
FlyCloudC Jun 25, 2025
63d30fc
docs(HAMT): for Path
FlyCloudC Jun 30, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
85 changes: 20 additions & 65 deletions immut/hashmap/HAMT.mbt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -376,30 +376,13 @@ pub fn[K : Eq + Hash, V] T::intersection(
self : T[K, V],
other : T[K, V]
) -> T[K, V] {
match (self, other) {
(_, Empty) => Empty
(Empty, _) => Empty
(Leaf(k, v), _) =>
match other.get(k) {
Some(_) => Leaf(k, v)
None => Empty
}
(_, Leaf(k, _)) =>
match self.get(k) {
Some(v) => Leaf(k, v)
None => Empty
}
(Branch(sa1), Branch(sa2)) =>
Branch(sa1.intersection(sa2, (m1, m2) => m1.intersection(m2)))
(_, _) =>
self
.iter()
.fold(init=Empty, (m, kv) => if other.get(kv.0) is Some(_) {
m.add(kv.0, kv.1)
} else {
m
})
}
self
.iter()
.fold(init=Empty, (m, kv) => if other.get(kv.0) is Some(_) {
m.add(kv.0, kv.1)
} else {
m
})
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This PR should only affect immut/hashset, is this accidentally introduced?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not accidental. Since the types of SparseArray::difference and SparseArray::intersection were changed

-fn[X] SparseArray::difference(Self[X], Self[X]) -> Self[X]
+fn[X] SparseArray::difference(Self[X], Self[X], (X, X) -> X?) -> Self[X]?

-fn[X] SparseArray::intersection(Self[X], Self[X], (X, X) -> X raise?) -> Self[X] raise?
+fn[X] SparseArray::intersection(Self[X], Self[X], (X, X) -> X? raise?) -> Self[X]? raise?

the corresponding calls in immut/hashmap were also affected.

}

///|
Expand All @@ -409,29 +392,12 @@ pub fn[K : Eq + Hash, V] T::intersection_with(
other : T[K, V],
f : (K, V, V) -> V raise?
) -> T[K, V] raise? {
match (self, other) {
(_, Empty) => Empty
(Empty, _) => Empty
(Leaf(k, v), _) =>
match other.get(k) {
Some(v2) => Leaf(k, f(k, v, v2))
None => Empty
}
(_, Leaf(k, v2)) =>
match self.get(k) {
Some(v1) => Leaf(k, f(k, v1, v2))
None => Empty
}
(Branch(sa1), Branch(sa2)) =>
Branch(sa1.intersection(sa2, (m1, m2) => m1.intersection_with(m2, f)))
(_, _) =>
self
.iter()
.fold(init=Empty, (m, kv) => match other.get(kv.0) {
Some(v2) => m.add(kv.0, f(kv.0, kv.1, v2))
None => m
})
}
self
.iter()
.fold(init=Empty, (m, kv) => match other.get(kv.0) {
Some(v2) => m.add(kv.0, f(kv.0, kv.1, v2))
None => m
})
}

///|
Expand All @@ -440,24 +406,13 @@ pub fn[K : Eq + Hash, V] T::difference(
self : T[K, V],
other : T[K, V]
) -> T[K, V] {
match (self, other) {
(Empty, _) => Empty
(_, Empty) => self
(Leaf(k, v), _) =>
match other.get(k) {
Some(_) => Empty
None => Leaf(k, v)
}
(Branch(sa1), Branch(sa2)) => Branch(sa1.difference(sa2))
(_, _) =>
self
.iter()
.fold(init=Empty, (m, kv) => if other.get(kv.0) is None {
m.add(kv.0, kv.1)
} else {
m
})
}
self
.iter()
.fold(init=Empty, (m, kv) => if other.get(kv.0) is None {
m.add(kv.0, kv.1)
} else {
m
})
}

///|
Expand Down
Loading
0