#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))