World's most popular travel blog for travel bloggers.

[Answers] On the fly manipulation of operators

, , No Comments
Problem Detail: 

Assume that you are writing sorting algorithms, and that you want the ability to select between ascending and descending order. The only change required to do this for comparison sorts is to use the inverse of the comparison operator (for example: > becomes <). This begs the question, why is it not possible to change operators on the fly?

A simple bubble sort for ascending order:

private T[] BubbleAscending(T[] sortMe)     {          bool stopMe = true;         int stopRecurse = sortMe.Length - 1;         int optimizeMe = stopRecurse;          for (int i = 0; i < stopRecurse && stopMe; i++)         {             stopMe = false;              for (int j = 0; j < optimizeMe; j++)             {                 if (sortMe[j].CompareTo(sortMe[j + 1]) > 0)                 {                     Swap(sortMe, j, j + 1);                     stopMe = true;                 }             }              optimizeMe--;         }          return sortMe;     } 

Now we have to have a Bubble sort for descending order:

private T[] BubbleDescending(T[] sortMe)     {          bool stopMe = true;         int stopRecurse = sortMe.Length - 1;         int optimizeMe = stopRecurse;          for (int i = 0; i < stopRecurse && stopMe; i++)         {             stopMe = false;              for (int j = 0; j < optimizeMe; j++)             {                 if (sortMe[j].CompareTo(sortMe[j + 1]) < 0)                 {                     Swap(sortMe, j, j + 1);                     stopMe = true;                 }             }              optimizeMe--;         }          return sortMe;     } 

Now we have to have some logic to allow the user to easily select between them:

public T[] BubbleSort(T[] sortMe, bool descending)     {         if (!descending)             return BubbleAscending(CopyArray(sortMe));          else             return BubbleDescending(CopyArray(sortMe));     } 

Wouldn't it be much simpler if we could do this?

public T[] BubbleSort(T[] sortMe, bool descending)     {         if (!descending)             operator comparison = >;          else if (descending)             operator comparison = <;          bool stopMe = true;         int stopRecurse = sortMe.Length - 1;         int optimizeMe = stopRecurse;          for (int i = 0; i < stopRecurse && stopMe; i++)         {             stopMe = false;              for (int j = 0; j < optimizeMe; j++)             {                 if (sortMe[j].CompareTo(sortMe[j + 1]) comparison 0)                 {                     Swap(sortMe, j, j + 1);                     stopMe = true;                 }             }              optimizeMe--;         }          return sortMe;     } 
Asked By : superstewie

Answered By : jmite

Welcome to the wonderful world of functional programming and the lambda calculus!

The answer is, there is no reason that you can't do this, and most sufficiently modern programming language (and some ancient ones i.e. LISP) will let you do this.

In a language with first-class functions, functions are data. You can treat them as variables, pass them as parameters, define them as lambda expressions (i.e. a nameless function). So in most languages, you can do something like this:

if (descending)   comparison = lambda x y -> x < y else    comparison = lambda x y -> x > y 

The lambda is just a way of saying "comparison a function which takes two arguments and returns the value after the ->".

Treating functions as data is an idea as old as computer science itself: lambda calculus was developed by Alan Turing's supervisor, Alonzo Church, in the 1930s.

Not being able to do this is a restriction of C and Java (although new versions are introducing lambdas), and a few other languages.

What you've shown is probably not possible because it's hard to parse (most parsers rely on the fact that < and > are special characters), but if you treat comparison as a normal function instead of an infix operator, and use a language that allows for higher-order functions, you can indeed do this, and in many cases it is preferable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59521

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback