# Functionel Programming - Notes to book
###### tags: `F#` `notes`
## Lecture 1: Introduction to Functional Programming
### Topics of today
-- Indtroduction to the course
-- Introduction to functional programming and F#
#### Goals of the week
- you know the high-level difference between the imparative, objecy-oriented and declarative programming paradigms
- you can make simple F# programs using the interactive envionment
- you can make simple recursive functions and use simple pattern matching.
- you know the difference between type check and type inference.
- you can understand the simple type results shown in the interactive environment.
### Chapter 1: Getting started
#### Values, types, identifiers and declarations
an arithmetic expression in a line, followed by two semicolons and terminated by pressing th *return* key:
```F#
2 * 3 + 4;;
```
The answer from the system contains the value and the type of expression:
```Fsharp
val it : int = 10
```
The system will add some leading characters in the input line to make a distinction between input from the user and output from the system.
```Fsharp
> 2*3 + 4;;
val it : int = 10
>
```
The leading string "> " is the output whenever this particular system is awaiting input from the user.
It is called the *prompt* --> it "prompts" for input from the user.
the input from the user is ended by a double semicoclon ";;"
while the next line contains the answer from the system.
Typewriter: input from the user is written in. The font
italic typewriter: the snaswer from the system is written in. The font.
------
| Name | Explanation | xName |
| -------- | -------- | -------- |
| val | indicates that a value has been computed | reserved
|it | name for the computed value | identifier |
| int | the result, denoting a subset of the integers | type
| let | starts the declaration | reserved
Declaration: User input
```Fsharp
let price = 125;;
```
```Fsharp
val price : int = 125
```
the identifier price is now a name for the integer value 125.
the identifier price is bound to 125.
Identifiers which are bound can be used in expression:
```Fsharp
price * 20;;
val it : int = 2500
```
The identifier it is now bound to the integer value 2500, and this identifier can also be used in expressions:
```Fsharp
it / price = 20;;
val it : bool = true
```
the operator / is the quotient on integers.
The expression *it/prince* = 20 is a question the system and the identifier it is now bound to the answer true of type boo.
Note that the equality sign in the answer expresses a binding of the identifer it to a value.
#### Simple function declarations
one can name a function, just as one can name an integer constant.
The type float denotes the subset of the real numbers that can be represented in the system.
We choose the name circleArea for the circle area function, and the function is then declared using a let-declaration:
```Fsharp
let circleArea r = System.Math.PI * r * r;
val circleArea : float --> float
```
identifier circleArea now denotes a value, as indicated by the reserved word val occurring in the answer.
function with the type Float --> float, where the symbol --> indicates a function type and the argument as well as the value of the function has type float.
The circleArea can be applied to different arguements. These arguments must have the type float.
```Fsharp
circleArea 1.0;;
val it : float = 3.14
circleArea (2.0);;
val it : float = 12.56
```
#### Comments
A string enclosed within a matching pair (* and *) is a comment.
or // can be used for one-line comments.
#### Anonymous functions. Function expressions
Function expression: a function without any name. is an expression where the value is a function.
A nameless anonymous function can be defined by a simple function expression (lambda)
```Fsharp
fun r -> System.Math.PI * r * r;;
val it : float -> float = <fuc:clo@10-1>
it 2.0;
val it : float = 12.56
```
fun: reserved word indicates that a function is defined.
r: the identifier ccuring to the left of -> is a pattern for the argument of the function.
Declaration of the cicle-area function could be made:
```
let circleArea = fun r --> System.Math.PI * r * r;;
val circleArea : float --> float
```
#### Function expressions with patterns
convenient to define a function in terms of a number of cases.
**Wildcard pattern**
Function expressed more compactly using a wildcard pattern "_" :
```Fsharp
function
|2 -> 28
|4 -> 30
|6 -> 30
|9 -> 30
|11 -> 30
|_ --> 31;;
```
the function is defined using six clauses.
first clause: 2 -> 28 consist of a pattern 2 and a corresponding expression 28.
next 4 clauses have si,ilar
last clause contains a wildcard pattern:
Applying the function to a value v, the systems find the caluse containing the first pattern that matches v and returns the value of the expression. (matches any other value)
*Wildward with or-pattern*
```Fsharp
function
|2 -> 28
|4|6|9|11 -> 30
|_ --> 31;;
```
the or-pattern 4|6|9|11 matches any of the values, 4,6,9,11 and no other values.
Declaration of the function:
```Fsharp
let daysOfMonth = function
| 2 -> 28
| 4|6|9|11 -> 30
| _ -> 31
;;
val daysOfMoth : int -> int
daysOfMonth 3;;
val it : int = 31
daysOfMonth 9;;
val it : int = 30
```
#### Recursion
The concept of recursion formula and recursive declaration of functions:
```Fsharp
0! = 1
m! = 1*2,..*n for n > 0
```
see p. 6-8 for more math
Recursive declarations
```Fsharp
let rec fact = function
| 0 -> 1
| n -> n * fact(n-1);;
val fact : int -> int
```
The declaration corresponds to the recursion formula for n!
the reserved rec in the let-declaration allows the identifier being declared.
This declaration consists of two clauses
0 -> 1
and
n -> n * fact(n-1)
This patterns are matched with integer aguments during the evoluation of function values.
For example:
``` F#
let rec fact = function
| 0 -> 1
| n -> n * fact(n-1);;
val fact : int -> int
```
#### Pairs
In Math x^n is a function of two variables x and n, but it is treated differently in F# using the concept of a pair.
> If a_1 and a_2 are values of types T1 and T2 then (a_1,a_2) is a value of type T1*T2
for example
```Fsharp
let a = (2.0,3);;
val a (2.0, 3) : float * int
```
given patterns pat_1 and pat_2 there is a composite patteren (pat_1,pat_2).
It matches a pair (a_1, a_2) exackly when pat_1 matches a_1 and pat_2 matches a_2.
```Fsharp
let (x,y) = a;;
val y : int = 3;
val x : float = 2.0
```
The concept of a pair is a special case of tuples.
A function in F# has *one* argument and *one* value.
**Notes on pattern matching**
The *order* of the *clauses* in the declaration of *power* is significant. This will not work
```Fsharp
let rec powerNo = function
| (x, n) -> x * powerNo(x, n-1)
| (x,0) -> 1.0
;;
```
The first pattern (x,n) will match any pair in form (u,i) and the second clause will consequently never come to use.
F# compiler discovers this --> warning.
The function can be applied to an to argument but would give an infinite evauation since the base case (x, 0) -> 1.0 is never reached.
#### Types and type checking
F# will try to infer a type for each value, expression an declaration entered.
Either the system can infer a type for input and accept it or it will not and will reject an give an error message.
> the above consinderation for function application f(e) is a special case of the general type rule for function application
> ```if f has type T1 -> T2 and e has type T1 then f(e) has type T2 ```
#### Bindings and environments
Binding and environment are used to explain that entities are bound by identifiers.
the execution of a declaration: say let x = e causes the identifier x to be bound to the value of the expression e.
The binding is denoted as
```Fsharp
a |-> 3 see book p 14.
```
A collection of binding = environment
```Fsharp
evn = [a |-> 3 ]
[b |-> 7.0]
```
is notation is not part of any program.
Used to explain the meaning of programs.
#### Free-standing programs
A free-standing program contains a *main* function of type:
```Fsharp
string[] -> int
```
preceded by the entry point attribute:
``` Fsharp
...
[<EntryPoint>]
let main (param: string[]) =
...
```
Hello world in F#
``` Fsharp
...
[<EntryPoint>]
let main (param: string[]) =
printf "Hello %s\n" param.[0]
0;;
...
```
#### Currying functions
1. How many arguments does the following fanction take?
``` F#
let f (x,y) = x + y
```
> It takes one argument!
> It takes one pair of two integers
> ``f : (int * int) -> int``
2. How many arguments does the following fanction take?
``` F#
let f x y = x + y
```
> It takes two arguments (sort of)
> ``f : int -> int -> int``
3. How many arguments does the following fanction take?
``` F#
f 5 ~> fun y -> 5 + y
```
This is called partial application
This is important because
- Partial application allows us to specialise a function for future use
- Immensely powerful with first class functions
- There are always edge-cases, but (with very few exceptions) functions should be curried rather than taking one giant tuples as an argument *(Doing so is simply too restrictive)*
### Chapter 2
#### Numbers. Boolean & the `unit` type
F# the set of values with the type: int is disjoint from the set of values with the type: float.
Enconding is different ...
**Oberators**
*oberator* synonym for function and the components of the argument of an operator will be called *operands*.
*monadic* operator is with one operand
*dyadic* operator has two operands.
Division is not defined for integers
``` Fsharp
13 / 5;;
val it : int = -2 // you cannot do this
13 % -5;;
val it : int = 3 // you can do this
```
**Truth values (true or false)**
the type: bool
| Logical operators |
|:----------------- |
| not (unary)negation|
|&& logical and (conjunction)|
|logical or (disjunction))|
functions can have truth values as result.
A truth function such as even is called a *predicate*.
Function on truth values are often called logical operators.
**The unit type**
only one value written () of type unit.
used in F# as a "dummy" result of a computation consisting solely of side-effects like input-output or modifications of mutable data.
#### Operator precedence and association
the monadic operator -minus is written in front of the argument, while dyadic operators are written in infix notation (placed between operands)
predence = just like in math...
Arithmetic operations:
+, - --> unary plus and minus
+, -, *, /, %, ** --> exponentiation
#### Operator precedence and association
#### Characters and strings
char = letter, a digit, special char.
**Strings**
sequence of characters...
**functions on strings**
``` F#
String.length "1234";;
val it : int = 4
String.length "\"1234\"";;
val it : int = 6
```
#### if-then-else expressions
``` F#
if exp1 then exp2 else exp3
```
exp1 type: bool
exp2 & exp 3: same type
if exp1 is true then do exp2
if exp1 is false do exp3
Pattern matching is to preferred.
#### Overloaded functions and operators
a function or operator is overloaded if it has different meanings when applied to arguments or operands of different types.
#### Type inference
F# system will try to determine a unique type using type inference.
if it does not succeed then the expression is not accepted and an error message is issued.
#### Functions are first-class citizens
An implication of this is that a function can be argument of another function and that the value of a function can again be a function.
--> gentle intro to this concept: *higher-order* functions
_____
## Lecture 2: Data types and polymorphism
### Chapter 3: Tuples, records and tagged values
Tuples are used in expression 'functions of serval variables' where the argument is a tuple, and in expression functions where the result is a tuple.
**Tuples**
An ordered collection of n values, where n > 1, is called an n-tuple.
```F#
(10,true);;
val it: int * bool = (10,true)
```
A 2-tuple is also called a pair.
A 3-tuple is call a triple.
A 4-tuple is called a quadruple.
An expression like (true) is not a tuple but just the expression true enclosed in brackets, so there is no concept of 1-tuple.
The symbol () denotes the only value of the type unit.
**Tuple expressions**
A tuple expression (expr1, expr2, ... expN) is obstained by enclosing n expressions expr1, expr2, ... expN in parentheses.
It has type T1*T2*...*TN
**Tuples are individual values**
A tuple expression may contain identifiers that are already bound to a tuple eg:
```F#
let t1 = (true, "abc");;
val t1: bool * string = (true, "abc")
let t2 = (t1, 1, -3);;
val t2 : (bool*string) * int * int = ((true, "abc"), 1, -3)
```
The value bound to identifier t1 is then found as a subcomponent of the value bound to t2.
A fresh binding of t1 is not going to affect the value of t2.
The subcomponent (true, "abc") is a value in its own right and it depends in no way on possible future binding of t1 once the value of the expression t2 has been evaluated.
**Equality**
defined for n-tuples of the same type, provided that equality is defined for the components.
The equality is defined componentwise
```
(v1, v2, ..., vN) is equal to
(v1', v2', ..., vN')
```
This corresponds to equality of the graphs represented by the tuples.
**Ordering**
The ordering operators >, >=, <, <= and the compare function are defined on n-tuples of the same type, provided ordering for the components.
eg:
```
(1, "a") < (1, "ab")
val it: bool = true
(2, "a") < (1, "ab")
val it: bool = false
```
**Tuple patterns**
A tuple pattern represent a graph
The graph represented by the value (3,2) matches the graph for the pattern in the sense that the graph for the value it obtainted from the graph for the pattern.
Patterns can be used on the left side in a let declaration which binds the identifiers in the pattern.
```F#
let (x,n) = (3,2);;
val x : int = 3
val n : int = 2
```
Patterns may contain constants like the pattern (x,0)
It matches any pair (v1, v2) where v2=0
See examples page 47
**Polymorphism (of many forms)**
```F#
let swap (x,y) = (y,x);;
val swap : 'a * 'b -> 'b * 'a
```
The type of swap expresses that the argument (type 'a * 'b) must be a pair and that the value is a pair: (type 'b * 'a).
It contains to values 'a and 'b = polymorphic type
functions like swap = polymorphic function
**Records**
A recond is a generalized tuple where each component is identified by a label instaed of the position in the tuple.
The recond type must be declared before a recond can be made.
```F#
type Person = {age : int; birthday : int * int;
name : string; sex : string};;
```
the keyword: type indicates that this is a type declaration
{} indicates a recond type.
record labels: age, birthday, name, sex
A value of type Person
```F#
let Snerle = {age = 35; birthday = (21,10);
name ="Snerle"; sex = "F"};;
```
This record contains the following fields:
- string "Snerle" with label name
- integer 35 with label age
- string "F" with label sex
- integer (21,10) with label birthday
A record is a local enviroment packaged in a certain way. It contains the binding of each record label to the corresponding value.
**Equality and ordering**
equality of two records with the same type is defined componentwise from the equality of values associated with the same labels.
Hence two records are equal if they are of the same type and contain the same local bindings with labels.
Ordering of records are based on a lexicographical ordering using the ordering of the labels in the records type declarations.
**Record patterns**
A record pattern is used to decompose a record into its fields
The pattern
```
{name = x; age = y; sex = s; birthdat =(d,m)}
```
denotes the graph shown. It generates bindings of identifiers: x,y,s,d,m when matched with a person record.
**Locally declared identifiers**
you can make let inside another let.
See 54-55 for example.
**Operators**
function canc: cancels commom divisors and thereby reduces any fraction with non-zero denominator to the normal satisfying the invariant.
canc is applied to guarantee that resulting values satisfy invariant.
**Tagged values. Constructors**
Tagged values are used when we group together values of different kinds to form a single set of values.
circle, squares, triangles may be group together to form a single collection of shapes if we put a tag on each representing value.
```F#
type Shape = |Circle of float
|Square of float
|Triangle of float*float*float;;
```
The response from F# indicates that Shape names a type, and that Circle, Sqaure and Triangle are bound to value constructors.
These value constructors are functions and they give a tagged value of type Shape when applied to an argument.
**Equality and ordering**
Equality and ordering are defined for tagged values provided they are defined for their components.
Two tagged values are equal if they have the same constructor and their components are equal. This corresponds to equality of the graphs represented by the tagged values.
The sequence in which the tags occur in the declaration is significant for the ordering.
**Constructors in patterns**
Constructors can be used in patterns
```F#
let area = function
|Circle r -> System.math.PI * r * r
|Square a -> a*a
|Triangle (a,b,c) ->
let s = (a+b+c)/2.0
sqrt(s*(s-a))*(s-b)*(s-c));;
val it: Shape -> float
```
The pattern matching treats constructors differently from other identifiers
> A constructor matches itself only in a pattern match while other identifiers match any value
**Enumeratio types**
Value constructors need to have any argument, so we can make special type declaration like:
```F#
type Colour = Red | Blue | Green | Yellow | Purple;;
```
Type like Colour are called enumeration types.
Functions on enumeration types may be declared by pattern matching:
```F#
let niceColour = function
|Red -> true
|Blue -> true
|_ -> true
val niceColour : Colour -> bool
```
**Exceptions**
Raising an exception terminates the evaluation of a call of a function.
It is possible to catch an exception using a try..with expression as in the following solveText function
```F#
let solveText eq =
try
string(solve eq)
with
|Solve -> "No solutions";;
val solveText : float * float * float * float -> string
```
### Chapter 4
At the core of functionel programming.
The concept of a list is a special case of a collection.
#### The concept of a list
A list is a finite sequence of values.
```
[v0; v1; ...; vn-1]
```
of the same type.
[2], [3;2], and [2;3;2] are lists of integers.
A list can contain an arbitrary number of elements.
A list is either empty (when n=0) or it is a non-empty list and can be characterized by the first element v0 called its head. The rest is called its tail.
Notes on the graph:
It shows the list [2; 3; 2] and [2].
The [2; 3; 2] list is hence a tagged pair with tag :: where the first component is the head and the rest is the tail.
**List constants in F#**
```F#
let xs = [2; 3; 2]
val xs : int list = [2; 3; 2]
let xy = ["Big"; "Mac"]
val yx : string list = ["Big"; "Mac"]
```
The type int list and string list, containing the type constructor list indicate that the value of xs is a list of integers. And yx is a list of strings.
We can build list of
- pairs
- records
- functions
- list of lists
- lists can be components of other values.
Examples see 68 in book.
**The type constructor**
The type constructor list has higher precedence than * and -> in the type expression, so that type string * int list means string *(int list)
The type contructor list is used in postfix notation and associates to the left.
All elements in a list must have the same type.
**Equality of lists**
Two list are equal when m=n and x=y.
This corresponds to the equlity of the graphs represented by the lists.
Hence, the order of the elements as well as repetitions of the same value are significant in a list.
The equlity operator = can be used to test equality of two lists provided that the elements of the list are of the same type.
**Ordering of Lists**
List of the same type are ordered lexicograhically, provided there is an ordering defined on the elements.
1. The list xs is a proper prefix of ys
```F#
xs ys
[1; 2; 3] < [1; 2; 3; 4]
val it: bool = true
```
2. The list agree on the first k elements and x_k+1 < y_k+1
```F#
[1; 2; 3; 0; 9; 10] < [1; 2; 3; 4]
val it: bool = true
```
See that at the 4 position we have 0 in the first list.
because 0<4
#### Construction and decomposition of lists
**The cons operator**
The infix operator :: builds a list from its head and its tail
```F#
let x = 2::[3; 4; 5];;
val x : int list = [2; 3; 4; 5]
let y = ""::[];;
val y : string list [""]
```
The operator associates to the right, x0::x1::xs means x0::(x1::xs)
where x0 and x1 have the same type and xs is a list with elements of that type.
```F#
let z = 2::3::[4;5]
val z : int list = [2; 3; 4; 5]
```
**List patterns**
cons also used in list patterns.
patterns and pattern matching for lists are used in the subsequent sections to declare functions on lists by using bindings of identifiers in a list pattern obtained by matching a list to the pattern.
[] list pattern for the empty list
x::xs pattern for non-empty list. Uses the cons operator.
non-empty list pattern gives the bindings x |> x0 and xs |> [x1; ...; x_n-1] of the identifiers x and xs.
**Simple list expressions**
Two simple forms of expressions called:
range expressions:
```F#
[b..e] [b..s..e]
```
where b,e,s are expressions having number types.
[b..e] generates the list of:
```F#
[b; b+1;b+2;...; b+n]
```
where n is chosen such that ```b + n <= e < b + n + 1```
It generates the empty list when e < b.
List of integers from -3 to 5 is generated:
```F#
[-3..5];;
val it : int list = [-3; -2; -1; 0; 1; 2; 3; 4; 5]
```
[b..s..e] generate the list of
```F#
[b; b+s; b+2s;... b+ns]
```
where s is called step. It can either be positive or negative. Not zero.
s determine if the list will be ascending or descending.
```F#
[6..-1..2];;
val it : int list = [6; 5; 4; 3; 2]
or
[6..1..2]
val it : int list = [2; 3; 4; 5; 6]
```
#### Typical recursions over lists
archetypical recursive function declaratins on lists.
**Function declarations with two clauses**
```F#
let rec suml = function
|[] -> 0
|x::xs -> x + suml xs;;
val suml : int list -> int
```
The pattern is convenient in order to split up a function declaratio into clauses covering different forms of the argument.
This above declaration is an example of a typical recursion schema for the declaration of function on lists.
**Function declarations with several clauses**
One can have function declarations with any number >= 1 of clauses.
Example the alternate sum of integer list:
In declaring this function we consider 3 different forms of the argument:
1. empty list: altsum [] = 0
2. list with one element: altsum [x0] = x0
3. list with two or more elements: altsum [x0; x1; x2; ...; xn-1] = x0 -x1 + altsum [x2; ...; xn-1]
List patterns for altsum declaration
```F#
let rec alsum = function
|[] -> 0
|[x] -> x
|x0::x1::xs -> x0 - x1 + altsum xs;;
val altsum : int list -> int
```
**Layered Pattern**
A layered pattern has the general form : pat as id
with pattern pat and identifier id.
A value val matches this pattern when the value matches the pattern pat. (when val == pat)
The matching binds identifiers(id) in the pattern pat as usual with the addition that the identifier id is bound to val.
```F#
let rec succPairs = function
|x0::(x1::_ as xs) -> (x0,x1) :: succPairs xs
|_
val succPairs : 'a list -> ('a * 'a) list
```
The pattern **x1::_as xs** is a layered pattern.
The patterns has the following bindings
```F#
x0 |> x0
x1 |> x1
xs |> [x1;...]
```
**Pattern matching on result of recursive call**
Pattern matching to split the result of a recursive call into components.
```F#
let rec sumProd = function
|[] -> (0,1)
|x::rest ->
let (rSum,rProd) = sumProd rest
(x+rSum,x*rProd);;
val sumProd : int list -> int * int
```
**Pattern matching on pairs of lists**
Declare a function Mix that mixes the elements of two lists
with pattern matching
```F#
let rec mix = function
|(x::xs,y::ys) -> x::y::(mix(xs,xy))
|([],[]) -> []
|_ -> failswith "error";;
val mix : 'a list * 'a list -> 'a list
```
with use of match expression:
```F#
let rec mix xlst ylst =
match (xlst, ylst) with
|(x::xs,y::ys) -> x::y::(mix(xs,xy))
|([],[]) -> []
|_ -> failswith "error";;
val mix : 'a list -> 'a list -> 'a list
```
#### Polymorphism
**List membership**
The member function for lists determine whether a value x is equal to one of the elements in a list.
No x can be a member of the empty list:
```F#
let rec isMember x = function
|y::ys -> x=y || (isMember x ys)
|[] -> false
val isMember : 'a -> 'a list -> bool when 'a : equality
```
'a : equality means: an equality type variable.
**Append (@) and reverse (List.rev)**
infix operator @ joins to lists of the same type.
List.rev reverses a list.
example of @:
```F#
[1;2] @ [3;4]
val it : int list = [1; 2; 3; 4]
```
@ is the same as ::
the List.rev will change the order from
```F#
[1; 2; 3; 4] to [4; 3; 2; 1]
```
**The value restriction on polumorhpism expressions **
Restrictions based on the concept of value expressions.
A value expression is an expression that is not reduced further by an evaluation.
Example:
[], Some [], (5,[]) (fun x -> [x])
> At top level, polymorphic expressions are allowed only if they are value expressions. Polymorphic expression can be used freely for intermediate results.
- All nonmorphic expressions are OK, even non-value expressions
- All expressions are OK, even polumorphic ones
- at top-level, polumorphic non-value expression are forbidden.
monomorphic expressions does not contain type variables.
-----
The notes for chapter 5.1 is under lecture 3: Collections and Algebraic Datatypes
## Lecture 3 : Collections and Algebraic Datatypes
### Chapter 5
#### Lists
Declarations of the library functions are not considered as we want to concentrate on how to use these functions in problem solving.
**The map function**
> The function application List.map f is the function that applies the function f to each element x0,x1,x2,...,xn-1 in a list [x0;x1;x2;...;xn-1]
**Functions using a predicate on the list elements**
```F#
List.exists : ('a -> bool) -> 'a list -> bool
List.forall : ('a -> bool) -> 'a list -> bool
List.tryFind : ('a -> bool) -> 'a list -> 'a option
List.filter : ('a -> bool) -> 'a list -> 'a list
```
see examples at 96 in book...
**The functions fold and foldBack**
---
**Fold**
A package may contain 0 to many cheeses.
```F#
packChesse : package -> cheese -> package
```
The function List.fold can be applied to the function package and a list of cheeses.
Use packCheese to pack the elements of the list into the package one after the other.
> The evaluation of List.fold f e [x0; x1;...; xn-1] accumulates the list elements x0,x1,...,xn-1 using the accumulation function f and the start value e
The type of fold:
```F#
List.fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
```
when applying List.fold --> look for the following entities:
- List element type 'b -> cheese
- Accumulator type 'a -> package
- Accumulatpr function f -> packCheese
- Start value e -> empty package
It has the types as folloes:
- float * float
- float
- fun s (x,y) -> s + norm(x,y) see book 98
- 0.0
Applying fold to the following version of "cons"
```F#
fun rs x -> x::xs
reverse function for lists:
let rev xs = List.fold (fun rs x -> x::xs) [] xs;;
val rev : 'a list -> 'a list
```
---
**Foldback**
List elements are accumulated in opposite order.
so
```F#
cheesePack : cheese -> package -> package
```
foldBack can be applied to the function cheesePack. a list of cheeses and a start package.
It uses cheesePack to pack elements of the list taken in reverse order.
>The evaluation of List.foldBack g [x0; x1; ...; xn-1] e accumulates the list elements in reverse order xn-1...x2,x1,x0 using the accumulation function g and the start value e.
Applying List.foldBack on the cons operator:
```F#
fun x xs -> x::xs
```
gives the append function:
```F#
let app ys zs = List.foldBack(fun x xs -> x::xs) ys zs;;
val app : 'a list -> 'a list -> 'a list
app [1;2;3] [4;5;6];;
val it : int list = [1; 2; 3; 4; 5; 6]
```
____
declaration of fold and foldBack
```F#
let rec fold f e = function
|x::xs -> fold f (f e x) xs
|[] -> e;;
let rec foldBack g xlst e = match xlst with
|x:: xs -> g x (foldBack g xs e)
|[] -> e;;
```
You can see the evaluation on page 103...
#### Finite sets
Note quick read thourgh of sets in general from 104-105
**Sets in F#**
finite sets of elements of a type where ordering is defined and provides efficient implementation for a rich collection of set operations.
```F#
set ["Bob"; "Bill"; "Ben"];;
val it : Set<string> = set ["Ben"; "Bill"; "Ben"]
```
See how the operations work on page: 106-110
#### Maps
Use finite functions to uniquely associate values with keys.
such are called maps.
Information about the math behind maps: 113-114
**Maps in F#**
support maps of polymorphic types ``` Map<'a; 'b>``` where 'a and 'b are the type of the keys and values.
Implemented by using balanced binary trees.
If it contains multiple entries for the same key, then the last occurring entry is the significant one.
```F#
Map.ofList [(1,"a"); (2,"b"); (2,"c")]
val it : Map<int,string> = map [(1,"a"); (2,"c")]
```
The list of entries of a map is achieved using the Map.toList function.
```F#
let l = Map.ofList [(1,"a"); (2,"b"); (2,"c")];;
Map.toList l;;
val it: int * string list = [(1,"a"); (2,"b"); (2,"c")]
```
An entry can be added to a map using add.
use find or tryFind to retrieve a value for a key.
If fail: find --> raise ecception. tryFind return none.
```F#
Map.find 1;;
val it : string = "a"
```
```F#
Map.tryFind 1;;
val it : string = "a"
```
Overview over most useful methods on Maps.
### Chapter 6
Structures that may contain subcomponents of the same type. A list is an example of a tree.
The list 1::[2;3;4] contains subcomponents [2;3;4] that also a list.
in F# use a recursive type declaration to represent a set of values which are trees.
#### Chinese boxes
Coloured cube that contains a coloured cube or contains nothing.
A cube characterised by its: side length, colour and the contained Chinese box.
The set Cbox of chinese boxes are defined by rules:
1. The tree Nothing is in CBox
2. if r is a float number, if c is a colour, and if cb in CBox, then the tree:
is also in CBox.
3. The set CBox contains no other values than the trees generated by repeaterd use of Rule 1 and Rule 2.
How to create elements of Cbox:
Step a: The void tree Nothing is a member of CBox by rule 1.
Step b: The following tree is a member of CBox by step a and rule 2.
Step c: The tree is a member of CBox by step b and Rule 2.
Step d: The tree is a member of CBox by step c and Rule 2.
**Type declaration**
```F#
type Colour = Red | Blue | Green | Yellow | Purple;;
type CBox = |Nothing
|Cube of float * Colour * CBox;;
```
The declaration is recursive. The declared type CBox occurs in the argument type of the constructor Cube.
The constructors Cube and Nothing corresponds to the Rules 1 and 2.
We note from Rule 3:
- Different values of type CBox represent different trees.
- Any tree is represented by a value of type CBox.
**Patterns**
Constructors for trees can occur in patterns.
Example of a tree pattern is ```Cube(r,c,cb)``` containing identifiers r,c and cb for the components.
The inductive definition of trees implies that any tress will either match the empty tree:
```Nothing```
or the tree pattern for a cube
```Cube (r,c,cb)```
**Function declarations**
declaration of the function:
```F#
count : CBox -> int
```
such that the value of expression ```count(cb)``` is the number of cubes in the Chinesebox cb:
```F#
let rec count = function
|Nothing -> 0
|Cube(r,c,cb) -> 1 + count cb;;
val count : CBox -> int
```
**Insertion function**
Declaration of an insertion function:
```F#
insert : float * Colour * CBox -> CBox
```
value of expression ``ìnsert(r,c,cb)```is the Chinese box obtained from cb by inserting an extra cube with side r, colour c.
The function is partial function -> raises exception in case insertion violates the invariant for CBoxes.
```F#
let rec insert(r,c,cb) =
if r <= 0.0 then failwith "ChineseBox"
else match cb with
|Nothing -> Cube(r,c,Nothing)
|Cube(r1,c1,cb1) ->
match compare r r1 with
|t when t > 0 -> Cube(r,c,cb)
|0 -> failwith "ChineseBox"
|_ -> Cube(r1,c1,insert(r,c,cb1));;
```
#### Symbolic differentiation
I will writes notes if I see that we need it...
I have read it.
It is from 127-131
#### Binary trees. Parameterized types
The constructor is a type declaration may have polymorphic types containing type variables.
These type variables are parameters of the type, written in brackets <..>
```F#
type BinTree<'a, 'b> =
|Leaf of 'a
|Node of BinTree<'a, 'b> * 'b * BinTree<'a, 'b>;;
```
```F#
let t1 = Node(Node(Leaf 1, "cd", Leaf 2),"ab", Leaf 3);;
```
of type ```BinTree<int,string>```
The top node element "ab" is the root of the tree t1.
```F#
let t2 = Node(Leaf 1, "cd", Leaf 2);;
let t3 = Leaf 3;;
```
are called the left sub-tree and the right sub-tree of t1.
The constrcutors ```Node```and ```Leaf``` can be used in patterns:
```
Leaf x
Node (t1, x, t2)
```
Declaration of the depth of a binary tree:
```F#
let rec depth = function
|Leaf_ ->
|Node(t1,_t2) -> 1 + max (depth 1) (depth t2);;
val depth : BinTree<'a, 'b> -> int
```
#### Traversal of binary trees. Search trees
A traversal of a binary tree is a function that visits the nodes of the tree in a certain order.
Uses the simplified BinTree:
```F#
tyep BinTree<'a> = |Leaf
|Node of BinTree<'a> * 'a * BinTree<'a>;;
```
tree of this type then described by a function of type:
```F#
BinTree<'a> -> 'a list
```
3 kinds og traverals:
1. Pre-order traveral: First visits the root node, then traverse the left sub-tree in pre-order and finally traverse the right sub-tree in pre-order.
```F#
let rec preOrder = function
|Leaf -> []
|Node(t1,x,tr) -> x:: (preOrder t1) @ (preOrder tr);;
```
2. In-order traveral: First traverse the left sub-tree in-order, then visit the root node and finally traverse the right sub-tree in in-order.
```F#
let rec inOrder = function
|Leaf -> []
|Node(t1,x,tr) -> x:: (inOrder t1) @ [x] @ (preOrder tr);;
```
3. Post-order traversal: First traverse the left sub-tree in post-order, then traverse the right sub-tree in post-order and finally visit the root node.
```F#
let rec postOrder = function
|Leaf -> []
|Node(t1,x,tr) -> x:: (postOrder t1) @ (postOrder tr) @ [x];;
```
**Search trees**
Rescrict the type variable 'a in our BinTree to types with an ordering:
```F#
type BinTree<'a when 'a : comparison> =
|Leaf
|Node of BinTree<'a> * 'a * BinTree<'a>;;
```
It is a search if:
Every node ```Node(tLeft,a tRight)```satisfies:
```
a' < a for every value 'a occurring in tLeft and
a'' > a for every value a'' occuring in tRight
```
^^search tree invariant.
A search tree can be used to represent a finite set. It is efficient when trees are balanced.
#### Expression trees
see page 137-138
#### Mutual recursion
trees with a variable number of sub-tree are obtainted by using a type where each node contains a list of sub-trees.
```type ListTree<'a> = Node of 'a * (ListTree<'a> list);;```
The values LIstTree type represent trees where:
- ```Node(x,[])```represent a leaf tree containing the value x
- ```Node(x,[t0;t1;...;tn-1])```represent a tree with value x in the root and with n sub-trees represented by the values t0,...tn-1
**Traversal of list trees**
2 kinds: depth-first and breadth-first.
depth-first: 1,2,5,3,5,6,7
breadth-first: 1,2,3,4,5,6,7
see page 139 for fold and foldBack on depth-fist
and page 140 for fold and foldBack on breadth-first
#### Electrical circuits
Electrical circuits built from components by serial or parallel composition.
```F#
type Circuit<'a> = | Comp of 'a
| Ser of Circuit<'a> * Circuit<'a>
| Par of Circuit<'a> * Circuit<'a>
```
How to write in F#:
```F#
let cmp = Ser(Par(Comp 0.25), Comp 1.0), Comp 1.5);;
val cmp : Circuit<float>
= Ser(Par(Comp 0.25), Comp 1.0), Comp 1.5)
```
define a function count for computing the number of components in a circuit:
```F#
let rec count = function
|Comp _ -> 1
|Ser(c1, c2) -> count c1 + count c2
|Par(c1, c2) -> count c1 + count c2;;
```
**Tree recursion**
Functions count can be expressed using a generic higher-order function: circRec for traversing circuits.
The function must be parameterized with 3 functions c,s,p
```
c: 'a -> 'b //The value for a single component
s: 'b -> 'b -> 'b // the combined value for 2 circuits connected in series
p: 'b -> 'b -> 'b //The combined value for 2 circuits connected in parallel
```
The declaration of the function:
```F#
let rec circRec (c,s,p) = function
|Comp x -> c x
|Ser(c1, c2) -> s (circRec (c,s,p) c1) (circRec (c,s,p) c2)
|Par(c1, c2) -> p (circRec (c,s,p) c1) (circRec (c,s,p) c2))
```
## Lecture 4: Modules and imperative programming
### Chapter 7: Modules
**Abstraction**
Key concept in designing a good program: Abstraction.
It must provide a service where a user can get a general understanding og what a libary function is doing.
Abstrations semantantical:
- Description of a collection of entities to be represented by and F# type.
- Description of specific values and computations to be implementented by F# values and functions.
Modules:
Technical means of dividing a programming problem into smaller parts.
Guided thorugh the use of abstractions
- A general, narrative description of the conceptual framework
- A presice, but short description of the intended working of each type, value and function.
**Files and compliation**
Overview
```
FileName.fsi F# signature file Text file edited by programmer
FileName.fs F# implementation file Text file edited by programmer
FileName.dll Library file Binary output file from F# compiler
```
**Type augmentation. Operators in modules**
Type augmentation adds declarations to the definition of a tagged or record type.
How to do it...
Member: cannot intermixed with let declarations.
Make, coord, norm: specified and implemented.
Note on it:
- the attribute "Sealed" is mandatory when a type augmentation is used.
- The heading "|" in the type declaration must be the same in the indentation level.
**Type extension**
We can use use type extension:
```F#
type ... with ...
```
**Classes and objects**
A class defintion looks syntactically like an augmented type dinition where the type expression has been removed and replaced with a declaration of a constructor.
see 156-157 for syntax example.
**Parameterized modules. Type variables in signatures**
A module can be parameterized by type variables and may thereby polumorphic types, values and functions.
see queue example from 157-159 in book.
**Customizing equality, hashing and the string function**
F# compiler will automatically generate a default equality operator.
This default equality operator is not the wanted operator because it distinguishes values that we want to consider equal. (so not a eqaul = as we know it)
Do not understand the text.
**Customizing ordering and indexing**
you can customize the ordering: q1 < q2 and indexing: q*[n] on values of a defined type.
Use a suitable type augmentation.
The corresponding type augmentation in the queue.
The ordering is declared by overiding the CompareTo methods in the IComparable interface.
The implementation uses list indexing in the list of queue elements in insertion order.
The signature: ```member Item : int -> 'a with get```
### Chapter 8: Imperative features
Express commands using and modifying the state of mutable objects.
Explained using a new components: the store.
A store consists of a set of locations containing values, together with operators to access and change the store.
The concept of mutable record fields gives the means of assigning values to object members.
**Locations**
A mutable location is a part of the computer memory.
A location is obtained by executing a let mutable declaration:
```F#
let mutable x = 1;;
val mutable x : int = 1
```
The keyword mutable requests F# to create a location, and the answer tells that x is bound to a location of type int, currently containing the value 1.
A set of locations with contents is called a store.
**Operators on locations**
An assignment expression exp1 <- exp2 is evaluated as followed:
1. Evaluate exp1 to get a location loc.
2. Evaluate exp2 to get a value v
3. Store the value v in the location loc
4. Deliver the value () of type unit as the result.
```F#
x <- 7;;
val it : unit = ()
```
The evaluation procedes as:
```F#
x <- 7 x |> loc1 loc1: 1
~~> loc1 <- 7 x |> loc1 loc1: 1
~~> () x |> loc1 loc1: 7
```
Side effect: the content of the location loc1 is changed.
It is not visible in the result which is just the uninteresting value () of type unit.
A contentsOf expression exp is evaluated as follows:
1. Evaluate exp to get a location loc.
2. Deliver the contents v of the location loc as the result.
The contentsOf operator has no visible symbol and the operator is automatically inserted by the compiler following the rule.
> A contentsOf operator is automatically inserted by the F# compiler whenever a location occurs in a context where a value is required. The right-hand side of a let-declaration is such a context
**Default values**
A mutable declaration requires an initial value to be stored in the location.
This value is obtained by evaluating the expression on the right-hand side of the declaration.
```F#
Unchecked.defaultof<type>
```
**Sequential composition**
A single semicolon: ;
denotes the sequential composition operator.
It combines 2 expressions to form a new expression
```
exp1 ; exp2
```
evaluated as follows:
1. Evaluate exp1 and discard the result
2. Evaluate exp2 and suply the result as the result of evaluatiing exp1 ; exp2
The compiler issues a warning if exp1 if odf type different from unit. Warning is avioded by using the ignore function:
```F#
ignore(exp1) ; exp2 or exp1 |> ignore ; exp2
```
**Mutable record fields**
A mutable record field is obtained by prefixing the label in record type declaration by the keyword mutable:
```F#
type intRec = {mutable count : int}
let r1 = {count = 0}
val r1 : intRec = {count = 0;}
```
creates the following entities:
1. A value (record) of type intRec
2. a location containing the value 0
3. a local binding inside the record of the record label count to the location
4. a binding of the identifier r1 to the record.
**References**
compiler does not accept use of locally declared mutables in locally declared functions.
The ref type provides a shorthand for a record type containing a single mutable field, and the ref function provides a value for this type.
```F#
type 'a ref = {mutable content: 'a }
let ref v = {contents of v}
```
**While loops**
If b denotes a expression of type bool
and e denotes an expression of any type:
```F#
while b do e
```
will be an expression of type unit.
evaluation:
1. Evaluate the expression b.
2. if the result is true, then evaluate the expression e and repeat the evaluation of the epxression: while b do e.
3. if false then terminate the evaluation and return result ().
Useful when evaluated in a context where some identifers are bound to mutables.
The expression e should contain assignment to some of these mutables
and b comprises tests of some of their values.
**Imperative functions on lists and other collections**
F# lib contains to functions: iter and iteri on lists.
```F#
List.iter: ('a -> unit) -> 'a list -> unit
List.iteri: (int -> 'a -> unit) -> 'a list -> unit
```
used to interate the effect of an imperative function over the elements of a list.
See how on page 184 in the book.
**Imperative tree traversal**
not much to write about
see page 185 for example
**Arrays**
An array of lenght n consists of n locations loc0,loc1,..., locn-1 of the same type.
the type of array: ```T []``` where T is the type of the elements.
Pros and cons with arrays:
- any array location can be accessed and modified in constant time.
- An array is a mutable object. The old value is lost when modified.
- cannot be extended by more elements in a simple way.
How to create an array:
```F#
let a = [|1;2;3;4|];;
val a : int [] = [|1;2;3;4|]
Array.create 5 3;;
val it : int [] = [|3;3;3;3;3|]
Array.init 5 (fun x -> x*2);;
val it : int [] = [|0;2;4;6;8|]
```
How to update an array:
```F#
let arr = Array.create 5 3;;
val arr : int [] = [|3; 3; 3; 3; 3|]
arr.[3] <- 42;;
val it : unit = ()
arr;;
val it : int [] = [|3; 3; 3; 42; 3|]
```
Overview over operations on arrays
**Imperative set and map**
## Lecture 8: Parser combinators
### The "Understanding Parser COmbinators" series
#### 1. Understanding Parser Combinators
The basic concepts of parser combinators and build the core of the library
**Parsing a hard-coded character**
How it works:
- the input to a parser is a stream of characters. We could use something complicated, but for now just a "string".
- If the stream is empty, then return a pair of consisting of "false" and an empty string.
- if the first character in the stream is an "A", then return a pair consisting of "true" and the remaining stream of characters.
- If the first character in the stream is not an "A", then return "false" and the (unchanged) orginal stream of characters.
``` F#
let parseA str =
if String.IsNullOrEmpty(str) then
(false,"")
else if str.[0] = 'A' then
let remaining = str.[1..]
(true,remaining
)
else
(false,str)
```
The signature of "parseA" is
```F#
val parseA : string -> (bool * string)
```
This tells us that the input is a string and the output is a pair consisting of the boolean result and another string (the remaining input)
**Parsing a specified character**
This time return a message indicating what happened.
We’ll call the function pchar for “parse char”. This will become the fundamental building block of all our parsers. Here’s the code for our first attempt:
```F#
let pchar (charToMatch,str) =
if String.IsNullOrEmpty(str) then
let msg = "No more input"
(msg,"")
else
let first = str.[0]
if first = charToMatch then
let remaining = str.[1..]
let msg = sprintf "Found %c" charToMatch
(msg,remaining)
else
let msg = sprintf "Expecting '%c'. Got '%c'" charToMatch first
(msg,str)
```
This tells us that the input is a pair of (string, character to match) and the output is a pair consisting of the (string) result and another string (the remaining input)
Lets test it:
A best case:
```F#
let inputABC = "ABC"
pchar('A',inputABC)
result: ("Found A", "BC")
```
A worst case:
```F#
let inputZBC = "ZBC"
pchar('A',inputZBC)
result: ("Expecting 'A'. Got 'Z'", "ZBC")
```
**Returning a SUccess/Failure**
Want to be able to tell the difference between a successful match and a failure, and returning a stringly-typed message is not very helpful.
lets use a choice type (discriminated union) to indicate the difference:
```F#
type ParseResult<'a> =
| Success of 'a
| Failure of string
```
The "Success" case is generic and can contain any value.
The "Failure" case contain an error message
Rewrite the parse to now return one of the "Result" cases:
```F#
let pchar (charToMatch,str) =
if String.IsNullOrEmpty(str) then
Failure "No more input"
else
let first = str.[0]
if first = charToMatch then
let remaining = str.[1..]
Success (charToMatch,remaining)
else
let msg = sprintf "Expecting '%c'. Got '%c'" charToMatch first
Failure msg
val pchar: (char * string) -> ParseResult<char * string>
```
this tells us that the output is now a "ParseResult".
A diagram of the function's inputs and outputs now:
**Switching to a curried implementation**
In functional languges it is moer idiomatic to use a curried version:
```F#
let pchar charToMatch str =
if String.IsNullOrEmpty(str) then
Failure "No more input"
else
let first = str.[0]
if first = charToMatch then
let remaining = str.[1..]
Success (charToMatch,remaining)
else
let msg = sprintf "Expecting '%c'. Got '%c'" charToMatch first
Failure msg
val pchar : char -> string -> Result<char * string>
```
The diagram over that:
**Rewirting with an inner function**
Sign in with Wallet
Connect another wallet