CSC161 2010F, Class 39: Pointers to Functions Overview: * Homework 7 * Function Pointers. * Lab. Admin: * Apologize: Behind in classprep. * Potential Prospies on Friday. * EC for G-Tones concert tonight in Loose Lounge. * EC for RHPS this weekend. * Two interesting performances by Ethel tonight and tomorrow night. * Reading for Friday: K&R 7.5-7.7. * Are there questions on Assignment 7? Homework 7 * Don't we need to length of the arrays in order to sort? * Yes. Sorry. Fixed. * What is merge sort? * Top down recursive version * Divide in half * Sort both halves with merge sort * Merge the two sorted halves. * Bottom-up merge sort * Merge neighbors into sorted lists of length two. * Merge neighbors into sorted arrays of length four. * Merge neighbors into sorted arrays of length eight * ... * Merge neighbors into a sorted array of length n. * For the generic merge sorts, quick sorts, etc. we need a way to compare elements generically For ints #define MAY_PRECEDE(x,y) x <= y For doubles #define MAY_PRECEDE(x,y) x <= y For strings #define MAY_PRECEDE(x,y) strcmp(x,y) <= 0 * How is "a" sorted vs. "ab" * I *believe* "a" comes before "ab" because '\0' comes before 'b'. * But you can accept whatever strcmp tells you. Today's reading was on pointers to functions * C lets you treat "function" as * parameter * something you assign to variables * something you can call * One important difference: These functions are typed: * Something that returns an int should not be used in place of something that returns a double * Something that expects an int should not be used in place of something that expects a double The type looks like this RETURN_TYPE (*NAME)(PARAM_TYPES) For example, fun is a function from integers to doubles double (*fun)(int x); Now, suppose we'd written isqrt double isqrt(int x) We can now write fun = isqrt; More importantly, we can make functions parameters to other functions. int sort(int vals[], int size, int (*may_precede)(int, int)); int ile(int x, int y) { return x <= y; } int ige(int x, int y) { return x >= y; } int c2z(int x, int y) { return abs(x) <= abs(y); } sort (grades, 12, ile); // Sort my array of grades from smallest to largest sort (grades, 12, ige); // Sort my array of grades from largest to smallest sort (temps, 365, c2z); // Sort my array of numbers by closest to zero How does this use of functions as parammeters differ from what we did in Scheme (other than the use of types)? * In Scheme, the symbol <= might have sufficed. * In Scheme, we can use lambda expressions to build anonymous functions. In C, there are not anonymous functions. (Okay, there weren't the last time I checked.) * Higher-order functions? map void imap(int vals[], int size, int (*fun)(int)) { int i; for (i = 0; i < size; i++) vals[i] = (*fun)(vals[i]); } // imap void PREFIX(map)(TYPE vals[], int size, TYPE (*fun)(TYPE)) { int i; for (i = 0; i < size; i++) vals[i] = (*fun)(vals[i]); } // map keep: Given an array and a predicate, keep the elements that meet the predicate. * Hard in C b/c we don't have dynamic arrays (yet) in C. compose (define compose (lambda (f g) ; Return a newly constructed function (lambda (x) (f (g x))))) It turns out that you can't write compose as a HOF in C. Why did I say "I'm a Stooge" when I wrote a function called "Iggy"? Is it because I have my TV Eye on you? Is it because I want my classroom to be a Fun House? Is it in tribute to a dying (perhaps dead) city? Lab! cp -r /home/rebelsky/public_html/Courses/CSC161/2010F/Examples/FunctionPoitners/* HERE