AlgebraicJulia / Catlab.jl

A framework for applied category theory in the Julia language
https://www.algebraicjulia.org
MIT License
608 stars 58 forks source link

Monic constraint and `no_bind` kwarg for AttrVars in hom search #918

Closed kris-brown closed 3 months ago

kris-brown commented 3 months ago

Addresses https://github.com/AlgebraicJulia/Catlab.jl/issues/916 in addition to addressing addressing the fact that the monic constraint keyword effectively would ignore AttrType components of the homomorphisms, which had the effect of:

1.) Returning morphisms which were technically not monic, if there existed matches which bound AttrVars in the domain to concrete values in the codomain 2.) Erroneously erroring due to "free floating variables" - we do not need to error for free floating variables if there is a monic constraint, since there are a finite number of possible assignments for each domain AttrVar in this case.

By default, homomorphism search can bind AttrVars to concrete values, but this will not be possible if monic or no_bind kwargs are turned on (either wholesale with true or componentwise). In these cases, it is not a problem if the domain has free-floating AttrVars. This is accomplished by adding a bit of code at the very end of the hom-search: we look at all of the unbound variables (which necessarily are free-floating ones) and use Iterators.product to further iterate over all possible bindings of those variables to AttrVars in the codomain (if monic, then we further only look at AttrVars which have not yet been assigned to).