Operator Precedence

Precedence allows to define the order of the operations.

If the precedence of op1 is higher than the one of op2, then x op1 y op2 z shall be read as: (x op1 y) op2 z.

See the precedence table for all Haskell operators.

By using the :info GHCi command, the precedence levels of operators can be returned:

Prelude> :info +
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
    -- Defined in ‘GHC.Num’
infixl 6 +

Operator Associativity

This determines how operators of the same precedence are grouped in the absence of parentheses.

Operators may be:

• associative, meaning the operations can be grouped arbitrarily
• left-associative, meaning the operations are grouped from the left: 2-3+4 = (2-3)+4
• right-associative, meaning the operations are grouped from the right: 2^3^4 = 2^(3^4)
• non-associative, meaning operations cannot be chained, often because the output type is incompatible with the input types

Operator Calls

Operators are just functions that can be called:

• either directly: op1 x or op2 x y; for example: (-x) or (+) x 4
• or, for the ones of arity 2, as infix operators: x `op2` y  ≡  op2 x y

Some Operators of Interest

x:y:z:l  ≡  x:(y:(z:l))

[4,5,3] = 4:5:3:[]

A -> B -> C ->  ≡  A -> (B -> (C -> D))

-- mult :: Int -> (Int -> (Int -> Int))
mult :: Int -> Int -> Int -> Int

-- mult x y z = ((mult x) y) z
mult x y z = x*y*z

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

a $ b op c  ≡  a (b op c)

($) :: (a -> b) -> a -> b
f $ x = f x

Notion of Type

A type is a set of associated values.

e :: T means that expression e is of type T.

Haskell infers types at compilation (static typing), which prevents to discover many problems [4] at runtime.

Some expressions that could be successfully evaluated can nevertheless be rejected on type grounds (ex: if True then 1 else False), but in practice it is hardly a problem.

Type Alias

Ex: type Pos = (Int,Int)

This does not introduce a new type; these are synonyms for Haskell.

Type declarations can have any number of parameters and be parametrised by other types, like in type Assoc k v = [(k,v)].

Data Declarations

This introduces a new type; ex: data Bool = False | True.

| shall be read "or", and the values specified for the new type are called constructors. They start with an uppercase letter and a given constructor may not be used in more than one type.

Constructors may have arguments, in which case they are constructor functions:

data Shape = Circle Float | Rect Float Float

Here Circle :: Float -> Shape.

Such functions have no definition equations, and Circle 1.0 is fully evaluated and cannot be further simplified.

The ordering on the constructors of a type is determined by their position in its declaration (ex: False < True; constructors with arguments are ordered lexicographically regarding these argments.

They may also be:

• parametrised: data Maybe a = Nothing | Just a.
• recursively defined: data Nat = Zero | Succ Nat

For example all sorts of trees can be defined with it:

• binary tree with content only in leaves:

data Tree a = Leaf a | Node (Tree a) (Tree a)

• binary tree with content only in non-leaf nodes:

data Tree a = Leaf | Node (Tree a) a (Tree a)

• binary tree with different types of content in leaf and non-leaf nodes:

data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)

• tree having any number of subtrees:

data Tree a = Leaf a | Node a [Tree a]

Newtype Declarations

Introduces a new type provided that it has a single constructor with a single argument.

Ex: newtype Nat = N Int.

By comparison:

• type Nat = Int would not introduce a new type
• data Nat = N Int would also introduce a new type, but would incur runtime overhead

Why data is not automatically transformed by Haskell internally in newtype whenever applicable is unsure (for us).

Algebraic Datatypes

They are defined based on unions of values.

For example, in:

data MyFirstType = FirstValue | SecondValue | FirstConstructor T

MyFirstType is the name of the type. FirstValue and SecondValue are (constructor) values.

FirstConstructor is a constructor, and T is a type name (not a constructor).

Type and constructor names can be the same, as no ambiguity can occur.

Polymorphic types can be defined:

data MySecondType a = ThirdValue | SecondConstructor a Int

Basic Types

• monomorphic: Bool, Char, String :: [Char], Int/Integer, Float/Double
• polymorphic: list, tuple, function

("I am a tuple", 2, True)

l1 = [1.0, 7.0, 2.0]
l2 = []
l3 = [100..]
l4 = 1 : 2 : 3 : []

u s = [toUpper c | c <- s]

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []    = v
foldr f v (x:xs)  = f x (foldr f v xs)

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []    = v
foldl f v (x:xs)  = foldl f (f v x) xs

s = "This is a unique \
\line."

Type Class

A type class is a set of types that support a set of functions called methods.

For example the Eq class is to gather all types that can be compared for egality (or inegality), based on the following two methods:

(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

A type may belong to one or more classes.

Class constraints can be specified when typing a function. For example:

(+) :: Num a => a -> a -> a

The type variable a must be here an instance of class Num.

A type respecting at least one of such constraints is said overloaded, as is the corresponding expression.

Well-known classes are: Eq, Ord, Show, Read, Num, Integral, Fractional.

Informal Descriptions

Various intuitive descriptions of a monad apply:

• a stateful datastructure representing some processing
• an abstraction, a generic concept allowing to structure programs generically and to unify in a functional way various problems (to structure them and favour separation of concerns)
• programmable ";" (semicolons whose effect can be defined)
• a structure allowing to express imperative traits in functional languages, to convey notions like exceptions or side-effects while preserving their purity
• a way of describing and composing impure expressions in a pure context: a monad is an expression still to be evaluated (potentially inducing then side-effects), yet able to be integrated in a pure context
• the code source of an imperative program that, once executed, returns a value of a specified type and that can be chained with other programs taking and returning such values; the language handles then the imperative programs themselves (ex: their source) rather than the values they return

More Formally

A monad M is a (type, return function, bind function) triplet with:

• a monadic constructor: t -> M t
• a function named return that, through the previous constructor, allows to obtain, from a value of type a, a value of monadic type M a: return: t -> M t
• a function named bind that allows to compose a monadic function [5] with others, represented by the >>= infix operator so that: >>= :: M t -> ( t -> M u ) -> M u

So return allows to convert a pure expression (not involving side-effects) of type t into an action (i.e. a transformation that may be executed) M t that is impure (with side effects) and deals with a value of type t. No opposite operation exists (that would transform a value of type type M t into one of type t, in the sense that side-effects cannot be rolled-back. A goal is thus to separate the pure parts of a program from its impure ones, which shall be minimised and isolated.

Mt >>= f (i.e. "bind Mt f") allows to apply the f function to the value of type t encapsulated in Mt; >>= drives the chaining of monadic functions (as such it handles functions, not values).

By composing >>= with return, any function g :: t -> t can be applied to a monad of type M t (here the types u and t in the definition of bind are the same).

These functions (f et g) are only aware of the value (t) encapsulated in the monad, not the monad (M t) itself.

So the developer composes a sequence of function calls (a pipeline) by chaining binds in an expression. Functions transform the values that they receive ; then the bind operator controls the returned monadic values (ex: it can enrich them outside of the view of these chained functions) and the next calls (ex: it can make them conditional).

So a monad of type M t is an algebraic datatype that derives from type t.

The elements of the monadic triplet shall respect following 3 axioms, return behaving like a neutral element from >>=:

• left composition by return, with: (return x) >>= f  ≡  f x
• right composition by return, with: m >>= return  ≡  m
• associativity of bind, with: (m >>= f) >>= g  ≡  m >>= \x . (f x >>= g)

A sequence of actions (transformations that may be executed) may be combined into a single composite action thanks to the do notation.

Let's consider types Vk for k in 1..n and R, and a function f of arity n and type V1 -> V2 -> ... -> Vn -> R.

do v1 <- a1
   v2 <- a2
   ...
   vn <- an
   return (f v1 v2 ... vn)

The <- operator in v1 <- a1, for v1 a value of type V1, means that the action (transformation function) a1 of type M V1 (i.e., if M is IO, of type WorldState -> (V1,WorldState)) shall be executed, and that its result (of type V1) shall be stored in variable v1. Then the (pure) function f can be evaluated with these resulting vk arguments, and its returned value of type R is returned as an action of type M R (ex: IO Int).

As a consequence, the do notation returns a new action, i.e. a single composite transformation that may be executed.

Refer to this article for more information.

In a Nutshell

A monad M defines a type that represents a processing and is associated to two operators:

• return: to encapsulate a value of type t in this monad (resulting in a monadic value M t)
• bind, i.e. >>=: to compose monadic functions

Examples

The IO monad is probably the most well-known monad. IO t represents an imperative program taking no parameter and returning a value of type t.

For example:

• IO () denotes, with the empty tuple (), a program returning no specific value (akin to void in some languages)
• the getLine``function is of type ``IO String, it returns the string entered on the keyboard by the user

A second example is the one of Maybe, as taken from this article

The Maybe-type (so here M = Maybe) is: Maybe t :: Just t | Nothing

The Maybe-return is:

return :: t -> Maybe t
return undefined = Nothing
return O -> Just O

The Maybe-bind is:

(>>=) :: Maybe t -> ( t -> Maybe u ) -> Maybe u
Nothing   ```>>=``` f = Nothing
(Maybe a) ```>>=``` f = Just( f a )

The Maybe monad allows to handle errors: as soon as a function call fails, the next binds short-circuit the processing rather than letting the next functions be evaluated in turn.

A third example is seqn, to transform a list of actions with side-effects (ex: IO) returning a result of type a into a single of such action:

seqn :: Monad m => [m a] -> m [a]
seqn []         = return []
seqn (act:acts) = do x <- act    -- *performs* this 'act' action
                          xn <- seqn acts
                          return (x:xs)

Properties

• any monad can be characterized as an adjunction between two (covariant) functors
• the monad as defined in category theory has been applied to functional programming, in order to provide semantics for the lambda calculus

Interest

• as monadic values represent explicitly not only computed values but also the effects that these evaluations trigger, a monadic expression can be freely replaced by its value (referential transparency), which enables the use of various optimisation approaches based on rewriting
• a monad captures, centralises and unifies once for all recurring schemes to integrate side effects that would be otherwise more difficult to handle (ex: with CPS, Continuation-Passing Style
• monads may register additional data that are inaccessible from functions and/or may drive their execution (ex: conditional call)
• monads may favour aspect-oriented programming, in the sense that they allow the developer to focus on his domain-specific logic (as the binding code, provided by the monad, is defined separately - and once for all)

Usages

• to condense code and to tie it to a mathematical formulation (compilation-time version of the "decorator pattern"
• to facilitate static analysis and program proofs
• to support the definition of simple DSL (Domain-Specific Languages) and to combine parsing rules
• to support the traversal of datastructures (see zipper)
• to transform complicated sequences of function calls into a compact pipeline abstracting out the management of additional data, flow control and side-effects
• to rely on call-by-need
• to allow for optimisations such as:
  • deforestation (a.k.a. fusion or "tree suppression"): a program transformation to eliminate intermediate lists or tree structures that are created and then immediately consumed by a program
  • memoisation: the caching of results of function calls in order to compute them once
  • parallelisation: to split a program between multiple logical processes
  • strong reduction: when β-reduction in the λ-calculus are also performed on function bodies

See also this section about monad applications.

Filenames

They may or may not start with a capital letter (and no specified convention applies).

They may be in snake_case or in CamelCase.

Ex: my_test.hs, HelloWorld.hs.

Extensions

The main extensions are:

• .hs: Haskell source code (to preprocess then compile)
• .lhs: literate Haskell source (to unlit, preprocess and compile), where all text is comment by default, and code is specifically designated as such
• .hi: interface file; contains information about exported symbols
• .hc: intermediate C files

A very basic Foobar.hs source file once compiled results in a standard Foobar.o object file, typically:

ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

If Foobar.hs defines a suitable main function, once linked it results in a standard Foobar.o executable, typically (depending on the build options):

ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 4.4.0, BuildID[sha1]=[...], not stripped

In terms of shared libraries, this boils down to, for example:

linux-vdso.so.1
libHSbase-4.14.2.0-ghc8.10.5.so => /usr/lib/ghc-8.10.5/base-4.14.2.0/libHSbase-4.14.2.0-ghc8.10.5.so
libHSinteger-gmp-1.0.3.0-ghc8.10.5.so => /usr/lib/ghc-8.10.5/integer-gmp-1.0.3.0/libHSinteger-gmp-1.0.3.0-ghc8.10.5.so
libHSghc-prim-0.6.1-ghc8.10.5.so => /usr/lib/ghc-8.10.5/ghc-prim-0.6.1/libHSghc-prim-0.6.1-ghc8.10.5.so
libHSrts-ghc8.10.5.so => /usr/lib/ghc-8.10.5/rts/libHSrts-ghc8.10.5.so
libgmp.so.10 => /usr/lib/libgmp.so.10
libc.so.6 => /usr/lib/libc.so.6
libm.so.6 => /usr/lib/libm.so.6
librt.so.1 => /usr/lib/librt.so.1
libdl.so.2 => /usr/lib/libdl.so.2
libffi.so.7 => /usr/lib/libffi.so.7
libpthread.so.0 => /usr/lib/libpthread.so.0
/lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2