Lecture 04
2022-10-05 | Week 2 | by Boyan Ding
Boyan here! This continues from last lecture, and covers the slides after 97 Intro to FP deck. As always, please give me feedback on the notes!
Table of Contents
Map, Filter and Reduce (continued)
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.
Each reducer takes three inputs:
- A function that processes each of the elements
- An initial “accumulator” value
- 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
accumis updated as we loop through each item the list. Each time the functionfis used to “accumulate” the item toaccum. - In the end, the final value of
accumis 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
fare 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.
foldlis left-associative:f( ... f(f(accum,x1),x2), ..., xn)foldris right-associative:f(x1, f(x2, ... f(xn, accum) ... ))
On the other hand, foldr is right-associative.
Influencer Alert!!
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 lambda function in the interpreter because it will cause an error. But we can call the lambda function we created.
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 Boyan’s opinion, 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
abs2xis\x -> abs (twox x) - Meanwhile,
abscubeis\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:
mandb - When called, it builds and returns a new function a new function that takes argument
xand computesy = 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:
- A function of zero or more arguments that we wish to run at some point in the future
- 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).
A pseudocode that represent the logic of currying can be written as:
Curry(Function f)
e = The expression/body of function f
For each parameter p from right to left:
f_temp = Define a new lambda function with:
1. p as its only parameter
2. e as its (expression)
e = f_temp
return f_temp
Let’s use the procedure above to curry the function mult3 x y z = x*y*z
- At first,
eis equal tox*y*z - Then we enter the for loop
- In the first iteration,
zis the parameter to be handled.f_temp = \z -> x*y*z - Next, we handle
yandf_temp = \y -> (\z -> x*y*z) - Finally, we handle
yand we getf_temp = \x -> (\y -> (\z -> x*y*z))
- In the first iteration,
Thus, the curried version mult3c = \x -> (\y -> (\z -> x*y*z))).
Let’s see how we call our curried function with x=2, y=3 and z=5!
ghci> mult3c = \x -> (\y -> (\z -> x*y*z)))
ghci> f1 = mult3c 2
ghci> f2 = f1 3
ghci> result = f2 5
30
So, what actually are f1 and f2?
f1 is obtained by calling the lambda of mult3c with x=2. Thus we replace the occurrences of x inside the lambda function with 2 and remove the \x -> at the beginning. f1 is: \y -> (\z -> 2*y*z).
When a inner lambda has the same parameter name as the outer one. The inner one takes precedence and shadows the outer one. In this case, the shadowed parameter will not get replaced. For example, when we evaluate (\x -> ((\x -> x) (x + 1))) 3, we will get ((\x -> x) (3 + 1)).
Once again, when we repeat the process, we can get f2 = \z -> (2*3*z), and finally result = 2*3*5, thus 30.
In fact, every time you define a function of more than parameter in Haskell, Haskell automatically and invisibly curries it for you.
This is evidenced by the fact that even if you replace the mult3c above with the “normal” mult3 x y z = x*y*z, you will get the same result. You can also legally execute (((mult3 2) 3) 5) in Haskell and get 30.
Surprising fact: Our usual way of calling functions mult3 2 3 5 looks like a single call with three arguments, but it’s really three calls to three different functions! What happen’s is exactly identical to (((mult3 2) 3) 5), thus we know function invocation is left associative.
Also, now we can reveal the fact about Haskell function type signatures:
Remember those ugly (and maybe confusing) Haskell type signatures?
mult3 :: Double -> Double -> Double -> Double
mult3 x y z = x * y * z
Well, here’s what they should really look like given that all functions are curried (thus mult3 is a three-level nested function that returns a function at each outer level):
mult3 :: Double -> (Double -> (Double -> Double))
mult3 x y z = x * y * z
Although the latter form looks more fundamental, it is even uglier. That’s why we used smore syntactic sugar to remove the parentheses. (We can regard the -> “operator” in type signatures as right-associative)
People may ask, why does Haskell curry function? We think there are two primary reasons:
- First, it enables partial function application (which we we’ll see more below)
- But mostly it appears to be motivated by theorists! It can facilitate program analysis and other stuff and it is consistent with the lambda calculus, the mathematical foundation of functional programming.
Partial Function Application
When you call a function with less than the full number of arguments this is called “Partial Function Application” or “Partial Application.”
Formally speaking, partial function application is an operation where we define a new function g by combining:
- An existing function
fthat takes one or more arguments, with - Default values for one or more of those arguments
The new function g is a specialization of f, with hard-coded values for some of f’s parameters.
Once defined, we can then call g with those arguments that have not yet been hard-coded.
Partial function application is deeply related with currying we have just learned. In fact, when we used ((mult3 2) 3) 5 earlier, we are implicitly doing partial function application. But let’s see more examples:
ghci> mult3 x y z = x*y*z
ghci> partial = mult3 2
ghci> partial 3 5
30
ghci> multby10_20 = mult3 10 20
ghci> multby10_20 3
Here, we are creating two specialized functions partial y z = 2*y*z and multby10_20 z = 10*20*z with partial application.
Partial function applications can be useful when combined with pre-existing functions and operators. Let’s see the following examples:
ghci> add5 = (+) 5
ghci> add5 100
105
All of Haskell’s operators are just functions! So the + sign is basically a function of two arguments.
Surrounding an infix operator with a pair of parentheses converts it to the prefix form which gives you identical behavior to a normal function.
ghci> map (/ 10) [100,200,300]
[10.0,20.0,30.0]
ghci> map (10 /) [100,200,300]
[0.1,5.0e-2,3.333333333333333e-2]
Haskell also allows you to apply partial application to either operands of infix operators. The function produced by the first line is equivalent to \x -> x / 10, while the second line produces \x -> 10 / x. You can see the behavior by reading the result returned by the map function.
Here are more examples:
ghci> filter (>= 6) [2,4,6,8,10,3]
[6,8,10]
ghci> map (++ " is LIT!") ["CS32","CS131"]
["CS32 is LIT!","CS131 is LIT!"]
ghci> filter (`elem` ['A'..'Z']) "Not Every Resistor Drives current"
"NERD"
In the last example, the pair of backticks turns a function with two arguments into an infix operator so that you can supply the second argument with partial application.
We can even use partial function application to define a partially-specified mapper function:
ghci> cuber = map (\x -> x^3)
ghci> cuber [2,3,5]
[8,27,125]
As you can see, with partial function applications often we don’t have to define a full function or lambda to do complex processing!
Algebraic Data Types
Algebraic Data Type (ADT) is the term we use in functional programming to describe a user-defined data type that can have multiple fields.
The closest thing to algebraic data types would be C++ structs and enumerated types. We use algebraic data types to create complex data structures like trees.
In Haskell, we use keyword “data” to define algebraic data types.
The simplest algebraic data types are just like C++ enums:
-
The pipe ( ) character means “OR” - Each choice for a given type is called a “variant” or a “kind”
data Drink = Water | Coke | Sprite | Redbull
data Veggie = Broccoli | Lettuce | Tomato
data Protein = Eggs | Beef | Chicken | Beans
For the Protein type, its equivalent in C++ would be:
enum Protein { Eggs, beef, chicken, Beans };
We can also define more complex ADTs where each variant also has one or more fields (like C++ struct).
data Meal =
Breakfast Drink Protein |
Lunch Drink Protein Veggie |
Dinner Drink Protein Protein Veggie |
Fasting
The definition of first variant Breakfast means that it is comprised of Drink and Protein fields. Its equivalent in C++ would be:
struct Breakfast {
Drink d;
Protein p;
}
The only difference is, the fields in Haskell does not have a name, and they are distuished by the order they appear in the definition.
Note that the variants with and without fields can coexist within a single ADT, the Fasting above is just an example.
Here are some examples to define variables with ADT:
careys_meal = Breakfast Redbull Eggs
pauls_meal = Lunch Water Chicken Broccoli
davids_meal = Fasting
Syntax
We use another example to introduce the syntax of Algebraic Data Types
-- algebraic.hs
data Color = Red | Green | Blue
data Shape =
Circle
Float Float -- x, y
Float -- radius
Color |
Rectangle
Float Float -- x1, y1
Float Float -- x2, y2
Color
- To define a new ADT, we use the
datakeyword - The syntax can be represented as
data TypeName = Variant1 | Variant2 | ... | VariantN - The initial of type names should be capitalized (to differentiate with type variables)
- The initial of variant names should be capitalized as well.
- The general syntax for defining a variant that has fields is:
VariantName Type1 Type2 ... TypeN
Each time you define a variant with fields, Haskell implicitly creats a “constructor” that can be used to create a new variable. For example, the code above a Circle constructor with four parameters (three Floats and a Color) to create a new Circle.
We can add the keywords deriving Show at the end of a definition to enable us to print out variable values in GHCi. This is simply a hack that makes our life easier when debugging in GHCi.
If we added deriving Show to both Color and Shape, we can test with the types in GHCi:
ghci> :load algebraic
[1 of 1] Compiling Main ( lambda.hs, interpreted )
ghci> c = Circle 5 6 10 Red
ghci> c
Circle 5.0 6.0 10.0 Red
ghci> r = Rectangle 0 0 5 6 Blue
ghci> r
Rectangle 0.0 0.0 5.0 6.0 Blue
ghci> :t r
r :: Shape
ghci> colors = [Red, Red, Blue]
ghci> colors
[Red,Red,Blue]
Note that the fields of a variant have no names! That means we must use their order/position to identify them.
Pattern Matching with ADT
In functional languages, we use pattern matching to process algebraic variables.
Let’s see an example with our shapes. We first update our Shape algebraic type a bit and add a new “Shapeless” type of shape.
-- shapes.hs
data Shape =
Shapeless
| Circle
-- x y rad
Double Double Double
| Rectangle
-- x1 y1 x2 y2
Double Double Double Double
deriving Show
getArea :: Shape -> Double
getArea Shapeless = 0
getArea (Circle _ _ r) = pi * r^2
getArea (Rectangle x1 y1 x2 y2) =
(abs (x2-x1)) * (abs (y2-y1))
We focus on the getArea function:
- The first line is the type signature. As this functions operates on various types of
Shape, this definition makes sense. - Then follows the actual pattern matching
- The first line means: “If the user passes in a Shapeless variable, then always return zero”.
- The second line handles the
Circlecase. It gets the third field (radius), placing it into variablerand computes the area. - The last line handles
Rectangle. It extracts the fields from the data structure and computes the area according to the width and height.
We can combine pattern matching on ADT with lists and tuples to create complex patterns. For example, the following function counts the occurrences of Circle within a list of Shape without using map, filter or foldl.
count_circle :: [Shape] -> Integer
count_circle [] = 0
count_circle ((Circle _ _ _):xs) = 1 + count_circle xs
count_circle (_:xs) = count_circle xs
Exercise: Implement count_circle with map, filter and foldl respectively.
Creating Trees with ADT
Let’s examine a more interesting use of ADTs – creating a binary search tree.
We’ll start by looking at the definition of a tree node ADT.
-- bst.hs
data Tree =
Nil |
Node String Tree Tree
A tree data type has two possible variants:
- An empty variant indicating that there is no node, like a
nullptr - A node variant representing actual nodes.
In this definition, each Node holds a String value, and two other tree data items that can be either Nil or Node. The first one is the left child of the node, and the second one is the right child. So this is a binary tree.
ghci> :load bst
[1 of 1] Compiling Main ( bst.hs, interpreted )
ghci> empty_tree = Nil
ghci> one_node = Node "Lit" Nil Nil
ghci> r = Rectangle 0 0 5 6 Blue
ghci> left_child = Node "Boomer" Nil Nil
ghci> right_child = Node "Zoomer" Nil Nil
ghci> root = Node "Cheugy" left_child right_child
ghci> root
Node "Cheugy" (Node "Boomer" Nil Nil) (Node "Zoomer" Nil Nil)
In the end of the code above, we created a tree with three nodes.
With this tree structure, we can implement search algorithm on this BST.
We’ll use a classic recursive search function and pattern matching.
search Nil val = False
search (Node curval left right) val
| val == curval = True
| val < curval = search left val
| otherwise = search right val
Ok, now let’s see how to create a function that adds a new node to a tree.
But this isn’t so easy, because in functional languages, we can’t modify existing values/variables. Suppose we create a node N and we want to make it the child of existing node M. So we can’t just find a node M and change its left or right child to point to the new N!
The strategy is, we want to create a new node M’, let it point to N and replace the node M we need to change.
But wait… Now the new node M is not part of the tree either. But we can just carry it on to create a new node to replace M’s parent. Eventually we can do this all the way to the root, and at that point, we can forget about the old tree.
The following Haskell code implements the logic:
insert Nil val =
Node val Nil Nil
insert (Node curval left right) val
| val == curval =
Node curval left right
| val < curval =
Node curval (insert left val) right
| val > curval =
Node curval left (insert right val)
This method sounds a little bit wasteful, because we need to create new nodes all the way up. However, if we think carefully about the process, we’ll find that to add a new node, we just need to generate replacement nodes for the nodes between our new node and the root. Then if a tree is balanced with n nodes, we need to create just log2(n) new nodes!
Meanwhile, with the creation of the new node, the old nodes will no longer be used. This is where “Garbage Collection” comes in.
Garbage Collection is a language feature that automatically reclaims unused variables, and all functional languages have built-in Garbage Collection.
We’ll learn more about GC later in the course, but the important thing is that GC doesn’t impact Big-O!
Although here we see that immutable tree is efficient (in the sense it does not change the Big-O bound of operations). It does not apply to all data structures.
For example, if hash tables are implemented as immutable, the insertion will be inefficient because you must regenerate the full array of n buckets every time you add a new item.
Influencer Alert: Immutability
Many languages now provide immutable data structures – it helps simplify code, reduce bugs, and ease multi-processing.
Examples include Google’s Guava library for Java, and immutable.js for JavaScript.
// Java Guava immutability example
Set<Integer> oldSet = ImmutableSet.of(1,2,3,4);
// Generate a whole new set, with 5 added to it
Set<Integer> newSet = new ImmutableSet.Builder<Integer>().addAll(oldSet)
.add(5)
.build();
// JavaScript immutable.js example
// Create a new immutable set of 1-4
const oldSet = Immutable.Set([1,2,3,4]);
// add returns a new set & doesn't change orig.
const newSet = oldSet.add(5)
Summary
In summary, here are what we have learned about functional programming
- Every function must take an argument.
- Every function must return a value.
- Functions are “pure” and have no side effects
- Calling the same function with the same input always returns the same result.
- All variables are “immutable” and can never be modified!
- Functions are just like any other data and can be stored in variables and passed as arguments.
And as we have seen along the way, while there are no purely functional languages in mainstream use, the paradigm has influenced every major language.
This concludes our introduction to Haskell and functional programming. Hope you had fun!