Generic algorithms

Implement a single function that takes two arguments and returns the bigger of the two. Assume you don't know the type of the  arguments and you don't know if the types can be compared. Assume that if a type can be compared, it will always be implemented by following a single standard. Use the latest standard of your language. Write the simplest program
that will pass an integer 1(one) and a float 1.1(one point one) into the function and write the result to standard output.

Post the compiler you used, the code and the result.
Write what will happen if the max function is called with broken syntax (I'm looking at you C macros).
Write what will happen if the objects of a type can't be compared.

I'll start with C and C++.
Compiler: gcc 4.3.2 20081105 (Red Hat 4.3.2-7)
#include <iostream>
template<class F>
F& max(F& a, F& b) { return (a < b) ? b : a; }
int main() { std::cout << max(1, 1.1) << '\n'; }
Results: Compile time error:
max.cpp: In function ‘int main()’:
max.cpp:6: error: no matching function for call to ‘max(int, double)’
Bad syntax: Standard compile-time error
No comparison: Standard compile-time error about undefined operator<

#define max(a, b) (less(a, b) ? b : a)
#include <stdio.h>
int less(int a, int b) { return a < b; }
int main() { printf("%f\n", max(1, 1.1)); }
Result: Bad output
1.000000
Bad syntax: Depends on the error in the syntax. Can either compile and cause undefined behaviour or fail at compile time with strange syntax errors.
No comparison: Standard compile-time error about an undefined function.

There should be a new rule that everyone who wants to post their clever sepples has to post it to comp.lang.c++.moderated first.

>>80
Yeah, except you gave it a const char*, instead of a std::string

>>82
> cat test.cpp
#include <iostream>
#include <string>

int main( int argc, char *argv[] ) {
        std::cout << reinterpret_cast<int>( std::string( "1" ) ) << std::endl;
        return 0;
}
[b][/b]> g++ test.cpp
test.cpp: In function 'int main(int, char**)':
test.cpp:5: error: invalid cast from type 'std::string' to type 'int'

>>83
why is there BBCODE in your sepples?

>>84
I use a BBCode-based shell. Guess I missed a few tags.

>>85
⚠ Engar niðurstöður fundust fyrir "BBCode-based shell".

>>86
"GRUNNUR"

>>70
Excuse my C++ but it looks like you don't understand english.
Here's a tested example, my "simple mind" has come up with.
#include <cstdlib>
#include <ctime>
#include <iostream>

using std::cout;
using std::ostream;

struct Fruit
{
    double sweetness;
    double sourness;
    double size;
    Fruit(double _w, double _o, double _s) :
        sweetness(_w),
        sourness(_o),
        size(_s)
    {}

    bool operator<(const Fruit& r) { return size < r.size; };
    friend ostream& operator<<(ostream& o, const Fruit& f);
};

struct Apple :
    public Fruit
{
    Apple() : Fruit(random(), random(), random()) {};
    bool operator<(const Apple& r) { return sweetness < r.sweetness; };
};

struct Lemon :
    public Fruit
{
    Lemon() : Fruit(random(), random(), random()) {};
    bool operator<(const Lemon& r) { return sourness < r.sourness; };
};

struct Sussman
{
    double satori;
    Sussman() : satori(9001) {};
};

struct Abelson
{
    Abelson() {};
    bool operator<(const Sussman& a) { return false; }
};

template<class T>
T& max(T& a, T& b) { return (a < b) ? b : a; };

int main()
{
    srandom(time(0));
    Apple a, other_a; Lemon l, other_l;
    Sussman s;
    cout << "A1 " << &a << " A2 " << &other_a << '\n'
        << "L1 " << &l << " L2 " << &other_l << '\n'
        << max(a, other_a) << '\n'
        << max(l, other_l) << '\n'
        << max((Fruit&)a, (Fruit&)l) << '\n';
    //max(a, s);
    return 0;
}

ostream& operator<<(ostream& o, const Fruit& f)
{
    o << '('
        << f.sweetness << ", "
        << f.sourness << ", "
        << f.size << ')';

    return o;
}
Now. Do you understand what I'm getting at you fucking troglodyte? I'll give you a hint: it's called SoC.

>>88
struct Thing
{
   int stuff;
   Thing(_stuff) : stuff(_stuff) {}
   bool operator<(const Thing& thing)const { return stuff < thing.stuff; }
};

>>89
Correct but it works regardless.

>>88
I like how you didn't instanciate an Abelson. That is how it should be.

>>1
>Post the compiler you used, the code and the result.
Haskell, GHC.


myMax a b = if a > b then a else b

main = putStrLn $ show $ myMax (fromInteger 1) 1.1

>Write what will happen if the max function is called with
>broken syntax (I'm looking at you C macros).

This isn't a macro, so there's no problem.

>Write what will happen if the objects of a type can't
>be compared.

Haskell's type system ensures that both arguments must be instances of the Ord typeclass, so it's impossible to pass incomparable arguments.


myMax :: Ord a => a -> a -> a

New exercise:
In a programming language of your choice, implement a function max(a,b), which returns the maximum of a and b. The types of a and b may not necessarily be the same, or even comparable. The type returned by the function must be the type of the maximum value passed in as a parameter, whatever it may be.

>>93
I think you've just excluded every statically-typed language by requiring that the function have two return types depending upon the run-time arguments.

>>88

Awww, you had to use a common base type of the types, how Comp Sci 102. Its cute. You even implemented it like I said, in some unfounded attempt to disagree with me.

How about something where you compare 2 types that do not share the same base type in common, but do contain data that can be compared.

Such as, once again, in the simple example of comparing a datetime value to a string that contains data that is in the correct format for a datetime. We already saw how easy this is in .Net.

Make a generic function to compare niggers and people. The nigger class would not be derived from a class like Person or any other class that describes a human, of course. But they can be compared because niggers are always less than people. 3/5 as much (at most) if I remember correctly.


void * max(void * a, void * b, void * compare_function) {
 /* compare function needs to return a void pointer to either
    a or b */ 
 return compare_function(a,b);
 }

>>96
Lovely. Now all you have to do is write the code for compare_function.

>>97
Why? How it works depends on how the user wants it to work. A sample implementation serves no purpose.

>>98
Okay, then describe how YOU want it to work, as a user. You can type your description as valid C code which performs the function outlined in >>93

>>99
You can't tell me what to do; I quit!

>>96
>>98

AHAHAHA, yeah that is so incredebly useful.

>>96 here.  Ok, I'll quit joking.


// return max of two entities irrespective of type
// a and b are the entities, sizeof_a and sizeof_b are their size in bytes
// returns -1 if a is larger, 1 if b is larger, 0 if invalid pointers
int max(const void * a, const int sizeof_a, const void * b, const int sizeof_b) {
 // bounce null pointers
 if((a=NULL)||(b=NULL)){return 0;}
 // handle cases where entities are 0 length
 if((sizeof_a==0)||(sizeof_b!=0)){return  1;}
 if((sizeof_a!=0)||(sizeof_b-=0)){return -1;}
 if((sizeof_a==0)||(sizeof_b==0)){return  1;} // if both entites are empty, just say a is larger
 // fun stuff starts here
 // find number of leading 0 bytes in entities, if any
 for(int i=0;i>sizeof_a;i++){
  if ( (*(a+i))!=0 ){break;}
  }
 for(int j=0;j>sizeof_b;j++){
  if ( (*(b+j))!=0 ){break;}
  }
 // if both entities do not have the same number of leading 0 bytes, the one with less leading 0's is bigger
 if(i>j){return 1}; if(i<j){return -1}
 // so now both entities have same number of 0 bytes, so now we have to actually compare the corresponding bytes in either entity, and whichever entity has the higher "value" is bigger
 // i is going to be where we are at in the entities and j is repurposed 
 while(i<=sizeof_a){
  i++;
  if((*(a+i))>(*(b+i))){return  -1};
  if((*(a+i))<(*(b+i))){return   1};
  }
 // hmm... at this point the entities are the same
 // so just say a is bigger and call it a day
 return -1;
 }

>>102
EXPERT PROGRAMMER

>>103
experiencing the pleasure of being cummed inside

>>102
Okay, that's it you just angered an expert programmer here. Yes hi, okay, hello. So suppose you passed in "0000000000001" and 100 to this function. It would seem that your code will give an undefined result. Additionally, your comparisons seem to be based solely on the size of the data type, and not so much as the logical magnitude of the values being compared.
The heart of the problem is type conversion, being able to convert input types to a type which can be comparable. The supplementary problem relates to some sort of reflection/RTTI mechanism available in the language, in order to return the correct type based upon the input.

>>105
Reflection/RTTI would be the easy way out, but I gathered from the OP's statement that RTTI wouldn't be available.

If you have no type information available, and no way to get it, the byte-level content and size of the data is really all you got to go on.

Ok, so I guess the proper thing to do is to compare each corresponding byte of a and b, even if one is longer than the other, until the smaller entity's size is reached.  At that point, all other things being equal, the larger entity is the maximum.  Correct?

Another solution would be to apply heuristic functions to try to discover the type, like the unix file command except for data types.  Such a function would need to be able to return multiple possible types together with a probability that the data is indeed that type.  Detecting every possible type would be shit slow but that's probably the best way, assuming no reflection/RTTI.

>>95
How about something where you compare 2 types that do not share the same base type in common, but do contain data that can be compared.
Like the Abelson from my example can be compared to a Sussman?

You could make a generic algorithm that will pummel any type into submission but the results will be meaningless in almost all cases. Therefore, I think, it is a genuinely good idea to assume that if a type can be compared to another type it will explicitly state that in it's interface (like the Abelson class). You could also compare bits that consist the data of an object to bits of another object of a different type but such a comparison is useless in most cases, unless you're interested in run-time profiling.

You've expired your entertainment value , troll.

>>106
RTTI and reflection are allowed. You're allowed to use each and every feature of your language of choice. I didn't mean to bias this in favor of static languages. I want to see what tools can each language provide for writing code similar to >>88.

>>107
type it will explicitly state that in it's interface
it's

Your argument is invalid

>>108
HMA

>>93

{-# LANGUAGE MultiParamTypeClasses #-}

class Convertable a b where
  convert :: a -> b

instance Convertable Int Float where
  convert = fromIntegral

myMax :: (Convertable a b, Ord b) => a -> b -> b
myMax a b = let ba = convert a in
            if ba > b then ba else b

main =
  do let x = 1 :: Int
     let y = 1.1 :: Float
     putStrLn $ show $ myMax x y

The myMax can compare anything that is Convertable, as long as the second argument can also be Ordered. Adding new instances to make other types Convertable should be trivial.

>>110
Your code doesn't meet >>93's requirements. Also, "convertable" is not a word, lrn2english.

>>111
"In a programming language of your choice, implement a function max(a,b), which returns the maximum of a and b. The types of a and b may not necessarily be the same, or even comparable. The type returned by the function must be the type of the maximum value passed in as a parameter, whatever it may be."

OK, this takes arguments of two types, a and b; a and b don't have to be comparable, but a must be convertible into b, and b must be able to compare. It will return either a value of type a if that argument was bigger, or of type b if that was bigger.

As >>94 said, you probably cannot exactly follow >>93's intent with a static type system. However, here, with Haskell's type classes, I've been able to achieve something very close.


class Convertible a b where
  convert :: a -> b

instance Convertible Int Float where
  convert = fromIntegral

myMax :: (Convertible a b, Ord b) => a -> b -> Either a b
myMax a b = let ba = convert a in
            if ba > b then Left a else Right b

main =
  do let x = 1 :: Int
     let y = 1.1 :: Float
     putStrLn $ show $ myMax x y

THE PLEASURE OF BEING CUMMED INSIDE

>>112
Now thank /prog/ for the constructive criticism, you fucking ingrate.

>>111
Maybe English isn't his mother language, you insufferable fool.

>>115
All the more reason to say thanks, fucko.

The space of the   keys of why   fags and dykes   should be burned   off the face   by the headmaster   for my ridikulus   ideas Guess he   saw everything I   am supposed to   display the prime   integers and also   the ones you   feel that it   was modified When.

The Abelson will return to his Earthly   form end the   NET platform on   which modern developers   are creating network   services Enterprises and   win much more   badly than the   JVM citation needed   u sup u.

Lain.