Haskell Book: Chapter 1 — All You Need is Lambda

Big Ideas

Haskell — We write Haskell because we are not geniuses. We have limited working memory, and Haskell allows us to offload a lot of work to the compiler.

Learning — Spaced repetition and iterative deepening are powerful tools for learning a subject. The book is written with these two concepts in mind.

Functional Programming — The essence of functional programming is the idea that a program is a combination of expressions.

Functions — Functions are nothing more than a mapping between a set of inputs to an output.

Terminology / Concepts

Referential Transparency — A referentially transparent function is a function that, given the same input, returns the same output in all contexts and has no side effects. We can replace a call to a referentially transparent function with the value returned by that function without any change whatsoever to our program’s semantics. Referentially transparent functions are also known as pure functions.

Abstraction — An abstraction is a term from lambda calculus that is synonymous with a lambda. The term abstraction is particularly well-fitting as an alias for a lambda. A lambda generalizes — i.e., abstracts — over a pattern. The stuff that is the same is encapsulated in the function’s body, and the stuff that’s different is passed in as arguments to the abstraction.

Alpha Equivalence — Alpha equivalence is the reason why \xy.xy is equivalent to \ab.ab. Alpha equivalence does not apply to free variables (defined below).

An abstraction consists of a head and a body. The head contains the parameters that will be bound to values when function is applied.

Beta Reduction — Beta reduction is the process of applying a lambda expression to an argument, and in the process “simplifying” the expression.

Beta Normal Form — Beta normal form is when you can no longer beta reduce a lambda term. You’ve either run out of functions to apply, or ran out of arguments to apply the function to. The lambda term (\x.xz) is in beta normal form. However, the term (\x.xz)z can be beta reduce into (zz).

Application is Left Associative — This means that (\x.x)(\y.y)z can be fully parenthesis as ((\x.x)(\y.y))z.

Free Variable — A free variable is a variable that is referenced / used in the function body, but is not bound in the function head.

Currying — There is no such thing as a lambda that takes multiple arguments. Every lambda takes on argument and returns one result. The syntax (\xy.x + y) is actually syntactic sugar for (\x.\y.x + y). In Haskell, every function is curried — every function takes on argument and returns one result, which may happen to be another function that takes one argument, etc. etc.

Combinator — A combinator is a function in which all the variables in the function body are bound in the function head. In other words, there are no free variables.

Divergence — Divergence is a term used to describe a function that never terminates. The lambda term (\x.xx)(\x.xx) is diverges. If we reduce this function, we get the same term again, ad infinitum. In programming, a function that diverges never terminates. It’s value is undefined, and we’ve encountered bottom / a bug.

My Thoughts

The big idea with functional programming is that a program is a combination of expressions. Almost everything in a functional programming language is an expression. The reason why this is important is that, if everything is the same type (loosely speaking), composability is increased. I can composed an expression out of expressions, each of which can be composed of further expressions — I can do this easily because everything is an expression. It is the same idea with SQL, where the only data structure is a table — SQL queries return another table, which can be further queried.

In imperative languages, some things are statements, which I can’t compose. Object-oriented languages are actually fairly composable, because almost everything is an object. (However, they suffer the huge downside of mutable state).

Show your support

Clapping shows how much you appreciated Steven Leiva’s story.