That&#x27;s funny. I was thinking isomorphism because you postulate an inverse, which homomorphisms don&#x27;t always have. But the identity doesn&#x27;t depend on f being invertible. You could just have a rule:<p>If f is a homomorphism with respect to r, then reduce(r, map(f, l)) = f(reduce(r, l)).<p>The rule can be proven without reference to an inverse for f so isn&#x27;t it enough to just add such a rewrite rule to your optimizer? (Now I&#x27;m not sure what the inversion trick accomplishes?).<p>&gt; Always curious to follow people doing compiler work; loop me in, yeah?<p>norstrulde.org and twitter.com&#x2F;ericbb<p>&gt; &quot;there might or might not be an algebra in which f acts as a homomorphism, and, even if there is, you may not have the transformations you need to determine it!&quot;<p>To my way of interpreting it, the algebra is determined by r, which is given. You might not know whether f is a homomorphism with respect to r and it&#x27;d be tricky to figure that out by inspecting the definitions for f and r but if you have a table built in advance that characterizes functions in relation to each other (incr is a homomorphism with respect to max, etc.), then you can drive your rewrite engine using that table... So I wouldn&#x27;t say that you want to use transformations to determine if f is a homomorphism but rather that you want to use the fact that f is a homomorphism to decide which transformations are applicable. Does that make sense?<p>Edit: I guess, more generally, you could have a relation with the form homomorphism(f:a-&gt;b, q:a-&gt;a-&gt;a, r:b-&gt;b-&gt;b) which justifies the transformation reduce(r, map(f, l)) -&gt; f(reduce(q, l)).