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
{- -}
- inline comment starts with
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:
- The expression after
caseis matched against each alternative till a match is found. - 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.
- If successful, the conresponding expression is returned, otherwise, the next guarded pattern or alternative is tried sequentially.
- 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.
- A data constructor followed by zero or more
atype. - An infix data constructor operator between two
btype. - 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,
newtypemay be used to define recursive types. - New instances can be defined for a type defined by
newtypebut may not be defined for a type synonym. - A type created by
newtypehas 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…