Recursion

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.

Lists

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

Match

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

Tree

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

Abstraction Over Functions

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.

We claim that something is the identity function on lists, we prove it by induction, suppoes that ls is the empty list, then something returns it back immediately, now suppose that it is the identity function on a list of size $n \in N_{0}$ , then if we call something on a list of size $n + 1$ , then since it's size is at least one, then we know that the second match branch is called, and thus the returned result is cons x (list-acc bop xs init) but note that (list-acc bop xs init) is the same as something xs and since xs has size $n$ then this returns xs, and so the final return is cons x xs which is ls, so by induction something it the identity on lists.

We claim that something-else reverses any input list. Before proving this let's understand why, suppose we call it with a list [1, 2, 3, 4], we can see that through recrusive calls, we break off the first element and then put it at the start of the accumulator by putting it at the front, we're reversing the order of the list so by the time we reach the base case, we've entirely reversed the list.

TODO add formal proof.

folding

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

⋆ : 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 ⋆ (a_{1} ⋆ (a_{2} ⋆ \dots (a_{n - 1} ⋆ a_{n}))))

foldl Expression