Functional Fundamentals

Alpha conversion (also written \(\alpha\)-conversion) is a way of removing name clashes in expressions. A name clash arises when a \(\beta\)-reduction places an expression with a free variable in the scope of a bound variable with the same name as the free variable. — Greg Michaelson, An Introduction to Functional Programming Through Lambda Calculus When we are performing a \(beta\)-reduction it is possible that the variable name in an inner expression is the same as a variable name in an outer expression. For example, consider ...

Formally, beta reduction (also written \(\beta\)-reduction) is the replacement of a bound variable in a function body with a function argument. The purpose of \(\beta\)-reduction is to compute the result of a function by function application using specific rules. More formally, the beta reduction rule states that a function application of the form \((\lambda x.t)s\) reduces to the term \(t[x := s]\). The term \(t[x := s]\) means that all instances of \(x\) in \(t\) are replaced with \(s\). The \(\rightarrow\) syntax is used as a shorthand for beta reduction. We can specify beta-reduction explicitly using the notation \((\lambda x.t)s \rightarrow t[x := s]\), which means that the beta reduction of \((\lambda x.t)s)\) is \(t[x := s]\). The beta reduction removes the \(\lambda\) symbol and resolves to the function’s body with the argument \(s\) substituted into the body. ...

The purpose of eta reduction (also written \(\eta\)-reduction) is to drop an abstraction over a function to simplify it. This is possible when there is nothing more that a function can do to its argument. For example, imagine that we have a simple function \( f\ x = g\ x \). Both \(g\) and \(f\) take the same argument, \(x\), and the function application function results in the same value (specified by the equality symbol). Since both \(f\) and \(g\) take the same argument and produce the same result, we can simplify the equation to just \(f = g\). In lambda calculus, this simplification is called \(\eta\)-reduction. ...

Three common terms come up whenever we talk about functions: domain, range, and codomain. This post clarifies what each of those terms mean. Before we start talking about domain and range, lets quickly recap what a function is: A function relates each element of a set with exactly one element of another set (possibly the same set). Math is Fun That is, a function relates an input to an output. But, not all input values have to work, and not all output values. For example, you can imagine a function that only works for positive numbers, or a function that only returns natural numbers. To more clearly specify the types and values of a functions input and output, we use the terms domain, range, and codomain. ...

I’m documenting my journey from functional neophyte to (hopefully) functional programmer by writing a series of blog posts on the topic. So far I’ve covered what functional programming is and why you would want to learn about it. In this post, I’m going to describe the resources I will be using to become functionally fluent. Although I have previously said I’m learning about functional programming, I should be more specific. I do already have some middling experience with Clojure and Lisp, but I have too many battle scars from running dynamic languages in production to go down that path again. At this point in my career, my experience dictates that any new code I write will be statically typed. Because of this bias, I’m going to approach learning functional programming through the lens of statically typed functional languages. My learning plan will reflect that and help narrow the scope of this project. ...

I previously talked about what functional programming is by comparing it to other programming paradigms. This post expands on that post to talk specifically about practical differences between functional programming and the paradigm most of us are intimately familiar with — imperative. This post is punctuated with some quotes from the book An Introduction to Functional Programming Through Lambda Calculus. It’s worth noting that each of these practical differences are enabled because of the power of referential transparency. ...

Having covered what functional programming is, I wanted to spend a minute or two discussing why I want to learn functional programming in the first place. I’m sure we have all heard vague things about “side-effects”, “immutability”, and “composition”, but I wanted to dive a bit deeper on the topic to describe what — to me — is important about functional programming. Referential Transparency The key differentiating feature of (pure) functional programs is that they provide referential transparency. An expression is said to be referentially transparent if it can be replaced with its corresponding value without changing the program’s behaviour. ...

I’m documenting my journey from functional neophyte to (hopefully) functional programmer by writing a series of blog posts on the topic. This is the first post describing what, exactly, the word functional programming means. Functional programming is a programming paradigm that lives alongside other programming paradigms. None of these paradigms have a precise, unanimous definition or standard, and there is not real agreement on which paradigm is better or worse for building particular types of software. ...