4 ms·

> In principle h need not be defined for empty inputs It actually need. Since the definition given earlier requires that h (x ++ y) = h x ⊙ h y for any x and

> In principle h need not be defined for empty inputs It actually need. Since the definition given earlier requires that h (x ++ y) = h x ⊙ h y for any x and y, in particular we can always take x or y (or both) to be empty. For the definition to make sense, h of an empty list must be defined. Otherwise one get a non-empty list homomophism. The above nicely demonstrates the pitfalls of using definitions based on binary operations instead of (finitary-)variadic operations: <https://ncatlab.org/nlab/show/biased+definition https://ncatlab.org/nlab/show/biased+definition>

shadowgovt 5y ago
Bird's paper (linked at the bottom of the article, https://www.cs.ox.ac.uk/files/3378/PRG56.pdf https://www.cs.ox.ac.uk/files/3378/PRG56.pdf) addresses this definitionally. Page 9: "If h is not defined on the empty list, then (+) is not required to possess an identity element and the above equation is asserted for non-empty lists only." This distinction rarely matters (except maybe if you're building a MapReduce engine, you might need to add a functionDefinedOnEmptyLists flag and special-case when the flag is false to assure that none of your nodes try to handle an empty-list input). Whether you want to allow for nullary operations to exist depends heavily on what you're doing. The approach suggested at https://ncatlab.org/nlab/show/biased+definition https://ncatlab.org/nlab/show/biased+definition has the consequence that the introduced nullary can "eat" the result... i.e. if we address h({}) being undefined by just making it infinity, and our (+) operator is just sum, then we end up with the result of the computation being infinity. Is that okay, or did we just waste a lot of processing time to reach the conclusion "Hey, somewhere we tried to operate on an empty list, hope you wanted any partial result drowned in an infinite sea?"
- pwdisswordfish8 5y ago
  If h is defined to equal infinity on all single-element lists, then it will also absorb the result. If you pick definitions that don’t make sense, it’s your problem. Never mind setting h to ∞ at the empty list makes it no longer a homomorphism with respect to (+).
- deleted 5y ago
  [deleted]

shadowgovt 5y ago

Bird's paper (linked at the bottom of the article, https://www.cs.ox.ac.uk/files/3378/PRG56.pdf https://www.cs.ox.ac.uk/files/3378/PRG56.pdf) addresses this definitionally. Page 9: "If h is not defined on the empty list, then (+) is not required to possess an identity element and the above equation is asserted for non-empty lists only." This distinction rarely matters (except maybe if you're building a MapReduce engine, you might need to add a functionDefinedOnEmptyLists flag and special-case when the flag is false to assure that none of your nodes try to handle an empty-list input). Whether you want to allow for nullary operations to exist depends heavily on what you're doing. The approach suggested at https://ncatlab.org/nlab/show/biased+definition https://ncatlab.org/nlab/show/biased+definition has the consequence that the introduced nullary can "eat" the result... i.e. if we address h({}) being undefined by just making it infinity, and our (+) operator is just sum, then we end up with the result of the computation being infinity. Is that okay, or did we just waste a lot of processing time to reach the conclusion "Hey, somewhere we tried to operate on an empty list, hope you wanted any partial result drowned in an infinite sea?"

pwdisswordfish8 5y ago
If h is defined to equal infinity on all single-element lists, then it will also absorb the result. If you pick definitions that don’t make sense, it’s your problem. Never mind setting h to ∞ at the empty list makes it no longer a homomorphism with respect to (+).
deleted 5y ago
[deleted]