search

typelevel / algebra

Experimental project to lay out basic algebra type classes
https://typelevel.org/algebra/
Other
378 stars 69 forks source link

Add GenBool instance for Map[K, V: GenBool]. #126

Closed TomasMikula closed 7 years ago

johnynek commented 8 years ago

I realize we didn't add MapBoundedSemilattice when we have Semilattice which we could.

Also, there are many similar constructions related to Option[T] which is like a Map[Unit, T].

TomasMikula commented 8 years ago

I will rewrite the expressions to invoke iterator early. Now I'm thinking, if the two maps differ in size by 3 orders of magnitude, it might be better to apply the small number of individual updates on the bigger map.

TomasMikula commented 8 years ago

Yeah, I realized there could be interesting structures for Map weaker than GenBool.

TomasMikula commented 8 years ago

I don't know how immutable Map is implemented, but if I assume that updating a single key costs log n, and if the other (smaller) map has size m, then if

m log n < n + m

it is more efficient to update the big map.

johnynek commented 8 years ago

Immutable map is a HashTrie, so it is ~ log_32 n cost to update a map of size n.

johnynek commented 8 years ago

@TomasMikula you might want to take a look at: https://github.com/non/algebra/blob/a32f76aba93245b95972b4b4bb80f29b0621c9ba/std/src/main/scala/algebra/std/Util.scala#L154 the addMap/subtractMap methods may be able to be used in these cases.

TomasMikula commented 8 years ago

Yeah, addMap could be used to implement or right away. subtractMap could possibly be used to implement without, passing constant function returning zero as negate (because here, unlike in rings, 0\a = 0). The problem is that if in x\y, x is much smaller, x\y can be fast, because we don't have to introduce 0s for all the elements of y (whereas in subtractMap you have to introduce the inverses).

johnynek commented 7 years ago

i think we need the TotalMap[K, V] to handle this. @TomasMikula I wonder if your https://github.com/TomasMikula/hasheq could be the right place to add such a type?

TomasMikula commented 7 years ago

i think we need the TotalMap[K, V] to handle this.

I'm afraid you're right.

I wonder if your https://github.com/TomasMikula/hasheq could be the right place to add such a type?

Indeed, it would make sense to add TotalMap to hasheq. Then have a third module that provides algebra instances for hasheq structures.

non commented 7 years ago

That sounds like a great plan to me!

TomasMikula commented 7 years ago

See