2

I want to use quicksort in C, which has a function signature of void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)), but the signature of my comparison function is int (*compar)(const void *, const void*, const int) with the third argument being constant during one call to quicksort.

As an illustration, assume that I want to sort an array of vectors according to different norms (L0, L1, L2 and Linifinity norm for example). Which norm it actually is, is passed as a third argument to the comparison function, but remains constant during the call of qsort. Is it possible to do an assignment in a form like

//Function declaration for parametric comparison
int cmp3(int* a_vec, int* b_vec, int x);

// Somewhere in main
int (*cmp2)(int, int);
cmp2 = cmp3(int*, int*, 2);//2 could mean L2 norm

to be able to call something like

qsort(a, 100, sizeof(a), cmp2);

I know this does not work, but I hope it gives an idea what I want to accomplish. Also it is not possible to make different comparison functions and calls to qsort as the number of different ways of comparing is too big.

njg
  • 45
  • 6

2 Answers2

4

This is called partial function application, and you can only achieve something like this with wrappers in C:

int cmp3(int *a, int *b) {
    return cmp2(a, b, 2);
}

If you're into partial function application or maybe mappings or pure functions, you may want to look into functional programming languages, like Haskell.

ForceBru
  • 43,482
  • 10
  • 63
  • 98
  • "you can only achieve it with wrappers in C", this is in no way a partial function application. – Stargateur Dec 14 '17 at 15:58
  • @Stargateur, or is it? Partial application is the process of fixing a number of arguments to a function, producing another function of smaller arity. So, this is exactly what `cmp3` does as a wrapper around `cmp`: we had `cmp2(int*, int*, int)` and ended up with `cmp3(int* a, int* b) == cmp2(a, b, 2);`. – ForceBru Dec 14 '17 at 16:06
  • You didn't reduce the arity of the function, you create a second function that have smaller arity :/. https://stackoverflow.com/a/5531152/7076153, the answer is NO. function in C are not primary value. You can't do partial application. – Stargateur Dec 14 '17 at 16:20
  • @Stargateur, right, C doesn't _support that_ natively (unlike Haskell), but one can create something similar anyway. And yes, partial application involves fixing a number of the function's arguments and producing __another function__ of smaller arity, which is exactly what `cmp3` does. – ForceBru Dec 14 '17 at 16:26
  • No this is not, `void (*function)(void *, void *) = cmp2(2);` could be name partial application. You didn't reduce anything, you create an entirely new function, `g(x, y) -> f(x, y, 2)` is not partial application. `f(x, y, 2) -> g(x, y)` is. But if you think that it's partial application please write a book to tell to the world. I think people will love know that do partial application in C is so easy. – Stargateur Dec 14 '17 at 16:34
0

The main problem is that the function signature expects 3 elements in the stack before being called. Old C compilers were "smart" and if you don't pass enough parameters, then they "complete" the stack with empty variables (zeroed).

Nowadays if you do that (assuming the compiler accept),it will have a 3rd variable with undefined value in the stack and not the value you are expecting.

You should do a "proxy" function as a previous comment said:

int cmp3(int *a, int *b) {
    return cmp2(a, b, 2);
}
gwerners
  • 66
  • 1
  • 6
  • Thanks for the clarification about the stack, this was one thing I was thinking about after reading the response above – njg Dec 14 '17 at 16:18
  • 2
    I'm not sure which 'smart C compilers' you are thinking of, but I've not encountered one like that in the last 30-plus years. – Jonathan Leffler Dec 14 '17 at 16:36
  • I have used in the past the Digital Unix C compiler an it could compile this: void function(int a, int b, int c); int main(int argc,char**argv){ function(12,13); return 0; } without problems. It pass 0 to the last variable. And "smart" was due to its strange behavior of accepting such code. – gwerners Dec 14 '17 at 17:10