Haskell programming from first principles

Introduction

Why Haskell? Whatever your reason, Haskell can help you think differently about writing programs. It’s a pure, functional language with a rich type system. Because of these features, Haskell can be a little difficult to learn, at first, but only because it is foreign, not because it takes a genius to understand and write in it.

The best frame of mind for learning Haskell is to not translate what you see in Haskell into your favorite language, but, rather, try to think in terms of Haskell directly. Don’t worry if you don’t understand everything the first time around; reviewing, recalling, and revisiting information is an efficient way to learn.

Work the exercises. Try to reason and predict the result before putting the code into the compiler. Wrestle with the exercises, but don’t get too hung up; move on and come back later. Don’t skip chapters, even if you’ve programmed before. Develop an intuition about Haskell’s syntax, conventions, and quirks.

Chapter 1: All You Need is Lambda

  • lambda calculus
    • a method of computation or reasoning
    • developed by Alonzo Church in the 1930s
  • functional programming
    • a programming paradigm that uses functions as the primary organizing structure
    • programs are a combination of expressions
      • expressions are values, variables, and functions
      • functions are expressions that apply to inputs and can be reduced or evaluated
    • first class functions
      • functions that can be used as values or inputs to other functions
    • pure functional language
      • strict use of lambda calculus
      • referential transparency: a function will always evaluate to the same value given the same inputs
  • abstraction
    • composing programs from smaller programs or functions that factor out certain patterns and can be applied in a variety of places

What’s a function?

A function is a mapping between a unique input value to a unique output value. Given the same input values, a pure function will always return the same output value.

Lambda expressions

Lambda calculus has three fundamental terms: expressions, variables, and abstractions.

Expressions can be a variable, an abstraction, or mix of the two. Variables are just names for inputs. Abstractions are functions. They have a head (or lambda) and a body. Arguments are input values. The head consists of a $\lambda$ and a variable. The body is an expression. A simple lambda abstraction looks like this (it’s also an anonymous identity function):

$$ \lambda x.x $$

The parameter, $x$, binds all instances of $x$, in the body of the function. When a value is assigned to $x$, all instances of $x$ will also be assigned that value.

Evaluating a function is called application; we apply the body to the arguments. The power of abstractions (or functions) lies in their use of names as placeholders for values. Once a function is applied, the variables are replaced by their values.

Alpha equivalence

Two lambda abstractions are alpha equivalent if the structure of each abstraction is the same. The names of the variables don’t negate the equivalence. In other words, the following abstractions are alpha equivalent:

$$ \lambda x.x = \lambda y.y $$

Beta reduction

Beta reduction is the evaluation of an abstraction and eliminating the head of the abstraction once the arguments have been applied to the body.

$$ ( \lambda x.x )( \lambda y.y ) \newline [x := (\lambda y.y)] \newline \lambda y.y $$

Beta reductions are left associative, meaning that the leftmost abstraction is evaluated first. Not all variables in the body need to be bound to an argument in the head. These are called free variables.

Free variables

Free variables are variables not bound by the head. However, alpha equivalence doesn’t apply to free variables. This is not alpha equivalent:

$$ \lambda x.xz \stackrel{\not \alpha}{\iff} \lambda x.xy $$

While, this is alpha equivalent:

$$ \lambda x.xz \iff \lambda y.yz $$

Multiple arguments

Each lambda only binds one argument. The leftmost lambda is evaluated first, followed by the second, and so on until no more lambdas are left. Currying is the beta reduction of nested lambdas.

$$ \lambda xy.xy = \lambda x.(\lambda y.xy) $$

Bookmark at page 14 (Chapter 1.7)