referentially transparent

we can replace any expression by its value without changing the behaviour of the program.

About Applicative and its relation with Monad

• Haskell language report 2010 https://www.haskell.org/onlinereport/haskell2010/
• Haskell book, a good tutorial https://en.wikibooks.org/wiki/Haskell
• A Gentle Introduction to Haskell, Version 98 https://www.haskell.org/tutorial/index.html

Layout is optional:

Haskell permits the omission of the braces and semicolons used in several grammar productions, by using layout to convey the same information. This allows both layout-sensitive and layout-insensitive styles of coding, which can be freely mixed within one program.

Formal layout rules:

The layout (or “off-side”) rule takes effect whenever the open brace is omitted after the keyword where, let, do, or of. When this happens, the indentation of the next lexeme (whether or not on a new line) is remembered and the omitted open brace is inserted (the whitespace preceding the lexeme may include comments).

For each subsequent line,

• if it contains only whitespace or is indented more, then the previous item is continued (nothing is inserted);
• if it is indented the same amount, then a new item begins (a semicolon is inserted);
• and if it is indented less, then the layout list ends (a close brace is inserted).
• If the indentation of the non-brace lexeme immediately following a where, let, do or of is less than or equal to the current indentation level, then instead of starting a layout, an empty list “{}” is inserted, and layout processing occurs for the current level (i.e. insert a semicolon or close brace)

Explicit open brace must be closed explicitly:

The layout rule matches only those open braces that it has inserted; an explicit open brace must be matched by an explicit close brace. Within these explicit open braces, no layout processing is performed for constructs outside the braces, even if a line is indented to the left of an earlier implicit open brace.

precedence and associative:

Consecutive unparenthesized operators with the same precedence must both be either left or right associative to avoid a syntax error.

lambda, let, conditionals extend as far to the right as possible:

The grammar is ambiguous regarding the extent of lambda abstractions, let expressions, and conditionals. The ambiguity is resolved by the meta-rule that each of these constructs extends as far to the right as possible.

var :: type

[x | xs <- [[(1,2),(3,4)],
            [(5,4),(3,2)]],
     (3,x) <- xs]

<- is generator syntax, and nested. Each iteration, if a value does not match, that value is skipped. Thus the above expression evaluates to [4,2]

In general in Haskell, <- will perform patern matching with left being pattern.

double x = x * x
  where decls
\ x y -> x + y

function

funlhs var = exp where decls
funlhs var
  | guard = exp
  -- three types of guards
  | (3,x) <- exp = exp
  | let decls = exp
  | boolexp = exp
  where decls

Functional composition has the definition of

\[(f \circ g) x = f (g x)\]

and the type of it

\[(\circ) :: (\beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma)\]

functional composition is also associative, thus no need to put brackets

\[(f \circ g) \circ h = f \circ (g \circ h)\]

The special value \(\bot\) is polymorphic: \(\bot\) is a value of every type. This means, any function can be applied to \(\bot\). If \(f \bot = \bot\), then \(f\) is said to be strict. Otherwise, it is non-strict. In other words, a function is strict if it is undefined whenever its argument is undefined.

In fact, a non-strict semantic is often preferable for functions, for several reasons:

• it makes reasoning about equality easier
• we can define new control structures by defining new functions

For example, we define a function three that takes anything and return the value 3. I.e.

three :: num -> num
three x = 3

Another example, the definition of cond

\[cond :: bool \rightarrow \alpha \rightarrow \alpha \rightarrow \alpha\]

cond p x y = x, if p
           = y, otherwise

Under strict semantics, \(cond\ True\ 0\ \bot = \bot\), under non-strict semantics, \(cond True 0 \bot = 0\). But in either case, cond is strict on its first argument. This also means, strictness is bundled with the function, and is applied on some arguments, not all.

The operational semantics of strict or non-strict functions is closely related to the reduction strategy. eager-evaluation reduces every expression to its simplest form, while lazy-evaluation does not care about the wellness of the expressions whose values are not required for the evaluation.

Three basic rules

1. Application rule: if f x :: t, then x :: t' and f :: t' -> t for some new type t'
2. Equality rule: if both the types x :: t and x :: t' can be deduced for a variable x, then t = t'.
3. Function rule: If t -> u = t' -> u', then t = t', and u = u'

Often, the newly introduced types are named by numerical sub-notation.

For example, consider the composition operator

(.) f g x = f (g x)

The following script shows the inference steps:

f :: t1
g :: t2
x :: t3
f (g x) :: t4
(.) :: t1 -> t2 -> t3 -> t4
g x :: t5
f :: t5 -> t4
x :: t6
g :: t6 -> t5
t1 = t5 -> t4
t2 = t6 -> t5
t3 = t6
(.) :: (t5 -> t4) -> (t6 -> t5) -> t6 -> t4

Finally, we need to replace the types with type variables to make it generic:

\[(\circ) :: (\beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma)\]

List itself is defined as a recursive type.

\[list \alpha :: Nil | Cons \alpha (list \alpha)\]

Let list comprehension notation be [<expr> | <qualifier>; ...]. Qualifier can be boolean expression for predicates or generators. Later generators vary more quickly than their predecessors, and can depends on the variables introduced by earlier ones. With this, we can define many operators on lists:

(++) :: [a] -> [a] -> [a]
concat :: [[a]] -> [a]
concat xss = [x | xs <- xss; x <- xs]

Instead of using (++) for concating list, we can use (:) (pronounced 'cons') for specifying consing. One important reason to use (:) is that, every list can be expressed in terms of [] and (:) in exactly one way.

(:) :: a -> [a] -> [a]
x:xs = [x] ++ xs

We have the following operators on lists:

(#) :: [a] -> num
#(xs ++ ys) = #xs + #ys

hd :: [a] -> a
tl :: [a] -> [a]
hd ([x] ++ xs) = x
tl ([x] ++ xs) = xs

take n xs ++ drop n xs = xs

takewhile :: (a -> bool) -> [a]  -> [a]
zip :: ([a], [b]) -> [(a,b)]
(!) :: [a] -> num -> a # index

Map and filter can be defined by:

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
filter :: (a -> bool) -> [a] -> [a]
filter p xs = [x | x <- xs; p x]

Fold:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b
sum = foldr (+) 0
product = foldr (x) 1
concat = foldr (++) []
and = foldr (&) True
or = foldr (|) False

foldr and foldl do rely on associative of the underlying operators to function correctly, and there are several duality theorems.

In big data literature, map and reduce are borrowed from functional programming. Map is just map, reduce has another familiar name called fold. The Map-reduce framework does not just borrow the name. Its contribution is scalability and fault-tolerance. In this case, map produces data by filtering, and emit the data, marshalling, and reduce does folding.