When I was reading the collection of learning resources on Haskell and tried to find a good start, I quickly realized that none of the books or tutorials are suitable for me: the easier a tutorial claims to be, the harder to really understand Haskell by reading it. What I need is a terse documentation that introduces the syntax and semantics of Haskell systematically and clearly, but unfortunately none was found.

I know I have to try the hard way: reading the Haskell language specification directly and absorb it myself. To make the process less dull and record my progress, I will write down my learning notes here incrementally.

Overview

A Haskell program is organized with four levels: modules, declarations, expressions & lexical structures, but the specification is organized in the reverse order.

Haskell has ad hoc polymorphism (overloading) and parametric polymorphism (Hindley-Milner type structure).

Haskell has six namespaces:

• for value
  • variable
  • constructor
• for type entity
  • type variable
  • type constructor
  • type class
• module

The same name can be reused without conflicts as long as they are in different namespaces.

Lexical Structure

A Haskell program is composed of lexemes (tokens) and whitespaces.

program → { lexeme | whitespace } 

Whitespace includes:

• The complete set of whitespace in both ASCII & Unicode
• Two kinds of comments
  • inline comment starts with --
  • nested comment wrapped by {- -}

A lexeme is one of the following:

• identifier
  • qvarid: (qualified) variable identifier
  • qconid: (qualified) constructor identifier
  • reservedid: reserved identifier
• operator
  • qvarsym: (qualified) variable (symbolic) operator
  • qconsym: (qualified) constructor (symbolic) operator
  • reservedop: reserved operator
• literal: integer, float, character or string literal
• special: one of special symbols ()[]{}`,;

A variable and a constructor is distinguished by the first character and put into different namespaces:

• identifier
  • variable: lower case (including underscore)
  • constructor: upper case
• operator
  • variable: non-colon
  • constructor: colon :

A variable or constructor can contain symbol ', so the common mathematical term “x prime” can be represented as x'.

By using layout rule (indentation), symbols {}; can be omitted in sereral grammer productions.

Expressions

Parentheses

(exp) is a parenthesized expression, and is equivalent to exp.

Function & operator application

Function is prefixed and curried, so f x y means (f x) y.

fexp    → [fexp] aexp

All operators are infixed except prefix negation -.

infixexp→ lexp qop infixexp
        | - infixexp    (prefix negation)
        | lexp
qop     → qvarop | qconop

An operator can be converted to prefix notation by parentheses. e.g.

(+) x y

Reversely, a function identifier (either variable or constructor) can be converted to an infix operator by backquotes.

x `op` y

List & Tuple

List is constructed with :.

1:2:3:[]   or   (:) 1 ((:) 2 ((:) 3 []))

Arithmetic sequence is another way to construct a list.

[1,3..6] == [1,3,5]
  [1..6] == [1,2,3,4,5,6]

Tuple is constructed with (,...,).

(1, 2, "a")   or   (,,) 1 2 "a"

Field label

A field label is used to give a name to a field in a datatype. It can be used to construct, extract and update the field.

A constructor with labeled fields:

aexp    → qcon { fbind1 , … , fbindn }  (n ≥ 0)
fbind   → qvar = exp 

Pattern matching

A pattern itself is not an expression, but it is an important part of sereral expressions, including: lambda abstractions, function definitions, let expressions, list comprehensions, do expressions and case expressions.

Pattern matching is used to deconstruct values according to their type specification. It proceeds from left to right, and outside to inside. Attempting to match a pattern can have one of three results:

• Fail
• Succeed: returning a binding for each variable in the pattern
• Diverge: i.e. return ⊥

The syntax for patterns covers a subset of expressions.

A pattern can match against infix expressions, but limited to infix constructors (the operator must be qconop).

pat     → lpat qconop pat (infix constructor)

A pattern can match against constructor functions (with or without field labels).

pat     → ...
        | lpat

lpat    → apat
        | gcon apat1 … apatk    (arity gcon  =  k, k ≥ 1) 

apat    → ...
        | gcon  (arity gcon  =  0)
        | qcon { fpat1 , … , fpatk }    (labeled pattern, k ≥ 0)

fpat    → qvar = pat 

A pattern can match against a variable, a literal, a parenthesized expression, a tuple or a list.

lpat    → var ...
        | - (integer | float)   (negative literal) 

apat    → ...
        | literal
        | ( pat )               (parenthesized pattern)
        | ( pat1 , … , patk )   (tuple pattern, k ≥ 2)
        | [ pat1 , … , patk ]   (list pattern, k ≥ 1)

The variables defined within the pattern can be binded, but how to name and bind the whole pattern? This is exactly what an as pattern does (var before @ is the name for the whole pattern).

apat    → var [ @ apat] (as pattern) 

Wildcard is used when you need a variable placeholder but do not want to bind the value to a name.

apat    → ...
        | _     (wildcard)

Sometimes you need a pattern that can never fail (only succeed or diverge), it is called a irrefutable pattern.

apat    → ...
        | ~ apat        (irrefutable pattern)

Besides ~apat, these patterns are also irrefutable: a variable, a wildcard, N apat where N is a constructor defined by newtype and apat is irrefutable, var@apat where apat is irrefutable. All other patterns are refutable.

Case expression

Case expression is very important because all other pattern matching expressions ultimately translate into case expressions.

A case expression has one or more alternatives.

lexp    → case exp of { alts }
alts    → alt1 ; … ; altn       (n ≥ 1) 

An alternative is either a pattern or empty. The pattern either coresponds to an expression (body) directly, or has one or more guarded patterns (note an optional gdpat appears at the right side of itself). A guarded pattern starts with | and is composed of one or more guards.

alt     → pat -> exp [where decls]
        | pat  gdpat [where decls]
        | (empty alternative) 
gdpat   → guards -> exp [ gdpat ]
guards  → | guard1, …, guardn   (n ≥ 1)
decls   → { decl1 ; … ; decln } (n ≥ 0) 

Note that each alternative can optionally have a where declaration. It is used to bind extra variables to be used in the local scope.

There are two types of guards: pattern guard & boolean guard, and local declarations can also be introduced together with guards.

guard   → pat <- infixexp     (pattern guard)
        | let decls           (local declaration)
        | infixexp            (boolean guard)

This is how a case expression works:

1. The expression after case is matched against each alternative till a match is found.
2. Then each guarded pattern in the matched alterantive is tested till one passes. A guarded pattern passes if and only if all of its guards pass.
3. If successful, the conresponding expression is returned, otherwise, the next guarded pattern or alternative is tried sequentially.
4. If no match can be found, the result is ⊥.

Lambda expression

Lambda is used to construct a function without a name. Besides a variable, the input can also be any pattern.

lexp    → \ apat1 … apatn -> exp        (n ≥ 1)

An example:

(\ (x, y) -> x+y) (3, 7)

Also note that lambda -> associates to the right, e.g.

Integer ->  Integer -> Integer
    is equivalent to
Integer -> (Integer -> Integer)

Let expression

A let expression introduces a nested, lexically-scoped, mutually-recursive list of declarations. exp after keyword in is the value of a let expression.

lexp    → let decls in exp
decls   → { decl1 ; … ; decln } (n ≥ 0) 

Some examples:

let {} in 42
let {(x,y) = (1,2)} in x+y

List comprehension

A list comprehension constructs a list of elements represented by exp qualified by one or more qualifiers.

aexp    → [ exp | qual1 , … , qualn ]   (n ≥ 1)

There are three kinds of qualifiers.

A generator is composed of a pattern (pat with type t) and a list (e with type [t]). The pattern is matched against and binded to each element of the list one by one, so the binded variables can be used to generate each element of the result list. The generators are evaluated in a nested, depth-first order, and a failed match is just skipped over.

qual    → pat <- e      (generator)

A qualifier can also be a local declaration to bind auxiliary variables, or a boolean guard to exclude some elements from the list.

qual    → ...
        | let decls     (local declaration)
        | exp           (boolean guard) 

Do expression

Wait till monad is fully understood.

Type signature

Haskell has type inference, but an expression can be optionally specified with a type signature.

exp     → infixexp :: [context =>] type

Declarations

There are top declarations (topdecl) that are only allowed at the top level of a module, and nested declarations (decl) that may be used either at the top level or in nested scopes.

topdecl → ...
        | ...
        | decl 

Top declarations

A top declaration starts with one of the keywords: data, type, newtype, class, instance, default and foreign.

data, type and newtype is for declaring new types. class is for declaring typeclasses and instance is for declaring the membership between types and typeclasses.

They are explained later one by one.

Nested declarations

In the last section, decl appears in the let expression and where clause without any explanations. Actually, they are nested declarations.

There are five kinds of nested declarations: type signature, fixity, function binding, pattern binding and empty declartions.

A type signature simply specifies types for variables.

decl    → gendecl
        | ...
gendecl → vars :: [context =>] type
vars    → var1 , …, varn        (n ≥ 1)

A fixity declaration gives the fixity and binding precedence of one or more operators.

gendecl → ...
        | fixity [integer] ops
fixity  → infixl | infixr | infix
ops     → op1 , … , opn         (n ≥ 1)
op      → varop | conop 

The right hand side (rhs) of function and pattern bindings are the same.

decl    → ...
        | (funlhs | pat) rhs

The syntax of rhs is almost the same as case expression, except -> is replaced by =.

rhs     → = exp [where decls]
        | gdrhs [where decls]
gdrhs   → guards = exp [gdrhs]

A function can be binded in multiple function binding declarations, as long as they are contiguous and the number of patterns is the same. In each of the declaration, the left hand side supports three alternative syntaxes.

funlhs  → var apat { apat }
        | pat varop pat
        | ( funlhs ) apat { apat }

And an example:

plus x y z = x+y+z
x ‘plus‘ y = \ z -> x+y+z
(x ‘plus‘ y) z = x+y+z

Type

Just as an expression may contain variables and denotes a value, a type expression may contain type variables and denotes a type value (but it is evaluated at compile time, unlike an expression evaluated at run time).

Type expressions are designed to have similar representations as their corresponding expressions.

Function type can be represented in infix or prefix notation. Like function application, type application (btype) is also prefixed and curried. atype is the type expression excluding infix function type and type application.

type    → btype [-> type]       (function type)
btype   → [btype] atype         (type application)
atype   → gtycon
        | ...
gtycon  → ...
        | (->)  (function constructor)

A type variable is an identifier beginning with a lowercase letter. A parenthesized type (t) is identical to the type t. A type constructor (type template) as an identifier begins with an uppercase letter. Besides function type, the syntaxes for tuple and list are also special syntaxes.

atype   → gtycon
        | tyvar
        | ( type1 , … , typek ) (tuple type, k ≥ 2)
        | [ type ]              (list type)
        | ( type )              (parenthesised constructor)
gtycon  → qtycon
        | ()            (unit type)
        | []            (list constructor)
        | (->)          (function constructor)
        | (,{,})        (tupling constructors) 

Kind

What is *, * -> *…? An ordinary type has kind *. A type constructor (template) that has one type argument has kind * -> *, e.g. a list. So on and so forth.

Context

The context (context => type) is used to indicate that type tyvar belongs to class qtycls.

A context is composed of zero or more class assertions.

context → class
        | ( class1 , … , classn )               (n ≥ 0)

And a class assertion is either either a type variable, or the application of type variable to one or more types.

class   → qtycls tyvar
        | qtycls ( tyvar atype1 … atypen )      (n ≥ 1)
qtycls  → [ modid . ] tycls
tycls   → conid
tyvar   → varid 

Algebraic data type

algebraic data type is named so because it is composed of other types by product and sum (algebraic operations). It introduces a new type constructor (simpletype) with zero or more constituent data constructors (constrs).

topdecl → ...
        | data [context =>] simpletype [= constrs] [deriving]

The type constructor begins with upper case letter and may have zero to more type variables as parameters. The type constructor then can be used in curried type application in a type expression.

simpletype      → tycon tyvar1 … tyvark         (k ≥ 0) 

On the right side of =, sum (alternative) types are separated by |.

constrs → constr1 | … | constrn         (n ≥ 1)

For each constr, there are three alternative syntaxes.

1. A data constructor followed by zero or more atype.
2. An infix data constructor operator between two btype.
3. A data constructor followed by field declarations.

constr  → con [!] atype1 … [!] atypek   (arity con  =  k, k ≥ 0)
        | (btype | ! atype) conop (btype | ! atype) (infix conop)
        | con { fielddecl1 , … , fielddecln }       (n ≥ 0) 
con     → conid | ( consym )    (constructor) 

! is strictness flag to indicate that the corresponding constructor argument is eagerly evaluated.

Type synonym

A type synonym is equivalent to its definition are completely interchangeable.

topdecl → type simpletype = type

Newtype

A newtype declaration introduces a distinct type whose representation is the same as an existing type.

topdecl     → newtype [context =>] simpletype = newconstr [deriving]
newconstr   → con atype
            | con { var :: type }

• Unlike type synonyms, newtype may be used to define recursive types.
• New instances can be defined for a type defined by newtype but may not be defined for a type synonym.
• A type created by newtype has an extra level of indirection compared to an algebraic datatype, so the pattern matching rule is different.

Ad hoc polymorphism

Ad hoc polymorphism (overloading) is supported by typeclasses.

A class declaration introduces a new class and the operations (methods) on it.

Modules

To be continued…