Re: a logarithmic-time alternative to summed-area tables for reducing arbitrary semigroup operations over arbitrary ranges (a generalization of RMQ segment trees)

> Abstract algebra is the study of what you can deduce from minimal sets
> of axioms about some set of things and operations on them.

Speaking of which, I have a data structure, useful for 3D  
calculations, which lies somewhere between bags and lists.  If order  
mattered, it would be simply a list.  If order did not matter, it  
would be simply a bag.  However, what matters is the parity of the  
order of the elements, so it's roughly a "bag with a parity flag".   
Does anyone here know what this is really called?  (in either math or  
CS?)

-Dave

> But what do you do if you're interested in an operation that doesn't
> have a left inverse?  For example, the "minimum" operation (or in
> general the meet operation of a meet-semilattice) can't have inverses
> of elements, because it's idempotent, so you can't compute it with a
> sum table.

This gets a little more subtle.  For instance, we normally think of  
"and" and "or" as being "min" and "max" over booleans (and so "all"  
and "exists" are simply these operations fmap'ped over an entire  
collection).  However, it's possible to keep a sum table of integers  
(anti-idempotent) which enables us to answer "all" or  
"exists" (idempotent) range queries via a simple function to booleans.

-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss