C - Help understanding 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

I believe that the list_map function calls the function pointer f() which is a pointer to a function that takes a void pointer and return void. If that is the case this is crazy way to implement a sort but doable.

Define a function like

void Test(void *)
{...}

And pass it in to the list_map() like so

list_map(listptr,Test);

I would assume your Test function gets called for each item in the list.

Answer 2

The second parameter to list_map is a pointer to function returning void and taking in a void pointer. Since list_map appears to be a map function, I would guess that it will call f (the pointer to a function) for each element of the list.

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:

void yourCustomSort(void*);
list_map(myList, yourCustomSort);

I would guess that the void* being passed into your sorting function will probably be to a node within the linked list.

MergeSort is a good choice for sorting linked lists.

Answer 3

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 4

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.

Answer 5

If in your node there is a pointer to the head of the list you have to use the pointer to the list as a frontier. Let me explain.

The map function is a common concept in functional programming, for now, you have just to know that is a function that get a list and apply another function (the applied function) to every node of the list was given to it. I bet you already knew it.

C language haven't, as far I remember, a map function, so you have to define one by your own it. It is not very difficult: Just start from the head of the list and walk to the tail. For every step pass the current listnode to the function that perform the operation you need to be performed (in this case the sort).

Now there is your assignment.

• You cant get any data from the applied function (it returns void)
• You have to walk down until the end of the list passing every single node to the function that do the sorting.
• It is useless to sort the list you haven't already visited, as you would keep to sort it for every node (sorting an already sorted set it is not too smart to me) ;)
• Your applied function get a single pointer. This in clearly stating that that pointer (the node you are at) represent a line: on his left (to the head) there is the part of list already sorted, to the right (to the tail) there are the wild elements.
• Since Your applied function get as input just a simple void * , I think it is better to leave the pointers alone and exchange the payload of the nodes

Said that, the pseudocode for your sorting function, one of the possibile ones, can be:

void ascendingSort(void*f)
{
  cursor=f->head; 
  placed=false;

  while(!placed and cursor!=f) { 
    if (cursor->data < f->data) {
      cursor = cursor->next;
    } else {
      swap( cursor->data, f->data);
      placed=true;
    }
  }

  while(cursor!=f) { 
      cursor = cursor->next;
      swap(cursor->data, f->data);
  }

}

Or, in a more concise form:

void ascendingSort(void*f)
{
  cursor=f->head; 

  while(cursor!=f) { 
    if (cursor->data > f->data) {
      swap( cursor->data, f->data);
    }
    cursor = cursor->next;
  }
}