How to write a function within a function (list_map)

Question

Hello I recently asked some questions on linked lists in C.
The link was found here

First I want to thank everyone for helping me with this. But I have one issue I cannot understand. I even asked the professor but he emailed me back with little information. Basically I am writing a linked list in C (see above link). One of the things the professor gives us in the header file is this:

void list_map( INTLIST *list, void (*f)(void *) );
/*Applies a function to each element of the list */

So I emailed him about this and said:

Another question, in the header file you did not define a sorting function, do we need to write a sorting function with the prototype and finally what is list_map

And he replied with:

You are asked to implement a sorting function f, which is called through list_map(list, f). Hope it clears your doubts.

My only doubts are this was not fully taught. I can understand how to sort the linked list in fact here is some pseudo code:

tmp=head;

while(tmp!=NULL)
{
   tmp2=tmp->next; //pointer to next node
   while(tmp2!=NULL)
    {
     if (tmp2->data < tmp->data)
        {
         int x = tmp2->data;
         tmp2->data = tmp->data;
         tmp2->data = x;
        }
     tmp2=tmp2->next;
    }
   tmp=tmp->next;
}

I know the experts might say this is not the most efficient, and I understand that right now I am just learning and trying to get things working. I can clean up afterwords...so on to my question.

My question is given I have the sort function (in the professor's case he calls it f). How would I call this sorting function when the signature is:

void list_map(INTLIST* list, void (*f) (void*));

Would I just say:

list_map(myList, f()); //apply function f to the current linked list

Or do I really need to define list_map somewhere? I am not the typical student just looking for someone to do my work. I am really trying to understand this as best I can.

Thanks to all of you.

[EDIT PORTION]

I wanted to add that one of the posters Kaleb P. said

"Thus, your job is to create a sorting function that you will pass in to list_map. Note that the correct syntax for passing it in will be:"

So should my code simply be this:

in the .h file I prototype the function as:

void myCustomSort(void*);

And then in the .cpp it becomes:

void myCustomSort(void*f)
{
tmp=f->head; 

while(tmp!=NULL) 
{
   tmp2=tmp->next; //pointer to next node 
   while(tmp2!=NULL) 
   { 
     if (tmp2->data < tmp->data) 
        { 
         int x = tmp2->data; 
         tmp2->data = tmp->data; 
         tmp2->data = x; 
        } 
     tmp2=tmp2->next; 
    } 
   tmp=tmp->next; 
} 
}

And to call it in main I would just do:

list_map(myListPointer, &myCustomSort); 

But don't I need to define list_map anywhere? Because it is in the .h file do I not have to define it?

Answer 1

Assuming list_map is implemented like this, giving f each node in sequential order,

void list_map(INTLIST *list, void (*f)(void *)) {
    INTLIST *node;
    for (node = list; node; node = node->next)
        f(node);
}

you can implement a selection sort

void list_sort(INTLIST *list) {
    list_map(list, swap_head_with_smallest);
}

where void swap_head_with_smallest(void *) swaps the datum of a given node with the smallest of the data of any nodes following it in the list.

---

As this is homework, I'm trying not to give the whole solution away.

void swap_head_with_smallest(void *list) {
    INTLIST *head = list;
    INTLIST *smallest;

    /* set smallest the smallest node of
         head, head->tail, head->tail->tail, etc. */

    /* swap head->datum and smallest->datum */
}

Answer 2

Your professor is trying to teach you a concept that's common in functional programming, which is the idea of a higher-order function. A higher-order function can take other functions as parameters, sort of like

list_of_cosines = map(cos, list_of_inputs)

where list of inputs is a series of floating point values, and cos is the normal cosine function. The map function will call cos for each value in list_of_inputs and return a list of the corresponding results.

C functions cannot take other function types as parameters, but they can take pointers to functions as parameters (usually termed a callback); the canonical example is the qsort() library function, which takes as one of its parameters a pointer to a function that accepts two pointers to void and returns -1, 0, or 1 depending on whether v1 < v2, v1 == v2, or v1 > v2, respectively. For example:

int compareIntValues(const void *v1, const void *v2)
{
  int lv1 = *(int *) v1; // convert inputs from pointers to void
  int lv2 = *(int *) v2; // to the type we're actually interested in
  if (lv1 < lv2) return -1;
  if (lv1 > lv2) return 1;
  return 0;
}

int main(void)
{
  int values[] = {3, 1, 4, 5, 7, 9, 6, 2};
  ...
  qsort(values,                             // buffer containing items to sort
        sizeof values / sizeof values[0],   // number of items to sort
        sizeof values[0],                   // size of each item
        compareIntValues);                  // comparison function
  ... 
}

qsort() will then call compareIntValues to order the elements in values. Similar to array expressions, a function designator will have its type implicitly converted from "function returning T" to "pointer to function returning T" depending on the context.

At this point I'm guessing, but it looks to me like your professor wants you to write the list_map function so that it will call a sorting function f with the list as the parameter, something like the following:

void list_map(INTLIST *list, void (*f)(void *))
{
  // sort the list by passing it to f
  f(list); // or (*f)(list);
}

void sortListAscending(void *ptr)
{
  INTLIST *ilptr = ptr;
  /**
   * sort the list in ascending order
   */
}

void sortListDescending(void *ptr)
{
  INTLIST *ilptr = ptr;
  /**
   * sort the list in descending order
   */
}

int main(void)
{
  INTLIST *theList;
  ...
  list_map(theList, sortListAscending); // sort the list in ascending order
  ...
  list_map(theList, sortListDescending); // sort the list in descending order
  ...
}

The interface provided by your professor is a bit confused; either both the list pointer and the parameter to f() should be void * (in which case you could use list_map to map functions to different list types) or both the list pointer and parameter to f should be INTLIST * (since you seem to be dealing with INTLIST types).

If I'm right, then the exericise is a bit pointless on the surface (why not call the sorting function directly?), but it could be your professor is building up to something a bit more general-purpose. After all, there's no reason that f has to be a sorting function; it could be a function to display the list, or to save the list to a file, or something else.

I have a different example of how to use callbacks to sort a list here; it may help illustrate why this method is useful.

EDIT

ephemient's example of what list_map needs to do is probably much closer to what your professor intends than what I wrote.