# Functional Programming

## Table of Contents

## 1 References

- introduction to functional programming 1988-Book-Bird-Introduction
- product type vs. sum type
*algebraic data type*is a kind of composite type, i.e., a type formed by combining other types. Algebraic data type contains product type and sum type.

## 2 TODO Haskell

### 2.1 Tmp

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

About Applicative and its relation with Monad

#### 2.1.1 operators

Use Hoogle to search for operator symbols!

- list difference
`(\\)`

The

`(\\)`

function is list difference (non-associative). The result of`xs \\ ys`

is a smaller`xs`

, with`ys`

removed. - strictness declaration

data Foo = Foo Int Int !Int !(Maybe Int)

- infix operator
`(+)`

and````

Haskell functions ar typically used using prefix notation. However, some operations are used infix, such as

`+`

. It is possible to use + in prefix style, by putting it inside parenthesis`(+)`

.Additionally, putting backticks around normal prefix functions enables you to use them as infix functions. It is typically used for 2-argument functions, but for more arguments, you need to use extra parentheses.

- as-pattern

f (x:xs) = x:x:xs f s@(x:xs) = x:s

- tilde

When using patten matching, a tilde makes two things:

- force matching: you tell the compiler, trust me, this would match. If not matching, it will result in runtime error.
- lazy matching: the match does not happen until the value is used.

head' ~(x:xs) = x

- function composition

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

It has precedence 9.

- dollar operator

($) :: (a -> b) -> a -> b

$ has 0 precedence, the lowest. Thus it is used to change the order of operator associativity. Also commonly used to separate large arguments.

sort $ "hello" ++ "world"

- Lexical syntax:

`=>`

- context or class inheritance

- Defined in Functor:

- <$>: fmap

- Defined in Applicative:

- <*>: used with fmap
- *>: defined in Functor sequential stmts

- Defined in Alternative

`<|>`

`Nothing <|> Just a = Just a`

### 2.2 references

- 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

### 2.3 layout

Layout is optional:

Haskell

permits the omission of the braces and semicolonsused 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 befreely mixedwithin 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.

### 2.4 lexical staff

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.

#### 2.4.1 fixity declaration

Determines the binding precedence of an operator. A fixity declaration may appear anywhere that a type signature appears.

There are three kinds of fixity, non-, left- and right-associativity (infix, infixl, and infixr, respectively), and ten precedence levels, 0 to 9 inclusive (level 0 binds least tightly, and level 9 binds most tightly). If the digit is omitted, level 9 is assumed. Any operator lacking a fixity declaration is assumed to be infixl 9 by default.

There is a table for all operators and their precedence levels.

### 2.5 decl

var :: type

### 2.6 do expression

do stmt -- stmt can be pat pat <- exp -- this is not the let expression. The binding will take effect in -- the following program let decls -- the last one must be an expression, and cannot have pattern binding exp

### 2.7 list comprehension

[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.

### 2.8 function and lambda

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

### 2.9 let binding

let x, y = 5,10 in x + y + 1

### 2.10 conditional

if e1 then e2 else e3

### 2.11 case expression

case exp of { pat -> exp where decls -- equivalent to pat | True -> exp pat | guard where decls -- which has three kinds of guards pat | (3,x) <- exp pat | let decls pat | boolexp }

## 3 Expression

An expression can be *reduced* to an simpler equivalent form. We say
an expression is *canonical* (or in *normal form*) if it cannot be
further reduced.

The result of *equality test* is done by reducing the expressions to
their canonical form, and testing whether the results are
identical. If an expression does not have a canonical form, the result
is undefined, represented by \(\bot\). In particular, function values
have no canonical form.

The order of evaluation thus matters. Each reduction step replace a
sub-term by an equivalent term. The term is called a *redex*, short
for *reducible expression*. There are two reduction policies,
*innermost reduction* and *outermost reduction*. *Innermost reduction*
reduces the innermost redex, i.e. the one that contains no other
redex. *Outermost reduction* reduces the one that is contained in no
other redex.

Any term that is reduced must be reduced to *head normal form*. A term
is in *head normal form* if it is not a redex, and it cannot become a
redex by reducing any of its subterms. For example, `(e1:e2)`

is in
head normal form, because the (:) *itself* cannot be reduced. However,
`e1`

and `e2`

might be reducible. It is a normal form only when e1 and
e2 both are in normal form. By definition, every term in normal form
is in head normal form, but not vice versa.

The evaluation order matters because of the *termination*. Sometimes,
the outermost reduction will terminate while the inner most fail to do
so. In fact, we have the following property:

For every term, if there exists any reduction order that terminates, then there is an outermost reduction that terminates.

Thus, outermost reduction is also called *normal order reduction*,
because it is capable of reducing a term to its normal form whenever
the term has such a form. It is also called *lazy evaluation*, because
it does not reduce a term unless it is essential for finding the
answer. By contract, the innermost reduction is called *applicative
order reduction*, or *eager evaluation*.

Outermost reduction is essential for evaluating non-strict functions. But innermost and outermost reduction will yield the same answer when only strict functions are involved.

With that said for termination property, however, outermost may
require more steps than innermost reduction. The reason is that, the
outermost reduction might duplicate some inner expressions. One
problem is called *graph reduction*, which ensures that the duplicated
sub-terms are always linked together in the graph, and reduction of
them will happen ones, for all the references of them. With graph
reduction, we can say outermost reduction never performs more steps
than innermost.

In summary, we shall use *outermost graph reduction* as the evaluation
model, because

- it terminates whenever any reduction order terminates
- it requires no more steps than innermost order reduction

However, the outermost reduction might use more space than
innermost. In this case, it might be desired to mix innermost order to
achieve better space efficiency. There is a special function `strict`

that fine-control the evaluation order. `strict f e`

is reduced by
first reducing `e`

to head normal form, then applying `f`

. The term
`e`

itself is evaluated as normal, using outermost order. With that,
`strict`

can be defined like below. We can easily have this: ```
f =
strict f
```

iff `f`

is a strict function.

strict f x = \bot, if x = \bot = f x, otherwise

There are some ways to decide how to use `strict`

to optimize the
space occupation, but some takeaway: for functions such as `(+)`

or
`(x)`

, that are strict in **both arguments**, and can be computed in
constant time and space, `foldl'`

is more efficient. But for
functions, such as `(&)`

and `(++)`

, that are non-strict in some
argument, `foldr`

is often more efficient. (`foldl'`

is a rewrite of
`foldl`

with strictness)

foldl' (op) a [] = a foldl' (op) a (x:xs) = strict (foldl' (op)) (a op x) xs

## 4 What is a Function?

- currying: replacing structured arguments by a sequence of simple
ones. The function application operation associates to the left,
i.e.
`f x y`

means`((f x) y)`

.

### 4.1 Composition

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)\]

### 4.2 Strictness

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.

## 5 Type

- Strong-typing: the type of an expression depends only on the type of its component expressions.
- Type variable: typically represented in Greek letters \(\alpha\), \(\beta\), etc. Such type can be instantiated by substitute the type variable with specific type.
- Polymorphic type: a type that contains
*type variables* - Enumerated type: enumeration of possible values
- Composite type: composite primitive type together to form new types
- algebraic data type: is a form of composite type, containing product
type and sum type
- sum type: this is like C union, so it is also called a tagged union. It can take value of either the type, but not both.
- product type: this is like a C structure with different fields. The value set of this type is the set-theoretic product, i.e., the Cartesian product of the set of the field type.

- Abstract Type: types in which the values are prescribed, but the operations are not, are called concrete types. A type whose values are not defined, but operations are, is called abstract type.

### 5.1 Type inference

Three basic rules

- Application rule: if
`f x :: t`

, then`x :: t'`

and`f :: t' -> t`

for some new type`t'`

- Equality rule: if both the types
`x :: t`

and`x :: t'`

can be deduced for a variable`x`

, then`t = t'`

. - 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)\]

### 5.2 List

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.

## 6 Recursion

Functions are often defined recursively. In this section, we see some of the list function definitions in recursion.

zip([], ys) = [] zip(x:xs, []) = [] zip(x:xs, y:ys) = (x,y):zip(xs,ys)

take 0 xs = [] take (n+1) [] = [] take (n+1) (x:xs) = x:take n xs drop 0 xs = xs drop (n+1) [] = [] drop (n+1) (x:xs) = drop n xs

hd(x:xs) = x tl(x:xs) = xs

map f [] = [] map f (x:xs) = f x : map f xs filter p [] = [] filter p (x:xs) = x : filter p xs, if p x = filter p xs, otherwise

# Bibliography

- [1988-Book-Bird-Introduction] Bird & Wadler, Introduction to Functional Programming, (1988).