Lecture 04

2023-04-12 | Week 2 | edited by Ruining Ding

(originally written 2022-10-03 by Boyan Ding)

Ruining here! This continues from last lecture, and covers the slides 82-122 Intro to FP deck. Note that the material from slides after 122 will be covered in discussion. As always, please give me feedback on the notes!

Table of Contents

• First-class and higher-order functions
• Map, Filter and Reduce
  • Map
  • Filter
  • Reducers (foldl/foldr)
  • Influencer Alert: map-filter-reduce
• Advanced Topics in Functional Programming
  • Lambda Functions
  • Closures
  • Influencer Alert: Lambda and Closure
  • Currying

First-class and higher-order functions

One key characteristic of functional languages is that they enable you to treat a function just like any other variable. In other words, functions are first-class!

Formally speaking, a language with first-class functions treats functions like any other data. They can be:

• stored in variables or data structures
• passed as arguments to other functions
• returned as values by functions

As we’ll see, these features enable more efficient program decomposition and allow functions to generate new functions from scratch !

One consequence of first-class functions is something called a higher-order function, which is either:

• a function that accepts another function as an argument, and/or
• a function that returns another function as its return value

The following example exercises the property of passing functions as arguments:

-- first.hs
insult :: String -> String
insult name = name ++ " is so cringe!"

praise :: String -> String
praise name = name ++ " is dank!"

talk_to :: String -> (String -> String) -> String
talk_to name talk_func
  | name == "Carey" = "No comment."
  | otherwise = (talk_func name)

talk_to is a higher-order function: its second argument, talk_func, is itself a function that takes in a String and returns a String. That’s reflected in its type: (String -> String); take note of the parentheses in the type declaration to denote a function-type parameter.

Let’s give it a shot:

ghci> :load first
[1 of 1] Compiling Main             ( first.hs, interpreted )
ghci> talk_to "Devan" praise
"Devan is dank!"
ghci> talk_to "Brendan" insult
"Brendan is so cringe!"
ghci> talk_to "Carey" insult
"No comment."

This second example returns a function!

-- first.hs
get_pickup_func :: Int -> (String -> String)
get_pickup_func born
  | born >= 1997 && born <= 2012 = pickup_genz
  | otherwise = pickup_other
 where
   pickup_genz name = name ++ ", you've got steez!"
   pickup_other name = name ++ ", you've got style!"

The higher-order function get_pickup_func returns different functions according to the argument born. The returned function can be stored into variable and invoked later.

ghci> :load first
[1 of 1] Compiling Main             ( first.hs, interpreted )
ghci> pickup_fn = get_pickup_func 2003
ghci> pickup_fn "Jayathi"
"Jayathi, you've got steez!"
ghci> get_pickup_func 1971 "Carey"
"Carey, you've got style!"

Although first-class and higher-order functions originate from functional programming, they are a pillar of virtually all modern programming languages.

Their use-cases include:

• providing comparison functions for sorting
• as callbacks when events trigger
• enabling multi-threading

Some examples:

// JavaScript
const sortByDate = (a,b) => {
  if (a.date < b.date) return -1;
  if (a.date > b.date ) return 1;
  return 0;
}

movies.sort(sortByDate);

// JavaScript
const handleClick = function (event) {
   alert("A button was clicked!");
};

// Select big button from HTML web page
var button = document.querySelector('#big-button');
// Specify what func should be called when it's clicked
button.addEventListener('click', handleClick);

// C++
void foo()      { /* does some work & returns */ }
void bar(int x) { /* does some work & returns */ }

int main() {
  std::thread thread1(foo), thread2(bar,42);

  // Run main, foo and bar until they all finish
  thread1.join(); // pause until foo() finishes
  thread2.join(); // pause until bar() finishes
  std::cout << "main, foo and bar completed.\n";
}

Map, Filter and Reduce

Here we introduce a key set of higher-order utility functions to process lists that are included in virtually all functional programming languages.

These functions fall into three categories: mappers, filters and reducers.

• A mapper function performs a one-to-one transformation from one list of values to another list of values using a transform function
• A filter function filters out items from one list of values using a predicate function to produce another list of values
• A reducer function operates on a list of values and collapses them into a single output value

We typically use one or more mappers and filters followed by one or more reducers to crunch data, e.g.: result = reduce(map(filter(input))).

Map

A mapper function maps a list of values to another list of values of the same length. Here are a few example mapper functions:

Map each string in a list to uppercase	Map each name in a list to a tuple of (last,first)
["foo","bar"] returns ["FOO ","BAR"]	["Andy Liu","Tia Tan"] returns [("Liu","Andy"),("Tan","Tia")]

Map every prime number in a list to True, every other number to False	Map each number in a list to its absolute value
[2,3,4,5,6] returns [True,True,False,True,False]	[20,-30,-27,45] returns [20,30,27,45]

Haskell provides a mapper function called map that accepts two parameters:

1. A function to apply to every element of a list
2. A list to operate on

The type signature of map is: map :: (a -> b) -> [a] -> [b]

• The first argument is a function that maps an individual item from a value of type a to a value of type b (a and b can be the same)
• The second argument is a list of type a
• The return value is a list of type b

We can define some functions to use with map:

-- mappy.hs
cube :: Double -> Double
cube x = x^3

one_over  :: Double -> Double
one_over x = 1/x

is_even :: Int -> Bool
is_even x = x `mod` 2 =0

ghci> :load mappy
[1 of 1] Compiling Main             ( mappy.hs, interpreted )
ghci> map cube [2,4,10]
[8,64,1000]
ghci> map one_over [2,4,8]
[.5,.25,.125]
ghci> map is_even [1,2,3,4,6]
[False,True,False,True,True]
ghci> map reverse ["mouse","cat","fly"] 
["esuom","tac","ylf"]

In the last invocation, we used Haskell’s library function reverse.

So how does the map function actually work? It’s simple. We can use pattern matching we have just learned to implement it.

-- map.hs
map :: (a -> b) -> [a] -> [b]
map func [] = []      
map func (x:xs) =
  (func x) : map func xs

Filter

A filter is a function that filters items from an input list to produce a new output list. Here are a few examples of filter functions:

Filter all odd numbers from an input list	Filter all spaces from a String
[1,2,3,4,5,6] returns [2,4,6]	"a man a plan a canal panama" returns "amanaplanancanalpanama"

Haskell provides a function called filter that accepts two parameters:

1. A function that determines if an item in the input list should be included in the output list
2. A list to operate on

The type signature of filter is: filter :: (a -> Bool) -> [a] -> [a]

• The first argument is a predicate function that determines if a value from the input list should be included in the output
• The second argument is a list of type a
• The returned list include all the items that passed the filter

The filter function can also be easily implemented using guards as follows:

filter :: (a -> Bool) -> [a] -> [a]
filter predicate [] = []
filter predicate (x:xs)
 | (predicate x) = x : (filter predicate xs)
 | otherwise = filter predicate xs

Reducers (foldl/foldr)

Let’s look at the last kind of the three: reducer. A reducer is a function that combines the values in an input list to produce a single output value.

Here are some reducer examples;

Reduce all the items from a list into a sum (or product)	Determine if any value in a list meets some requirement (e.g., is odd)
[10,3,7] returns 20	[2,4,6,8] returns False
[10,3,7] returns 210	[2,4,5,8] returns True

Count the # of people with each last name from a list of tuples	Append each word in a list into a single string, adding spaces in between
[("Li","Ari"),("Li","Sam"), ("Bui","Tom"), ("Li","Ann")] returns [("Li",3),("Bui",1)]	["I","like","candy"] returns "I like candy "

Each reducer takes three inputs:

1. A function that processes each of the elements
2. An initial “accumulator” value
3. A list of items to operate on

Haskell has two different reducer functions: foldl and foldr. Let’s learn about both!

Let’s first look at the pseudocode for foldl

To ease the understanding, this version is not functional code yet. We will see the real functional implementation later.

foldl(f, initial_accum, lst):
  accum = initial_accum
  for each x in lst:
    accum = f(accum, x)
  return accum

The core logic of foldl all happens around the accumulator variable accum:

• It is first set with the initial value initial_accum, the second argument to the function. The initial value can often be 0, 1 or an empty list
• Next, the accum is updated as we loop through each item the list. Each time the function f is used to “accumulate” the item to accum.
• In the end, the final value of accum is returned.

Here is one example f function for foldl (this time we use C++-like code to specify the typing):

int f1(int accum, int x)
  { return accum + x; }

If the function f1 is used in place of argument f, foldl computes the sum of list lst. When in doubt, create an example and try to evaluate with hand with the pseudocode!

The logic of foldr is similar to foldl with small changes. Here is its pseudocode:

foldr(f, initial_accum, lst):
  accum = initial_accum
  for each x in lst from back to front:
    accum = f(x, accum)
  return accum

There are two differences between foldr and foldl:

• The iteration order of list is reversed in foldr
• The order of arguments of f are different

Now let’s see the Haskell code for foldl:

foldl f accum [] = accum
foldl f accum (x:xs) =
  foldl f new_accum xs
 where new_accum = (f accum x)

foldr f accum [] = accum
foldr f accum (x:xs) =
  f x (foldr f accum xs)

As you can see, each new value x is “folded” into the accumulator as it’s processed.

• foldl is left-associative: f( ... f(f(accum,x1),x2), ..., xn)
• foldr is right-associative: f(x1, f(x2, ... f(xn, accum) ... ))

On the other hand, foldr is right-associative and, under some circumstances, allows processing infinite lists!

Influencer Alert: map-filter-reduce

Nowadays, virtually all modern languages now implement the map-filter-reduce paradigm. Here are some examples from Python, Java and Javascript

# Python map-reduce example
def adder(a,b):
  return a + b

nums = [1, 4, 9, 16]
roots = map(sqrt, nums)

sum_of_roots = reduce(adder, roots)

// Java map-reduce example
List<Double> nums =
  Arrays.asList(1.0, 4.0, 9.0, 16.0);

double sum_of_roots = nums.stream()
        .map((n) -> Math.sqrt(n))
        .reduce(0, Double::sum);

// JavaScript map-reduce example
function adder(total, num)
 { return total + num; }

var nums = [1, 4, 9, 16];
var roots = nums.map(Math.sqrt);
var sum_of_roots = roots.reduce(adder, 0);

Moreover, these functions form a new paradigm that has radically transformed the Internet, medicine, autonomous vehicles, and virtually every other field.

While mapping, filtering and reducing seem marginally useful when running on a small list of items on a single computer, they can be applied to a huge cluster of servers to process massive amount of data.

All of this is possible because these are pure functions that are stateless, so they can be run in parallel!

Advanced Topics in Functional Programming

Now we are in the Functional Programming home stretch, where we are learning some more advanced functional programming. Many concepts covered here are actually the core of FP, and that’s where things get interesting~

Lambda Functions

We start from lambda functions. By definition, a lambda function is just like any other function, but it does not have a function name.

For example, the corresponding lambda function of a normal function cube x = x^3 is \x -> x^3 in Haskell. The two functions are identical except the second does not have a name. Calling (\x -> x^3) 3 gives you the same result as cube 3.

Having lambda function is just another manifestation that functions are the first-class citizens in functional programming languages. It allows functions to be written as values without giving them name, just like values of other types (integers, strings, etc.)

People may wonder what practical benefit lambda function can bring. Sometimes it can make code easier to read. We can use lambdas in higher-order functions with we don’t want to bother defining a whole new named function.

For example, with lambda, we can create the following functions:

squarer lst = map (\x -> x^2) lst
cuber lst = map (\x -> x^3) lst

The squarer and cuber functions computes the square and cube of each item within the list. We don’t need to define separate helper functions and the logic can be understood by looking at the one-liner code.

Ok, let’s learn the syntax for defining a lambda function in Haskell. A lambda expression in Haskell is written as \param_1 ... param_n -> expression

• The lambda function starts with a backslash (\). It is chosen because its resemblence with the Greek letter lambda.
• Then you specify the name of one or more parameters, specified by spaces. These are called bound variables.
• The dash-greater sequence (->) follows the list of parameters, separates them with the rest of lambda.
• Finally, we have the function’s expression, which is what the function computes and returns.

Let’s see some examples in the Haskell interpreter:

ghci> (\x y -> x^3+y^2) 10 3
1009

Unfortunately we can’t just define a stand-alone lambda function in the interpreter because it will cause an error. But we can save the lambda function we created in a variable and/or call it.

In the example above, we create a lambda expression and call it with arguments x=10 and y=3. Thus it computes 10^3+3^2 and returns 1009.

Here are two examples with map:

ghci> map (\x -> 1/x) [3..5]
[0.3333333333333333,0.25,0.2]
ghci> map (\x -> take 2 x) ["Dog", "Cat"]
["Do","Ca"]

Also, we can assign a lambda function to a variable. After the assignment, we can call lambda just like we would call any other function.

ghci> a_func = \x y -> x++y
ghci> a_func [1,2,3] [4,5]
[1,2,3,4,5]

Some may wonder, does assigning lambda to variable defeat the purpose of having anonymous function? In some sense, it does seem so. However, looking from another angle, lambda functions can be regarded as more fundamental than named functions. Defining named function like a_func x y = x ++ y can be regarded as syntatic sugar of a_func = \x y -> x ++ y.

Next, let’s look at a fancier usage of lambda expression: using it to generate new functions! Look at the following code:

-- lambda.hs
wrapFuncWithAbs func = (\x -> abs (func x))

cubed x = x^3
twox = 2*x

Our function accepts an input function func, it builds a new function that computes y=abs(func(x)) and returns that new function as output.

ghci> :load lambda
[1 of 1] Compiling Main             ( lambda.hs, interpreted )
ghci> abs2x = wrapFuncWithAbs twox
ghci> abs2x (-42)
84
ghci> abscube = wrapFuncWithAbs (\z -> z^3)
27

Both abs2x and abscube are created from return values of wrapFuncWithAbs functions.

• The returned lambda assigned to abs2x is \x -> abs (twox x)
• Meanwhile, abscube is \x -> abs ((\z -> z^3) x)

Neat, right? We just generated two new functions from scratch!

Closures

Let’s take a closer look at what is happening with functions that generates other functions.

-- lambda.hs
slopeIntercept m b = (\x -> m*x + b)

twoxPlusOne = slopeIntercept 2 1
fivexPlusThree = slopeIntercept 5 3

In the example above, we created another function generator slopeIntercept:

• It accepts two parameters: m and b
• When called, it builds and returns a new function a new function that takes argument x and computes y = m*x + b

Then we create a function twoxPlusOne by calling slopeIntercept with m equals to 2 and b equals to 1. In the process, Haskell “captures” the specific values of m and b along with the expression \x -> m*x + b. This way, when we next call twoxPlusOne. Haskell will use m=2 and b=1.

ghci> :load lambda
[1 of 1] Compiling Main             ( lambda.hs, interpreted )
ghci> twoxPlusOne 9
19

The combination of a lambda expression with a snapshot of all “captured” values (like m and b) is called a closure.

When we create another function with the same generator, the other function will have its own generator as well, such as the fivexPlusThree above. Its closure has different values of m and b than the one of twoxPlusOne.

How do we decide what variables are captured as part of a closure? The answer is: “free variable”.

A free variable is any variable that is not an explicit parameter to the lambda. For example, in \x -> m*x + b, m and b are free variable, and x is not (because it appears in the parameter).

Variables within lambda that appears in the parameter also have a name, they are called “bound variable”. Thus “free variable” means that they are not “bound” to any of the parameter with the current lambda.

Formally, a closure is a combination of the two things:

1. A function of zero or more arguments that we wish to run at some point in the future
2. A list of “free” variables and their values that were captured at the time the closure was created

When a closure later runs, it uses the values of the free variables captured at the time it was created.

For the last sentence, it is true for Haskell, but the behavior may vary with language. We’ll see as we deep-dive into functions.

People may wonder where the free variables are stored, because they are still available for use after the function that create the closure has returned. If they were stored on the stack, that would not be possible.

The answer is that they are often stored on the heap. Unlike C and C++ where local variables are managed on the stack, languages that support lambda expression and closure usually store the relevant information on the heap so that they can be used after the creator function returns. The storage is managed by garbage collectors and will be freed when the runtime decide that the captured variables cannot be referenced by anyone.

Influencer Alert: Lambda and Closure

Nowadays, even in the languages that are not typically functional, you can often find that they support some form of lambda functions and closures. They are used when we want to pass a simple function to another function.

For example, in C++, we can use lambda to provide comparators for sorting:

// C++ code that uses a lambda to sort a bunch of
// Students in alphabetical order.

vector<Student> students;
// ...
sort(students.begin(), students.end(),
    [](const Student & a, const Student & b)
    {
       return a.getName() < b.getName();
    });

In C++, we need to explicitly specify the free variables to capture inside the pair of brackets (Note: C++ handles captures differently from most functional languages). Then follows the argument list within the parentheses and the function body in the braces.

The next example is the typical Javascript way to create callback for event handling. The lambda function is created with the function keyword

// javascript: Lambda function is called
// when the user clicks on the "big button"

// Select big button from HTML web page
var button = document.querySelector('#big-button');

// Specify the behavior when the button is clicked
button.addEventListener('click',
    function() { alert("A button was clicked!"); });

In Java, you can use lambda function to specify the action in created thread (rather than the traditional way of creating a class that implements the Runnable interface)

// Java thread example
public class LambdaThreadExample {
   public static void main(String args[]) {
    final int count = 50000;
    Thread t = new Thread(() -> {
      for(int i=0; i < count; i++)
         System.out.println("Child Thread: "+ i); });
   t.start(); // Start the background thread
   // Main Thread
   for(int j=0; j < 100000; j++)
      System.out.println("Main Thread: "+ j);
}

Currying

Here comes currying, a fundamental concept in functional programming. It might be confusing at first, but pay attention. Quite a few mysteries we encountered earlier will be solved if you understand it well.

By definition, currying transforms a function of multiple arguments to a series of functions of a single argument.

We’ll first use an example to get a feeling of what currying is like. Let’s say we have a following function f in a JS-like language:

function f(x, y, z) { return x + y + z; }

When we curry the function f, it’s converted to the following “nightmare”:

function f(x) {
  function g(y) {
    function h(z) {
      return x + y + z;
    }
    return h;
  }
  return g;
}

As we can see, the original function is converted into a series of nested functions:

• The number of nested level equals to the number of argument of the original function
• Each function takes a single argument in sequence, starting from the outmost one
• The outer functions returns the nested function in the next level
• The inner-most function does the original computation

Let’s say we wanted to call our original function like this: f(10, 20, 30)

If we want to achieve the same effect with curried version

temp_func1 = f(10);
temp_func2 = temp_func1(20);
final_result = temp_func2(30);

According to the closure we have just learned, each call above fills in one variable (x and y respectively). When we do the final call, only the last parameter is needed and we get the result we want.

Or more concisely, we can do it on a single line: final_result = f(10)(20)(30)

As it turns out, every function with two or more parameters can be represented in curried form!

It’s called “currying” because our friend, Haskell Curry, came up with the approach. (Well, in fact Moses Schönfinkel first had the idea several years before. It could have been called Schönfinkelisation…)

Formally, Currying is the concept that you can represent any function that takes multiple arguments by another that takes a single argument and returns a new function that takes the next argument, etc.

It turns the function y = f(a, b, c) into y = ((f_c a) b) c.

Each function takes one argument and returns another function as its result (except for the last function which returns the result).