#lang racket ; hof.rkt: CS 251 Higher-Order Functions examples (define (double x) (* 2 x)) (define (inc x) (+ 1 x)) (define a-cons-cell (cons double inc)) (define wow ((car a-cons-cell) ((cdr a-cons-cell) 4))) ; it should *pain* us to write the next three functions separately (define (inc-n-times-ouch n x) (if (= 0 n) x (+ 1 (inc-n-times-ouch (- n 1) x)))) (define (double-n-times-ouch n x) (if (= 0 n) x (* 2 (double-n-times-ouch (- n 1) x)))) (define (cdr-n-times-ouch n xs) (if (= 0 n) xs (cdr (cdr-n-times-ouch (- n 1) xs)))) ; The world balance is tilted toward evil by this code. ; We must abstract the common pattern to save the day! ; First-class and higher order functions give us an elegant tool. (define (n-times f n x) (if (= 0 n) x (f (n-times f (- n 1) x)))) (define a (n-times double 4 7)) (define b (n-times inc 4 7)) (define c (n-times cdr 4 (list 1 2 3 4 5 6 7 8 9))) ; And of course we can define functions for these as well. (define (double-n-times n x) (n-times double n x)) (define (add n x) (n-times inc n x)) (define (nth-cdr n xs) (n-times cdr n xs)) ; Anonymous functions mesh nicely with higher order functions. (define (three-to-the n) (n-times (lambda (x) (* 3 x)) n 1)) (define eighty-one (three-to-the 4)) ; But don't get too lambda-zealous. Wrapping functions needlessly ; is poor style. (define (nth-cdr-bad n xs) (n-times (lambda (ys) (cdr ys)) n xs)) ; Use the earlier definition instead. cdr is already a function! (define (nth-cdr-good n xs) (n-times cdr n xs)) ; Higher-order function hall-of-famer! What does it do? (define (map f xs) (if (null? xs) null (cons (f (car xs)) (map f (cdr xs))))) (define bumped (map inc (list 1 2 3 4 5))) ; = 2 3 4 5 6 (define doubled (map double (list 1 2 3 4 5))) ; = 2 4 6 8 10 (define firsts (map car (list (cons 1 2) (cons 3 4) (cons 5 6)))) ; = 1 3 5 ; Another famous higher-order function. (define (filter f xs) (if (null? xs) null (if (f (car xs)) (cons (car xs) (filter f (cdr xs))) (filter f (cdr xs))))) (define (even? x) (= 0 (modulo x 2))) (define all-even (filter even? (list 1 2 3 4 5))) (define bigger-than-7 (filter (lambda (x) (> x 7)) (list 1 485 3 55 14))) ; Return a function. (silly example, better ones later) (define (double-or-triple-if-f-of-seven f) (if (f 7) (lambda (x) (* 2 x)) (lambda (x) (* 3 x)))) (define d (double-or-triple-if-f-of-seven (lambda (x) (< (- x 9) 0)))) (define e (d 3))