Here we'll assume that you are already familiar with recursion, we're going to use it now to build up everything we can do in non-functional programming languages, so that we're not lost when it comes to doing basic things in a functional way.

Tail Recursion

We say that a recursive call is tail recursive, if it is the last evaluated expression before the outer function returns.

Let's start by looking at the sum of consecutive numbers, from a non-tail recursive approach:

(define (recsum x) (if (zero? x) 0 (+ x (recsum (- x 1) ) ) ) )

We can observe that `recsum`

is not tail recursive, because when it makes it's recursive call, we still have to add x to that value before we return. Now let's look at a tail-recursive solution

(define (tail-recsum x sum) (if (zero? x) sum (tail-recsum (- x 1) (+ sum x))) )

Here we'll note that there is a difference in our approach, we first add sum to x before passing it to the next layer in the recursion, the benefit of this is that all the information is passed from one recursive layer to the next, meaning that there's no need to keep the stack frame of the previous call in memory. This allows for tail call optimization, which will save space and time.

Another way of thinking about tail recursion, is that the previous function is going to return whatever this function returns, so there's no need to keep any information about the previous function call.

When working with lists, we can notice that it has a recursive structure, for example if we had the list [1, 2, 3, 4], we could think of this as a list with two elements, [1, [2, 3, 4]], where the second element [2, 3, 4] is really a list of the form [2, [3, 4]], where the second element [3, 4] is really [3, [4]], where the second element is really [4, []], and then we stop.

The above should convince you what indeed lists do have a recursive structure, most functional languages will allow you to split lists based on what we just discussed.

> (car '(1 2 3)) 1 > (cdr '(1 2 3)) '(2 3)

With this recursive structure in place, we know that a list is either an empty list or it is an element x with a prepended list xs, we can directly translate that idea into a function which returns the length of our list

(define (list-length l) (if (equal? l '()) 0 (+ 1 (list-length (rest l) ) ) ) )

While using if statements works, the match statement helps us take a recurisve element and figure out what rule was used to produce it. For example, we can re-do the above code:

(define (list-length l) (match l ['() 0] [(cons x xs) (+ 1 (list-length xs) ) ] ) )

We can also quickly create a map function like this:

(define (map f l) (match l ['() '()] [(cons x xs) (cons (f x) (map f xs))] ) )

In general we can use this as a template to build functions that operate on lists

(define (list-op-template l) (match l ['() TODO] [(cons x xs) (TODO (list-op-template xs))] ) )

We also know that trees have a recursive structure, so we can define those too:

; a binary tree holding values of type T ; - either an empty tree represented by the symbol 'nil ; - a node that contains two binary trees (left and right) and a value of type T (struct Node (left val right) #:transparent) (define (tree-op-template t) (match t ['nil TODO] [(Node l v r) (TODO (tree-op-template l) (tree-op-template r))] ) )

Specifically we can get the tree's depth for example:

(define (tree-depth t) (match t ['nil 0] [(Node l v r) (+ 1 (max (tree-depth l) (tree-depth r)))] ) )

First recall that we created functions to abstract over values, for example, suppose we want to convert from celcius to farenheit, then we could specifically do it for any value we wanted like this:

(+ 32 (* -7 (/ 9 5))) (+ 32 (* 9 (/ 9 5))) (+ 32 (* 20 (/ 9 5))) ...

But that becomes unwieldy, so we create

;; number -> number (λ (x) (+ 32 (* x (/ 9 5)))

And thus we no longer have to write the same expression again and again. Now we'll observe this pattern occur again but for functions themselves

(define (list-sum l) (match l ['() 0] [(cons x xs) (+ x (list-sum xs))] (define (list-prod l) (match l ['() 0] [(cons x xs) (* x (list-prod xs))]

Therefore to stop writing the same code again when we need a new function to work on a list, we create the following

(define (list-acc bop ls init) (match ls ['() init] [(cons x xs) (bop x (list-acc bop xs init))] ) )

Note:

- ls is the list.
- bop stands for a binary operation
- init is the initial value such 0 for the sum which is used in the base case
- bop and init need to be passed all the way through the recursive calls so that bop will be available at any arbitrary level in the recursion. We need init so that when we reach the base case we will be able to return it as we do not have the ability to hard code it in. A more sane way to think of why we need to pass the values is that if we did not there would be no way to use them at some arbitrary level in the recursion.

And now we can produce our functions easily:

(define (list-sum l) (list-acc + l 0)) (define (list-prod l) (list-acc * l 1))

Higher Order Function

We say that a function f is to be high-order if

- one or more of its arguments are a function
- its output is a function

The usual suspects for higher order functions are

`map`

which is a function which takes another function f and a list, and the result is a new list where each element is procued by calling f on the corresponding element of the input list.`filter`

takes a predicate, and a list, and returns a list of elements that satisfy the predicate.`compose`

takes two functions f: A -> B and g : B -> C and produce a new function h : A -> C defined as h(x) = g(f(x))

For fun let's go back to `list-acc`

and make a tail-recursive version:

(define (list-acc-tr bop ls acc) (match ls ['() acc] [(cons x xs) (list-acc-tr bop xs (bop x acc)] ) )

Note the similar pattern to our previous tail recursion, we first apply the binary operation before we do the recursive call, note that it happens in this order because racket has eager evaluation, which means that all of it's arguments are evaluated before the function is called.

List Operation Tail

Observe the following code

(define (something ls) (list-acc cons ls '())) (define (something-else ls) (list-acc-tr cons ls '()))Determine what the functions

`something`

and `something-else`

are and prove that they do what you claim.
A fold takes in

- a function f: (A, B) -> B
- a list of type A
- an initial value of type B

And produces a value of type B

We can start by doing right folding

(define (foldr f init ls) (match ls ['() init] [(cons x xs) (f x (foldr f init xs))] ) )

To understand how this works we'll write out an example:

(foldr + 0 '(1 2 3)) (+ 1 (foldr + '(2 3)) ) (+ 1 (+ 2 (foldr + '(3)) )) (+ 1 (+ 2 (+ 3 (foldr '()) ))) (+ 1 (+ 2 (+ 3 0 ))) (+ 1 (+ 2 3)) (+ 1 5) 6

There's two ways of remembering foldr, it's called the right version because the fold call moves to the right, also note that it creates a full expression before everything is evaluated on the way out.

And now we have folding from the left:

(define (foldl f acc ls) (match ls ['() acc] [(cons x xs) (foldl f (f x acc) xs)] ) )

With the following example:

(foldl + 0 '(1 2 3)) ; which returns whatever is on the next line (foldl + 1 '(2 3)) ; which returns whatever is on the next line (foldl + 3 '(3)) ; which returns whatever is on the next line (foldl + 6 '()) ; which returns whatever is on the next line 6

Note that the way foldl did it's calculation was like (3 + (2 + (1 + 0))) where as foldr did it as (((0 + 1) + 2) + 3).

You can remember foldl because the fold always stays on the left, which is an artifact of it being tail recursive, since it is tail recursive it runs faster than foldr. It calculates things as it goes, so that when the final recursive call is reached there is nothing more to do.

foldr Expression

Suppose that we have a list $({a}_{1},\dots ,{a}_{n})\in {X}^{n}$ and some binary operation $\star :X\times X\to Y$, that has some identity element $e$ that is used as the accumulator, then the evaluation of foldr with these arguments is given by $$(e\star ({a}_{1}\star ({a}_{2}\star \dots ({a}_{n-1}\star {a}_{n}))))$$

foldl Expression

Suppose that we have a list $({a}_{1},\dots ,{a}_{n})\in {X}^{n}$ and some binary operation $\star :X\times X\to Y$, that has some identity element $e$ that is used as the accumulator, then the evaluation of foldr with these arguments is given by $$({a}_{n}\star ({a}_{n-1}\star \dots ({a}_{2}\star ({a}_{1}\star e))))$$

foldr foldl Equivalent When Operation is Commutative and Associative