Gain insights into functional programming with OCaml and Haskell, explore lambda calculus, abstractions, and dataflows, and learn to apply these concepts to real-world scenarios, contrasting with Java.

ocaml_utop_haskell.tar.gz

OCaml

Functional programming is a paradigm that builds complete applications by breaking down programs into constituent functions that empowers developers to build fast, bug-resistant applications.

You’ll be introduced to functional programming with illustrative examples contrasting the more widely used imperative programming paradigm. You’ll review lambda calculus as an introduction to expressions, the building blocks of functional programs. You’ll continue with abstractions and complex data types before exploring common computation patterns. Next, you’ll learn how dataflows create whole programs out of existing functions. Finally, you’ll finish by applying your functional programming knowledge to various real-world scenarios. At each step, you’ll learn OCaml and Haskell, while contrasting imperative programming with Java.

By the end of this course, you’ll be prepared to use functional programming in your daily work and have the framework to know when to use either imperative or functional paradigms.

Mastering Functional Programming with OCaml and Haskell

Functional programming is based on a theoretical foundation called [lambda calculus](https://en.wikipedia.org/wiki/Lambda_calculus) (also written as $\lambda$-calculus) , invented by Alonzo Church. The easiest way to understand lambda calculus is to think of it as an idealized bare-bones functional programming language. In other words, take OCaml or any similar functional programming language and strip down all features that do not contribute to the ability to do functional programming. What remains is essentially lambda calculus.




# Lambda expressions

The expressions of lambda calculus, called lambda expressions, can be built from either one of the following three rules:

* A variable — `x`, `y`, `myvar`, and so on—is a lambda expression.
* Given `x` is a variable and `e` is a lambda expression. A function abstraction is a lambda expression.
* If `e1` and `e2` are lambda expressions, a function application, `e1` `e2`, is also a lambda expression.

We can use the Backus–Naur form (BNF) notation to express the formal syntax of lambda calculus more succinctly.

```haskell
<var> ::= x | y | myVar | ...
<lambda_expr> ::= 
  <var>
| λ <var> . <lambda_expr>
| <lambda_expr> <lambda_expr>
```

Moreover, we can use parentheses in lambda expressions to avoid ambiguity.

As we can see, lambda calculus centers around two concepts—function abstraction and function application—drawn directly from mathematical functions. **Function abstraction** formulates the way we declare a mathematical function of one argument, for example $f(x) = x$. Likewise, in lambda calculus, $\lambda x.\, x$ represents a function that takes an input `x` and returns itself. This is the identity function. 
Function application resembles how we apply a function to an argument.
For instance, we can apply $f(x) = x$ to $2$ and obtain $f(2) = 2$. 
Similarly, $(\lambda x.\, x)\,y$ represents the act of applying the function $\lambda x.\,x$ to $y$.

Despite having only variables and functions as language elements, lambda calculus is as powerful as any general-purpose programming language, such as C, Python, Java, and OCaml. 
In particular, lambda calculus is powerful enough to encode and implement operations for numbers, boolean values, and data structures like pairs and lists in lambda calculus. Read about [Church encoding](https://en.wikipedia.org/wiki/Church_encoding) for more details. In fact, we could even write a microservice in lambda calculus! Admittedly, the code would likely look dreadfully complicated.

# Lambda reduction

To run a program means to reduce the lambda expression denoting the program until the expression can not be further reduced. The fully reduced expression is the value of the program.
A function abstraction such as $\lambda x.\,x \, x$ or a variable $x$ is fully reduced.
Conversely, a function application of the form $(\lambda x.\,e1)\,e2$ can be reduced further by substituting the function's formal argument `x` with the actual argument `e2` into the function body `e1`. Such a lambda expression is called a **reducible expression** or **redex**. 

For example,

$(\lambda x.\,x \,  x ) \,y$

$y \, y$


Now an interesting question arises, "Can we fully reduce any lambda expression in a finite number of steps?"
The answer is no. There are lambda expressions that can never be fully reduced,  $(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$ is one . This is the identity function. This function application evaluates to itself. 

$(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$ 

$(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$

$(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$

$\ldots$


If you think about it, this makes a lot of sense. Lambda calculus allows us to formulate undefined values in the same way we can write Java or Python programs 
that run in an endless loop.

# Functions are first-class citizens

One fascinating aspect of lambda calculus is that there is no distinction between a variable and a function - both are expressions. 
Variables or functions can be freely passed as an argument to another function or returned from another function.
For example, $(\lambda x.\,x \, z) \, (\lambda y. \, y)$ represents a function application in which we apply the $\lambda x.\,x \, z$ function to the $\lambda y. y$ function. Functions are said to be first-class citizens in lambda calculus. 


Functional programming languages are built on this idea and treat functions as first-class citizens. In these languages, functions can be assigned to variables, passed to functions, or returned from functions like we usually do with numbers, boolean values, or strings. In contrast, in imperative programming languages, functions are second-class citizens. That means functions can’t be used to construct expressions. We can neither assign functions to variables nor pass functions as arguments to other functions.

The concept of first-class citizens is one of the big ideas of functional programming. It is the foundation for higher-order functions, a hallmark of functional programming.

# Currying and partial application

Lambda calculus only allows functions to have exactly one argument. However, a great insight of lambda calculus is that we can represent a multi-argument function as a chain of nested single-argument functions. This technique is known as [**currying**](https://en.wikipedia.org/wiki/Currying).

To illustrate, suppose we want to formulate a function that accepts two arguments — $x$ and $y$ — then applies the function $f$ to them, and returns the result. Using currying, we can define it as a chain of two single-valued functions, $\lambda x.\lambda y.\, f \, x \, y$.



Since $\lambda x.\lambda y.\, f \, x \, y$ is actually two nested functions, applying it to two arguments, $u$ and $v$, means we first apply it to $u$ and then $v$.

$(\lambda x.\lambda y.\, f \, x \, y) \, u \, v$

$(\lambda y.\, f \, u \, y) \, v$

f u v

Another fascinating aspect of currying is that it enables partial application. We don’t have to apply the function,  $\lambda x.\lambda y.\, f \, x \, y$, to two arguments. Instead, we partially apply it to a single argument, $u$, and stop entirely. What we obtain is a unary function, $(\lambda y.\, f \, u \, y) \, v$, where we fix $x$ with $u$.


Currying together with partial application is another big idea of functional programming. OCaml and Haskell rely on currying to represent multi-argument functions.

# Reduction strategies

We previously saw that a lambda expression of the form $(\lambda x\,e1)\,e2$ is a redex or reducible expression.
But what if the argument is also a redex? For example, $(\lambda x.\,x \,  x) \, ((\lambda y.\,z) \,  u)$ is itself a redex. However, the argument, $(\lambda y.\,z) \,  u$, is also a redex.

We could use either of the following two strategies:
* Reduce the e2 argument first and then substitute x with the fully reduced e2 in e1. This reduction strategy is often termed **call-by-value**.
* Substitute x with the entire expression g as is. This reduction strategy is also known as **call-by-name**.


The following compares these two strategies side-by-side:

Get familiar with the basics of lambda calculus, the foundation of all functional programming languages.


Lambda Calculus: The Foundation of Functional Programming

Get familiar with the basics of lambda calculus, the foundation of all functional programming languages.

Introduction

Expressions: Building Blocks of Functional Programs

Building Abstractions with Functions

Compound Data Types

Common Computation Patterns

Dataflow Programming with Functions

Applying Functional Programming to Various Domains

Conclusion

Appendix

Lambda Calculus: The Foundation of Functional Programming

Lambda expressions