List Homomorphisms and Parallelism | Hacker News Reader

List Homomorphisms and Parallelism

sigkill.dk

83 pointssidcool19 comments

> 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>

Bird's paper (linked at the bottom of the article, 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 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?"

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 (+).

There are, broadly speaking, two reasons to study math in detail.

The first is because it's interesting by itself. And it is! The patterns and the patterns they build can be their own reward.

The second is because fundamental mathematical theorems are incredibly useful for practical engineering. Because list homomorphisms have the mathematical properties they do, we know that if we operate upon data using list homomorphisms, we can (mechanically) MapReduce that data. That knowledge makes practically unsolvable problems solvable.

I have asked this in the past, but how do people actually read formulae and text using non-standard operators like this article? When you encounter the text `a ⊗ b = a ⊙ f b` how do you read this in your mind?

In these simple examples it's easy enough to ignore, but in more realistic code that I've seen it's impossible for me to follow until I invent arbitrary names for these operators.

I would say 'dot' and 'cross' etc.

But I think something else entirely. Usually I have a little picture in my head of what I feel the operator does or what it's properties are.

In this particular case I see/imagine a little purple bridge atop the operands that glows slightly and connects them.

I'd say use whatever feels natural to you: names, colors, shapes, smells(?), other feelings... Now I really wonder if there are people who read symbolic expressions by associating smells or taste.

Like you mention, I invent names, though not quite arbitrarily. '⊙' looks like an 'oh-dot' to me, and '⊗' is just 'cross'.

Algebra classes are full of such operators, and usually my instructors were kind enough to give them names during lectures.

I read them by their LaTeX names, which are "ocross" and "odot". Sometimes I will just read them as "cross" or "dot", or even "add" and "times" when applicable.

> how do you read this in your mind?

By looking at the screen. Do you have to ‘read’ a painting to be able to perceive it?

Depends on what I want to do with it. For most paintings, I only intend to perceive the aesthetics of color, and then I don't need to read it. When I want to discuss some paintings though, it does help to be able to describe them in words - either for colors or for particular features.

And then, if a painting is actually a 'riddle' that is intended to be taken as a message, then I really do want to decipher it in words. This happens in particular with religious icons (at least in Eastern Orthodoxy).

I feel we'll soon get into a discussion of whether reasoning is necessarily language-based or not, which I don't want to go into. So instead I will ask - how do you discuss that formula with someone else? How do you call that operator, or others like `<=>` when you're verbally discussing the algorithm/code with someone else?

You can always look them up to check:

- https://en.wiktionary.org/wiki/%E2%8A%97

- https://en.wiktionary.org/wiki/%E2%8A%99

So I'd read it as "the tensor product of a and b equals the dot product of a and b times b", something like that.

Or just "a times b = a prod f b" if I see this often.

These operations are meant to be essentially an arbitrary binary operation, not the tensor product.

The piece contains examples of the maximum segment sum, such as “mssp [3,-1,2] = 3”. Am I missing something? Shouldn’t the answer be 4?

You're right! I fat-fingered that example and nobody noticed (or pointed it out) before you. Fixed!

also mssp ([3,-1,1] ++ [1,-1,3]) = 6, right?

Damn, messed up again. I guess I should run more code and write less text.

> I guess I should run more code and write less text.

Wisdom

The meat of this is definitely the third homomorphism theorem. I worried that it was completely non-constructive but according to the linked paper you can define the corresponding associative operation as follows:

    t * u = h (g t ++ g u)

where g is a pseudo-inverse of h such that hgh = h. The left and right folding of the function is used to prove associativity. Sure finding a pseudo inverse isn't always easy but it's at least somewhat doable.

> Now define a function f that morally computes such a tuple for single element subarrays:

what does `morally computes` means?

Reply on news.ycombinator.com