Jump to content

  • Log In with Google      Sign In   
  • Create Account

Name of a particular property


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Bacterius   Crossbones+   -  Reputation: 8866

Like
0Likes
Like

Posted 22 June 2013 - 04:01 AM

Hello,

in my library I'm working on, I have a few functions which take (among other parameters) a data buffer, with the property that calling such a function twice in succession, with two data buffers, is equivalent to calling it once with the ordered concatenation of both data buffers. In other words:

F("hello")
F(" ")
F("world")

Is strictly equivalent to:

F("hello world")

Is there a name for such a property? For instance a function such that F(F(x)) = F(x) is called idempotent. I'm asking because I'm tired of describing this property in such a long-winded manner in my documentation, and it would be nice if there was a word I could use to sum it all up efficiently.

 

Thanks!


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


Sponsor:

#2 Paradigm Shifter   Crossbones+   -  Reputation: 5372

Like
2Likes
Like

Posted 22 June 2013 - 04:12 AM

Linear?

 

f(x + y) = f(x) + f(y)

 

(although linearity also means f(a*x) = a * f(x)).


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#3 JD557   Members   -  Reputation: 163

Like
1Likes
Like

Posted 22 June 2013 - 04:34 AM

I'm not an expert on the topic, but this ressembles a lot the way IO is handled in haskell via monads. You might want to look into that.

 

Here's a really nice explanation and some more monad examples.



#4 Álvaro   Crossbones+   -  Reputation: 13311

Like
4Likes
Like

Posted 22 June 2013 - 04:43 AM

I don't know of a name, but I can make one up: "concatenation invariant". :)



#5 JD557   Members   -  Reputation: 163

Like
0Likes
Like

Posted 22 June 2013 - 05:11 AM

Linear?

 

f(x + y) = f(x) + f(y)

 

(although linearity also means f(a*x) = a * f(x)).

 

This seems ok to me

 

print("A"+"B")=print("A")+print("B")

print(5*"A")=print("A"+"A"+"A"+"A"+"A")+print("AAAAA")



#6 Bacterius   Crossbones+   -  Reputation: 8866

Like
0Likes
Like

Posted 22 June 2013 - 05:18 AM

Linear?

 

f(x + y) = f(x) + f(y)

 

(although linearity also means f(a*x) = a * f(x)).

 

That would be fine for a couple of them but many of them do not actually return an output of the same size as the input (or at all) so in those instances "linear" would be meaningless, unfortunately.

 


I don't know of a name, but I can make one up: "concatenation invariant".

 

I like it smile.png


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#7 Felix Ungman   Members   -  Reputation: 1032

Like
1Likes
Like

Posted 22 June 2013 - 05:23 AM

As you're dealing with data buffer, it seems that the function is some kind of stream writing operator.


openwar  - the real-time tactical war-game platform


#8 Khatharr   Crossbones+   -  Reputation: 3001

Like
0Likes
Like

Posted 25 June 2013 - 03:36 AM

I don't know of a name, but I can make one up: "concatenation invariant". smile.png


How about "inconcatviant"?
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#9 frob   Moderators   -  Reputation: 21281

Like
0Likes
Like

Posted 25 June 2013 - 10:23 AM


I have a few functions which take (among other parameters) a data buffer, with the property that calling such a function twice in succession, with two data buffers, is equivalent to calling it once with the ordered concatenation of both data buffers.

I don't think that is a very good idea.

 

When it comes to building a language, make it apply in ALL cases.  Something that applies in only SOME cases is usually a bug.

 

For example, your example

Print("Hello"); Print(" "); Print("World!);

might just happen to be functionally equivalent to Print("Hello World!");

 

But it is not universally true of all string functions.  It is very different from:

PrintLine("Hello"); PrintLine(" "); PrintLine("World!");

The result should be three distinct entries.  It would be functionally equivalent to Print("Hello\n \nWorld!\n");

 

Or consider:

ShowDialog("Hello"); ShowDialog(" "); ShowDialog("World!");

I expect three distinct dialog boxes, not one single dialog box with the strings concatenated.

 

 

 

It is one thing to allow adjacent string literals to be concatenated.  It is quite another thing to not call adjacent functions because their parameters happen to be the same type.


Check out my personal indie blog at bryanwagstaff.com.

#10 Álvaro   Crossbones+   -  Reputation: 13311

Like
0Likes
Like

Posted 25 June 2013 - 11:17 AM

 


I have a few functions which take (among other parameters) a data buffer, with the property that calling such a function twice in succession, with two data buffers, is equivalent to calling it once with the ordered concatenation of both data buffers.

I don't think that is a very good idea.

 

[...]

 

I don't understand your objection. Perhaps you misread something? He is not saying that this property is universal, only that he has several functions with that property and he wants to know of a short way to describe it. It sounds very reasonable to me...



#11 freeworld   Members   -  Reputation: 325

Like
1Likes
Like

Posted 25 June 2013 - 04:35 PM

How does the documentation for std::cin describe it?
[ dev journal ]
[ current projects' videos ]
[ Zolo Project ]
I'm not mean, I just like to get to the point.

#12 Bacterius   Crossbones+   -  Reputation: 8866

Like
0Likes
Like

Posted 25 June 2013 - 08:59 PM

Yes, I am not building a language. But some of my library's functions simply behave that way to allow for arbitrary amounts of data to be provided and at any rate, not limited by the amount of data that can be physically present on one invocation of the function (think about a network socket, for instance, you don't know how much data you are going to receive next, you could receive it all in one shot, or one byte each time you check, so you need a way to make it work the same regardless of how much you've got every time you poll the socket - there are other examples of course). Actually everything is quite consistent overall.

 

 

 

How does the documentation for std::cin describe it?

 

It doesn't really say anything, actually. The std::cout version says it "inserts" into the stream. I think the notion of stream might help me describe it, though.


Edited by Bacterius, 25 June 2013 - 09:08 PM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#13 Alpha_ProgDes   Crossbones+   -  Reputation: 4688

Like
0Likes
Like

Posted 25 June 2013 - 11:10 PM

Hello,

in my library I'm working on, I have a few functions which take (among other parameters) a data buffer, with the property that calling such a function twice in succession, with two data buffers, is equivalent to calling it once with the ordered concatenation of both data buffers. In other words:

F("hello")
F(" ")
F("world")

Is strictly equivalent to:

F("hello world")

Is there a name for such a property? For instance a function such that F(F(x)) = F(x) is called idempotent. I'm asking because I'm tired of describing this property in such a long-winded manner in my documentation, and it would be nice if there was a word I could use to sum it all up efficiently.

 

Thanks!

 

 

I don't know of a name, but I can make one up: "concatenation invariant". smile.png

 

Buffered concatenation........?


Beginner in Game Development? Read here.
 
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
 
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts Posted Image
 
Spoiler

#14 TheChubu   Crossbones+   -  Reputation: 4349

Like
0Likes
Like

Posted 26 June 2013 - 08:35 PM

Buffered invariant concatenation!


"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS