:::warning **Announcements** - `A0: Intros` graded - `A1: Values` due tonight - `A2: Functions` out tomorrow - First pair assignment! Pair policy summary, [Google form for pair matching](https://forms.gle/ua41UfbydZ1dsbkV6) - Next help hours: - Emily 3-5pm tomorrow L037 ::: :::success **Agenda** - Tail-recursive `reverse` ([prior notes][notestail]) - RackUnit ([prior notes][notesunit]) - Functions as values - Syntactic sugar - The most famous higher-order functions (HOF) - `map` (transform all!) - `filter` (keep some!) - `fold` (combine to one value!) - left vs right fold (next time) - Practice: writing/using HOFs (next time) ::: [notestail]: https://hackmd.io/@avh/B1Fdn6Sjlx#Tail-recursive-reverse [notesunit]: https://hackmd.io/@avh/B1Fdn6Sjlx#Testing-with-RackUnit # Functions as values Racket has first class functions: functions have all the rights and privileges of other values! A function is a `value` because on its own, in its current form, it cannot be evaluated. A function needs to be _applied_ in order to be further evaluated. `+` on its own is a function: it is a value. `(+ 1 0)` is a function application: it is *not* a value, because it can be evaluated to the value of `1`. :::info :star: Student question: is `'(+ 1 2)` a value? ::: :::spoiler Think, then click! Yes, `'(+ 1 2)` is a value! This is because the `'` tic/single quote in Racket stops evaluation, and instead indicates that what follows should be treated as a data value. Another way to think about this is that the `'(...)` turns what's inside the parens into a list of quoted data: ```racket > (first '(+ 1 2)) '+ ``` In more detail than we got to in class, this is the "quote" form: https://docs.racket-lang.org/guide/quote.html ::: :::info :star: Student question: is `'(+ 1 2)` a lambda/function? ::: :::spoiler Think, then click! No, it cannot be applied. Trying to apply it gives: ``` application: not a procedure; expected a procedure that can be applied to arguments given: '(+ 1 2) ``` ::: A lambda expression defines a function: ```racket (lambda (x y) (+ x y)) ; ^ args ^ body ``` is the function that adds its two arguments. Note that this function does not have a name: it is _an anonymous function_. It turns out that the function definition syntax we've been using so far is really just syntactic sugar for a variable binding to a lambda! `(define (fn x) (...))` is really sugar for `(define fn (lambda x) (...))`! ## Syntactic sugar _Syntactic sugar_ is convenient syntax added to a language to make it easier to use, without changing the core language itself. It's called "sugar" because it's an additive that makes our lives sweeter! Syntactic sugar is: – _Static textual translation_ to existing features in the core language. – i.e., not a new language feature. We'll see other examples of syntactic sugar throughout the semester. A3: Interp has you work with the "desugaring" process. ## Functions as values, vs. higher-order functions First, a bit of terminology: A language having **first-class** functions means that functions can be used in any other place a value can be used. This is also sometimes referred to as "functions as values". A **higher-order function** is a function that takes one or more other functions as arguments and/or produces a function as a result. Why two different terms? "Higher-order functions" are a mathematical concept that applies outside of programming, where "first-class functions" is more commonly used to describe a feature of a programming language. # `map` (transform all) ## Function group exercise (`map`) :::success Consider the following warmup questions: ::: ```racket (define (double-all ls) (if (empty? ls) '() (cons (* 2 (first ls)) (double-all (rest ls))))) (define (add-1-all ls) (if (empty? ls) '() (cons (+ 1 (first ls)) (add-1-all (rest ls))))) (define ls '(1 2 3 4 5)) ;; WARMUP QUESTIONS: ;; Q1: What is shared across these two implementations? ;; Q2: What is different? ;; Q3: Write two lambda expressions to capture what each function does to ;; each element of the list (the "different" piece, one for double-all ;; and one for add-1-all). ``` :::spoiler Think, then click! Q1: both implementations produce a new list by applying some transformation to every element in the argument list. Q2: `double-all` doubles the element, `add-1-all` adds 1 to the element. Q3: here are the two lambdas: ```racket (lambda (elem) (* 2 elem)) ; doubles (lambda (elem) (+ 1 elem)) ; adds 1 ``` ::: :::info :star: Student question: isn't separating out the `lambda` more work than just writing the original function? ::: :::spoiler Think, then click! It would be, if we only wanted to write a single function. But we'll see this pattern happens *all the time*. Imagine, say, we were writing a list-calculator app that wanted to apply dozens of functions to each element of a list. A core philosophy in programming is to avoid redundant code, and to instead abstract over shared details. In the rest of this lecture, the value of this will hopefully become more clear. ::: Now, let's write a function that can do _either_ of these actions based on the function passed in as an argument: we can start with `double-all`, rename it to `out`, then take the function to apply as an argument `f`: ```racket (define (out f ls) (if (empty? ls) '() (cons (f (first ls)) (out f (rest ls))))) ; note: need to pass f ``` We can then call this as: ```racket > (out (lambda (x) (* 2 x)) ls) '(2 4 6 8 10) > (out (lambda (x) (+ 1 x)) ls) '(2 3 4 5 6) ``` We have accomplished the same thing as our two original functions, without duplicating so much code! :::info This is in fact the **most famous** higher-order function: better known by the name **map**! **map** applies a given function to each element of a collection, producing a new collection of results in the same respective order as the original list. ::: With its more common name: ```racket ;; The most famous higher-order function! ;; map ;; - f : a function to be applied ;; - xs : a list ;; map creates a new list with f applied to each element of xs (define (map f xs) (if (empty? xs) '() (cons (f (first xs)) (map f (rest xs))))) >> (map (lambda (x) (* 2 x)) ls) '(2 4 6 8 10) >> (map (lambda (x) (+ 1 x)) ls) '(2 3 4 5 6) ``` :::success Another question: based on our implementation, does the value we return for each element need to be the same type as the values in the list? ::: :::spoiler Think, then click! Answer: No! Nothing here requires that the output have the same type. Consider: ```racket > (map number->string ls) '("1" "2" "3" "4" "5") ``` ::: ### Map in other languages Map is built into _many_ languages now: Python: ```python # Map in python doubled = list(map(lambda x: x * 2, numbers)) # Or: similar idea, list comprehension doubled = [x * 2 for x in numbers] ``` JavaScript: ```javascript const doubled = numbers.map(x => x * 2); ``` Rust: ```rust let doubled: Vec<i32> = numbers.iter().map(|x| x * 2).collect(); ``` OCaml: ```ocaml let doubled = List.map (fun x -> x * 2) numbers;; ``` ## More properties of map: :::info Properties of **map**: - Input items and return items do not need to be of the same type - Preserves the length of the original list ::: --- # `filter` (keep some) Let's look at another case where we could use a nice functional abstraction: ```racket (define (keep-even ls) (if (empty? ls) '() (let ((rs (keep-even (rest ls)))) (if (even? (first ls)) (cons (first ls) rs) rs)))) (define (keep-gt3 ls) (if (empty? ls) '() (let ((rs (keep-gt3 (rest ls)))) (if (> (first ls) 3) (cons (first ls) rs) rs)))) ``` :::success What do both of these functions do? ::: :::spoiler Think, then click! They both apply a check to every element of a list, producing a new list with only the values that passed the check. ::: In the first function, the check is `even?`. In the second function, the check is `(lambda (x) (> x 3)`. This leads us to another famous higher-order function: **filter**! ```racket ; Another famous higher-order function. ;; filter ;; - f : a function to be applied as a predicate/check ;; - xs : a list ;; filter creates a new list with each element of xs where f ;; applied to the element is not #f (define (filter f xs) (if (empty? xs) empty (if (f (first xs)) (cons (first xs) (filter f (rest xs))) (filter f (rest xs))))) ``` Rewriting our two functions from above: ```racket > (filter even? ls) '(2 4) > (filter (lambda (x) (> x 3)) ls) '(4 5) ``` :::success What restrictions do we have on the function for filter? ::: There are in a sense two different answers: 1. *Conceptually*, we want it to return a boolean. 2. In practice, Racket treats anything other than `#f` as true. For example: ```racket > (filter (lambda (x) (+ 1 x)) ls) '(1 2 3 4 5) ``` :::warning Be aware of this as you are debugging! **filter** will run with functions that don't produce a boolean, but probably that was not what you meant to do. ::: ## Properties of **filter** :::success Properties of **filter**: - The length of the produced list may be anything from 0 to the length of the original list. - (In Racket) this does not mutate the list or its elements, conceptually it copies them to build a new list. ::: --- # `fold`: (reduce/combine to result) We'll motivate our third famous higher-order function with another pair of examples: ```racket (define (sum ls) (if (empty? ls) 0 (+ (first ls) (sum (rest ls))))) (define (product ls) (if (empty? ls) 1 (* (first ls) (product (rest ls)))) ``` :::success What is **not** shared across these two functions? ::: :::spoiler Think, then click! Answer: 1. The function to apply (e.g., `+` vs `*`) 2. The base case value (here, the identity: `0` vs `1`) - we can also think of this as the "starting" value We can see that the function to apply and the base case values are related in these examples: the base case values are the identity for the function. We can also notice that unlike `map`/`filter`, the functions here are applied to 2 (not 1) argument(s). ::: We call this *fold* (though in other languages, its sometimes called *reduce*). :::warning We got to here in Thursday's lecture, but feel free to read ahead if you'd like. ::: ## Fold group exercise: :::success - Implement 2 versions of fold - 1 should use natural recursion (same pattern as sum and product) - 1 should use tail recursion - Discuss: do both versions produce the same result? - It's likely helpful to draw out list of calls - What happens if we pass both `(fold cons empty lst)` ? ::: :::spoiler Think, then click! ```racket ; Our third famous higher-order function: fold! ; Natural recursion (define (foldr func acc lst) (if (empty? lst) acc (func (first lst) (foldr func acc (rest lst))))) ; Note: foldr is not tail recursive, since foldr is not called ; as the outer-most expression of the "else" ; Said another way: after a recursive call returns, the function ; still needs to do the work of applying the function to the ; current element and the recursive result. ; In tail recursion, the function should have no work left by ; the time the recursive call returns ; Tail recursion ; Note we don't *need* a helper function with an additional ; acc, since we can use the argument tracking the "starting" ; value for that! (define (foldl func acc lst) (if (empty? lst) acc ; Note: acc should be the 2nd arg to the (func ...) call to ; match Racket's built-in foldl order. In class, our ; specification was not precise enough to require this, ; but the version below *is* what I showed in class as ; the reference solution! (foldl func (func (first lst) acc) (rest lst)))) ``` ```racket ; Fold right recursion (foldr + 0 '(1 2 3)) ; result: (+ 1 (foldr + 0 '(2 3))) (foldr + 0 '(2 3)) ; result: (+ 2 (foldr + 0 '(3))) (foldr + 0 '(3)) ; result: (+ 3 (foldr + 0 '())) (foldr + 0 '()) ; result 0 ; Overall, computes (+ 1 (+ 2 (+ 3 0)) ; ^ base case, initial acc ; ^ processes elems -> to the right ; Note: acc stays the same, is just passed down to the base ; case ; Fold left recursion (foldl + 0 '(1 2 3)) (foldl + (+ 1 0) '(2 3)) (foldl + (+ 2 1) '(3)) (foldl + (+ 3 3) ()) ; returns (+ 3 3) = 6 ; Overall, computes (+ 3 (+ 2 (+ 1 0))) ; ^ initial acc ; ^ processes elems <- to the left ; 3 is the outer-most elem ; Note: acc changes on each recursive call ``` :star: `foldr` uses an accumulator, but is not tail recursive! - `foldl` is more efficient because it is tail recursive, but if order matters, it effectively visits the elements in reverse order. - `foldr` maintains the same order. This matters for e.g., string concatenation. If stack space is more of a concern then time, it's more efficient to `foldl` and then `reverse` (both tail recursive). ::: # Combination HOF example Here is a function that returns the sum of the squares of all the positive numbers in a list. ```racket ; Answer using all 3 famous HOFs! (foldl + 0 (map (lambda (x) (* x x)) (filter positive? ls))) ``` Note: this solution uses HOFs, but does not use _explicit_ recursion (it does not call a function recursively on the `rest` of `ls`, even though implicitly we know the implementations do recur). A2: Function asks you to write similar functions.