How to write a function inside a function (list_map)

Question

Hello, I recently asked a few 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 problem that I cannot understand. I even asked the professor, but he e-mailed me some information. Basically, I write a linked list in C (see Link above). 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 sort function, we need to write a sort function with a prototype, and finally, what is list_map

And he answered:

You will be asked to implement the sort function f, which is called via list_map (list, f). Hope it clears your doubts.

My only doubt is that this has not been fully taken into account. I can understand how to actually sort the linked list, here is some kind of 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 that experts can say that this is not the most effective, and I understand that now I am just studying and trying to make everything work. I can clear the afterword ... so on to my question.

My question is asked. I have a sort function (in the case of a professor, he calls it f). How can I call this sort function when the signature is:

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

I would say:

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

Or do I really need to define list_map somewhere? I'm not a typical student, just looking for someone to do my job. I'm really trying to figure it out as best as possible.

Thank you everybody.

[EDIT PORTION]

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

"Therefore, your task is to create a sort of the function with which you list_map. Note that the correct syntax for passing it will be:"

So should my code just be as follows:

in the .h file, I am a function prototype:

 void myCustomSort(void*); 

And then in .cpp it will be:

 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 basically, I would just do:

 list_map(myListPointer, &myCustomSort); 

But don't I need to define list_map anywhere? Since it is in the .h file, do I need to define it?

Answer 1

Assuming list_map implemented as follows, 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 sorting selection

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

where void swap_head_with_smallest(void *) replaces the base date of the given node with the smallest of the data of any nodes following it in the list.

---

Since this is homework, I try not to give the whole decision.

 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 is 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 a normal cosine function. The map function calls cos for each value in list_of_inputs and returns a list of corresponding results.

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

 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 . Like an array expression, a function pointer will have its type implicitly converted from a "function returning T" to a "pointer to a return function T" depending on the context.

At the moment, I suppose, but it seems to me that your professor wants you to list_map function, so that it list_map the sort function f with the list as a 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 confusing; either the list pointer and the f () parameter should be void * (in this case you could use list_map to map functions to different types of lists), or the list pointer and the parameter in f should be INTLIST * (since you seem to be dealing with types INTLIST).

If I'm right, then exericise is a little pointless on the surface (why not call the sort function directly?), But it may be your professor creating something more universal. After all, there is no reason for f be a sort function; it may be a function to display the list or save the list to a file or something else.

I have another example of using callbacks to sort the list here ; this can help illustrate why this method is useful.

EDIT

The ephemeral example of what list_map should do is probably much closer to what your professor intends than what I wrote.

Answer 3

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

So your task is to create a sort function that you pass to list_map . Note that the correct syntax for passing it is:

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

I would guess that void* passed to your sort function would probably be in the node in the linked list.

MergeSort is a good choice for sorting linked lists.

Answer 4

I believe the list_map function calls a function pointer f (), which is a pointer to a function that takes a void pointer and returns void. If so, then this is a crazy way to implement a view, but doable.

Define a function of type

 void Test(void *) {...} 

And pass it to list_map () like this:

 list_map(listptr,Test); 

I would suggest that your test function is called for every item in the list.

Answer 5

If your node has a pointer to a list header, you should use a list pointer as a border. Let me explain.

The display function is a general concept in functional programming, at the moment you should know that this is a function that receives a list and applies another function (application function) to each node of this list. I bet you already knew that.

The C language does not have, as I recall, a display function, so you need to define it on your own. This is not very difficult: just start at the head of the list and go to the tail. For each step, pass the current listnode to the function that performs the operation that you want to perform (in this case, sorting).

Now there is your task.

• You cannot get any data from the application function (it returns void)
• You need to go to the end of the list, passing each node to the sort function.
• It is useless to sort a list that you have not visited yet, since you will sort it for each node (sorting an already sorted set is not too smart for me);)
• Your application function gets one pointer. This clearly indicates that this pointer (the node you are on) is a line: to the left of it (by head) is the part of the list already sorted, to the right (to the tail) there are wild elements.
• Since your application function receives just a simple void * as input, I think it's better to leave pointers alone and exchange the payload for nodes.

Said that the pseudo-code for your sort function, one of the possible ones could 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; } }