4 ms·

List Homomorphisms and Parallelism

83 points by sidcool 5y ago

tsimionescu 5y ago
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.
- lasfter 5y ago
  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.
- pwdisswordfish8 5y ago
  > 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?
  - tsimionescu 5y ago
    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?
- Athas 5y ago
  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.
- jiehong 5y ago
  You can always look them up to check: - https://en.wiktionary.org/wiki/%E2%8A%97 https://en.wiktionary.org/wiki/%E2%8A%97 - https://en.wiktionary.org/wiki/%E2%8A%99 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.
  - taejo 5y ago
    These operations are meant to be essentially an arbitrary binary operation, not the tensor product.
- dgb23 5y ago
  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.
pwdisswordfish8 5y ago
> 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
derriz 5y ago
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?
- Athas 5y ago
  You're right! I fat-fingered that example and nobody noticed (or pointed it out) before you. Fixed!
  - thargor90 5y ago
    also mssp ([3,-1,1] ++ [1,-1,3]) = 6, right?
    - Athas 5y ago
      Damn, messed up again. I guess I should run more code and write less text.
      - jkhdigital 5y ago
        > I guess I should run more code and write less text. Wisdom
deleted 5y ago
[deleted]
contravariant 5y ago
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.
- deleted 5y ago
  [deleted]
deleted 5y ago
[deleted]
shadowgovt 5y ago
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.
lma21 5y ago
> Now define a function f that morally computes such a tuple for single element subarrays: what does `morally computes` means?

83 points by sidcool 5y ago

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.

lasfter 5y ago
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.
pwdisswordfish8 5y ago
> 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?
- tsimionescu 5y ago
  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?
Athas 5y ago
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.
jiehong 5y ago
You can always look them up to check: - https://en.wiktionary.org/wiki/%E2%8A%97 https://en.wiktionary.org/wiki/%E2%8A%97 - https://en.wiktionary.org/wiki/%E2%8A%99 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.
- taejo 5y ago
  These operations are meant to be essentially an arbitrary binary operation, not the tensor product.
dgb23 5y ago
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.

pwdisswordfish8 5y ago

> 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

derriz 5y ago

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?

Athas 5y ago
You're right! I fat-fingered that example and nobody noticed (or pointed it out) before you. Fixed!
- thargor90 5y ago
  also mssp ([3,-1,1] ++ [1,-1,3]) = 6, right?
  - Athas 5y ago
    Damn, messed up again. I guess I should run more code and write less text.
    - jkhdigital 5y ago
      > I guess I should run more code and write less text. Wisdom

deleted 5y ago

[deleted]

contravariant 5y ago

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.

deleted 5y ago
[deleted]

deleted 5y ago

[deleted]

shadowgovt 5y ago

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.

lma21 5y ago

> Now define a function f that morally computes such a tuple for single element subarrays: what does `morally computes` means?