5 ms·

Pretentious or not, the term is used erroneously here. Recursive data structures and recursive algorithms are, quite plainly, not isomorphic. They are not two

Pretentious or not, the term is used erroneously here. Recursive data structures and recursive algorithms are, quite plainly, not isomorphic. They are not two equivalent representations of the same thing. Something that is isomorphic to a recursive function that works on a quadtree would be an imperative function that works on a quadtree with identical functionality. tl;dr: I think the author meant "synergistic".

braythwayt 10y ago
I don’t know that an algorithm and a data structure have to be equivalent representations of the same thing to be isomorphic. In the case of the algorithm, is it the code that must be equivalent? Or the runtime behaviour? The runtime behaviour of the ‘whirling regions’ algorithm clearly is not an equivalent representation of the two-dimensional array representation of an image. However, the runtime behaviour of the quadtree algorithm exactly matches the quadtree data structure. This is my proposition: That what matters is whether the algorithmic behaviour is equivalent. I would say the same thing about `binrec` matching a binary tree. ...Or at least, I would have, up until today. I am open to being disabused of this notion.
- gohrt 10y ago
  Isomorphic means "have the same shape". It means that there is some structural property that the two objects have in common. The more interesting/complex the property is (and the more superficially different the two objects look), the more defensible the use of the word is.
stan_rogers 10y ago
"Isomorphic" literally means "of the same shape".
- mypalmike 10y ago
  Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code. The code is treelike, but that's because all code is treelike(1). As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary graph. It is still treelike. (1) My old Atari 800 BASIC programs notwithstanding.
  - braythwayt 10y ago
    I was speaking to the relationship between the code's runtime behaviour and the structure of the data. When I say the word "algorithm," am I talking about the way the code is noted in a particular language? Or the steps one takes to perform the operation?
    - groovy2shoes 10y ago
      In some other languages, even the notation itself has obvious parallels between data definition and process definition. Consider a list and `map` in Standard ML: datatype 'a list = Nil | Cons of 'a * 'a list; val rec map : ('a -> 'b) -> 'a list -> 'b list = fn f => fn xs => case xs of Nil => Nil | Cons(x, xs') => Cons(f x, map f xs'); The case analysis of a list is obviously isomorphic to the definition of a list, in the sense that the data and the process have the same shape: a list is a `Nil` or a `Cons(item, more list)`, while a function that traverses a list checks if a list is `Nil` and does something, otherwise it's a `Cons(...)` and it does something else. The linear recursive nature of the list definition lends itself naturally to algorithms which are similarly linearly recursive. (`map` itself can be said to create homomorphisms, but that's beside the point here; I use this particular example only because it happens to be the simplest non-trivial one I could think of). Okay, so perhaps this isn't quite what "isomorphic" means in category theory, or topology, or graph theory, or set theory, or what have you. Even in mathematics, though, it's obvious that terminology gets borrowed between the branches when there are concepts that are somehow related. Why should programming be any different? So, I argue that it's not wrong to use "isomorphic" in the sense that you have—in fact, it's a term that I've seen used in the same sense on numerous occasions, and something that I think experienced programmers have internalized. In this case, the structure of the data, that is, a linearly recursive collection of elements, precisely matches the structure of the process, that is, a linearly recursive traversal of elements. Whether or not there actually exists an isomorphism between the two is irrelevant to the notion that the two are isomorphic, that is, they have "equal shapes". I think a habit of thinking of words in an etymological way leads naturally to borrowing those words for similar concepts. This is neither the first time such a thing has happened, nor will it be the last. To knowledgeable parties, your use of the word communicated a characteristic of your program in a succinct way that you continued to illustrate—that the shape of the quad tree data structure reflects the shape of the algorithms used to process instances of said structure. One might say that the various meanings of the term "isomorphic" are... isomorphic ¬_¬
greydius 10y ago
> They are not two equivalent representations of the same thing. Algorithms encoded as a program end up as an abstract syntax tree in the compiler. Algorithm -> Data structure. The compiler then turns that ast into some other representation (e.g. machine instructions, JavaScript) which is again the algorithm. Data structure -> algorithm. Bijection identified.
- Bahamut 10y ago
  An isomorphism is more than a bijection, unless it is between sets and the category is the one of all functions from one set to another. Isomorphism is about preserving relations as well. For example, consider the ring of integers and the field of rational numbers. One can construct a bijection between one to the other (they both have the same cardinality as the natural numbers), but they are significantly different constructs. The bijection would not be able to preserve the operations - in fact, the rational numbers as a ring is significantly different, and unless one wants to use information about the cardinality, a bijection between the two is otherwise worthless.
  - greydius 10y ago
    Correct. A bijection implies isomorphism in the category of sets. Thus an isomorphism exists. I suppose we need to convince ourselves that algorithms and abstract syntax trees do indeed form sets. (Exclude such things as "the algorithm that computes the set of all algorithms", etc.)
    - Bahamut 10y ago
      But that is typically not how the word is used because to substitute bijection with isomorphism, it would only make sense when talking about cardinality - that is not how you used it.
chronial 10y ago
I am following the mathmatical definiton of isomorphism: The two sets are Quadtree instances and calls of `myself`. The map from calls to instances is "instance that was given as argument". This map is obviously bijective. The structure that is preserved is "is a child of". QED :)

braythwayt 10y ago

I don’t know that an algorithm and a data structure have to be equivalent representations of the same thing to be isomorphic. In the case of the algorithm, is it the code that must be equivalent? Or the runtime behaviour? The runtime behaviour of the ‘whirling regions’ algorithm clearly is not an equivalent representation of the two-dimensional array representation of an image. However, the runtime behaviour of the quadtree algorithm exactly matches the quadtree data structure. This is my proposition: That what matters is whether the algorithmic behaviour is equivalent. I would say the same thing about `binrec` matching a binary tree. ...Or at least, I would have, up until today. I am open to being disabused of this notion.

gohrt 10y ago
Isomorphic means "have the same shape". It means that there is some structural property that the two objects have in common. The more interesting/complex the property is (and the more superficially different the two objects look), the more defensible the use of the word is.

stan_rogers 10y ago

"Isomorphic" literally means "of the same shape".

mypalmike 10y ago
Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code. The code is treelike, but that's because all code is treelike(1). As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary graph. It is still treelike. (1) My old Atari 800 BASIC programs notwithstanding.
- braythwayt 10y ago
  I was speaking to the relationship between the code's runtime behaviour and the structure of the data. When I say the word "algorithm," am I talking about the way the code is noted in a particular language? Or the steps one takes to perform the operation?
  - groovy2shoes 10y ago
    In some other languages, even the notation itself has obvious parallels between data definition and process definition. Consider a list and `map` in Standard ML: datatype 'a list = Nil | Cons of 'a * 'a list; val rec map : ('a -> 'b) -> 'a list -> 'b list = fn f => fn xs => case xs of Nil => Nil | Cons(x, xs') => Cons(f x, map f xs'); The case analysis of a list is obviously isomorphic to the definition of a list, in the sense that the data and the process have the same shape: a list is a `Nil` or a `Cons(item, more list)`, while a function that traverses a list checks if a list is `Nil` and does something, otherwise it's a `Cons(...)` and it does something else. The linear recursive nature of the list definition lends itself naturally to algorithms which are similarly linearly recursive. (`map` itself can be said to create homomorphisms, but that's beside the point here; I use this particular example only because it happens to be the simplest non-trivial one I could think of). Okay, so perhaps this isn't quite what "isomorphic" means in category theory, or topology, or graph theory, or set theory, or what have you. Even in mathematics, though, it's obvious that terminology gets borrowed between the branches when there are concepts that are somehow related. Why should programming be any different? So, I argue that it's not wrong to use "isomorphic" in the sense that you have—in fact, it's a term that I've seen used in the same sense on numerous occasions, and something that I think experienced programmers have internalized. In this case, the structure of the data, that is, a linearly recursive collection of elements, precisely matches the structure of the process, that is, a linearly recursive traversal of elements. Whether or not there actually exists an isomorphism between the two is irrelevant to the notion that the two are isomorphic, that is, they have "equal shapes". I think a habit of thinking of words in an etymological way leads naturally to borrowing those words for similar concepts. This is neither the first time such a thing has happened, nor will it be the last. To knowledgeable parties, your use of the word communicated a characteristic of your program in a succinct way that you continued to illustrate—that the shape of the quad tree data structure reflects the shape of the algorithms used to process instances of said structure. One might say that the various meanings of the term "isomorphic" are... isomorphic ¬_¬

greydius 10y ago

> They are not two equivalent representations of the same thing. Algorithms encoded as a program end up as an abstract syntax tree in the compiler. Algorithm -> Data structure. The compiler then turns that ast into some other representation (e.g. machine instructions, JavaScript) which is again the algorithm. Data structure -> algorithm. Bijection identified.

Bahamut 10y ago
An isomorphism is more than a bijection, unless it is between sets and the category is the one of all functions from one set to another. Isomorphism is about preserving relations as well. For example, consider the ring of integers and the field of rational numbers. One can construct a bijection between one to the other (they both have the same cardinality as the natural numbers), but they are significantly different constructs. The bijection would not be able to preserve the operations - in fact, the rational numbers as a ring is significantly different, and unless one wants to use information about the cardinality, a bijection between the two is otherwise worthless.
- greydius 10y ago
  Correct. A bijection implies isomorphism in the category of sets. Thus an isomorphism exists. I suppose we need to convince ourselves that algorithms and abstract syntax trees do indeed form sets. (Exclude such things as "the algorithm that computes the set of all algorithms", etc.)
  - Bahamut 10y ago
    But that is typically not how the word is used because to substitute bijection with isomorphism, it would only make sense when talking about cardinality - that is not how you used it.

chronial 10y ago

I am following the mathmatical definiton of isomorphism: The two sets are Quadtree instances and calls of `myself`. The map from calls to instances is "instance that was given as argument". This map is obviously bijective. The structure that is preserved is "is a child of". QED :)