Oct 19

Haskell Book - Christopher Allen

Haskell User's Guide - Release 8.8.1

Haskell Slides

Haskell Chapter-1

Haskell Chapter-2

Haskell Chapter-3

Haskell Chapter-4

Haskell Chapter-5

Haskell Chapter-6

Haskell Chapter-7


What is Haskell?

Haskell is a widely used purely functional language. Functional programming is based on mathematical functions. Besides Haskell, some of the other popular languages that follow Functional Programming paradigm include: Lisp, Python, Erlang, Racket, F#, Clojure, etc. Haskell is more intelligent than other popular programming languages such as Java, C, C++, PHP, etc.

Haskell’s pure functional basis also lends it a high degree of abstraction and composability. Abstraction allows you to write shorter, more concise programs by factoring common, repeated structures into more generic code that can be reused. Haskell programs are built from separate, independent functions, kind of like LEGO®: the functions are bricks that can be assembled and reassembled.

Features of Haskell

Haskell is a widely used purely functional language. Here, we have listed down a few points that make this language so special over other conventional programming languages such as Java, C, C++, PHP, etc.

  • Functional Language − In conventional programing language, we instruct the compiler a series of tasks which is nothing but telling your computer "what to do" and "how to do?" But in Haskell we will tell our computer "what it is?"
  • Laziness − Haskell is a lazy language. By lazy, we mean that Haskell won't evaluate any expression without any reason. When the evaluation engine finds that an expression needs to be evaluated, then it creates a thunk data structure to collect all the required information for that specific evaluation and a pointer to that thunk data structure. The evaluation engine will start working only when it is required to evaluate that specific expression.
  • Modularity − A Haskell application is nothing but a series of functions. We can say that a Haskell application is a collection of numerous small Haskell applications.
  • Statically Typed − In conventional programing language, we need to define a series of variables along with their type. In contrast, Haskell is a strictly typed language. By the term, Strictly Typed language, we mean the Haskell compiler is intelligent enough to figure out the type of the variable declared, hence we need not explicitly mention the type of the variable used.
  • Maintainability − Haskell applications are modular and hence, it is very easy and cost-effective to maintain them.

What is functional programming?
Functional programming is a computer programming paradigm that relies on functions modelled on mathematical functions. The essence of functional programming is that programs are a combination of expressions. Expressions include concrete values, variables, and also functions. Functions have a more specific definition: they are expressions that are applied to an argument or input, and once applied, can be reduced or evaluated. In Haskell, and in functional programming more generally, functions are first-class: they can be used as values or passed as arguments, or inputs, to yet more functions.

Functional Programming and Haskell
The main points are:
• Functional programming is based on expressions that include variables or constant values, expressions combined with other expressions, and functions.
• Functions have a head and a body and are those expressions that can be applied to arguments and reduced, or evaluated, to a result.
• Variables may be bound in the function declaration, and every time a bound variable shows up in a function, it has the same value.
• All functions take one argument and return one result.
• Functions are a mapping of a set of inputs to a set of outputs.
Given the same input, they always return the same result.
These things all apply to Haskell, as they do to any pure functional languages, because semantically Haskell is a lambda calculus.
Haskell is a typed lambda calculus — more on types later — with a lot of surface-level decoration sprinkled on top, to make it easier for humans to write, but the semantics of the core language are the same as the lambda calculus. That is, the meaning of Haskell programs is centered around evaluating expressions rather than executing instructions, although Haskell has a way to execute instructions, too.

What is Lambda Calculus?

Lambda calculus is a framework developed by Alonzo Church in 1930s to study computations with functions.

  • Function creation − Church introduced the notation λx.E to denote a function in which ‘x’ is a formal argument and ‘E’ is the functional body. These functions can be of without names and single arguments.
  • Function application − Church used the notation E1.E2 to denote the application of function E1 to actual argument E2. And all the functions are on single argument.

Syntax of Lambda Calculus

Lamdba calculus includes three different types of expressions, i.e.,

E :: = x(variables)

| E1 E2(function application)

| λx.E(function creation)

Where λx.E is called Lambda abstraction and E is known as λ-expressions.

Evaluating Lambda Calculus

Pure lambda calculus has no built-in functions. Let us evaluate the following expression −

(+ (* 5 6) (* 8 3)) 

Here, we can’t start with '+' because it only operates on numbers. There are two reducible expressions: (* 5 6) and (* 8 3).

We can reduce either one first. For example −

(+ (* 5 6) (* 8 3)) 
(+ 30 (* 8 3)) 
(+ 30 24) 
= 54

β-reduction Rule

We need a reduction rule to handle λs

(λx . * 2 x) 4 
(* 2 4) 
= 8

This is called β-reduction.

The formal parameter may be used several times −

(λx . + x x) 4 
(+ 4 4) 
= 8

When there are multiple terms, we can handle them as follows −

(λx . (λx . + (− x 1)) x 3) 9 

The inner x belongs to the inner λ and the outer x belongs to the outer one.

(λx . + (− x 1)) 9 3 
+ (− 9 1) 3 
+ 8 3 
= 11

Free and Bound Variables

In an expression, each appearance of a variable is either "free" (to λ) or "bound" (to a λ).

β-reduction of (λx . E) y replaces every x that occurs free in E with y. For Example −

Bound Variables

Alpha Reduction

Alpha reduction is very simple and it can be done without changing the meaning of a lambda expression.

λx . (λx . x) (+ 1 x) ↔ α λx . (λy . y) (+ 1 x) 

For example −

(λx . (λx . + (− x 1)) x 3) 9 
(λx . (λy . + (− y 1)) x 3) 9 
(λy . + (− y 1)) 9 3 
+ (− 9 1) 3 
+ 8 3