# Functionel Programming - Notes to slides
###### 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 : bogen : Data types and polymorphism
### Chapter 3: Tuples, records and tagged values
### Chapter 4
### Chapter 5.1
## Helles Noter til List.
**Example**
``` F#
> [5; 3; -23];;
val it : int list = [5; 3; -23]
> [System.Math.PI; 0.0]
val it : float list = [3.141592654, 0.0]
```
**List constructors**
- List are generated as follows:
- [] is the empty list
- x :: xs is a list with *head* x and *tial* xs
- e.g
`5 :: [3; -23] = [5; 3; -23]`
``` F#
> 5 :: 3 :: -23 ::[];;
val it : int list = [5; 3; -23]
```
**Summing a list**
- How do we define a function sumList that adds up the elements of a list?
``` F#
> sumList [5; 3; 2];;
val it : int = 10
```
- What should the results of the following two calls of sumList be? (Answeared :wink:)
``` F#
sumList [] = 0
sumList (x :: xs) = x + sumList xs
```
- From these two equations we can read off the recursive implementation:
``` Fsharp
let rec sumList =
function
| [] -> 0
| x :: xs -> x + sumList xs
```
**Appending lists**
- We can join lists using @
``` Fsharp
> [5; 3]@(-23::[]);;
val it : int list = [5; 3; -23]
```
## Lecture 2 : slides : Data types and polymorphism
### Last week
We introduced functional programming
- Functions are first-class citizens
- Keep side effects to a minimum
- Type inference vs type checking
- Recursive functions rather than loops
### Goals of the week
* You can define and use higher-order functions.
* You understand polymorphism in F#.
* You can use simple structured data like tuples and lists.
* Be able to create examples using data types and lists
* Be comfortable programming with recursion
### Some observations
#### Imperative languages are typically structured around statements and expressions
**Statements:**
``` F#
if (x > 4) then
return "get4"
else
return "lt4"
return "gt4" -> statement
return "lt4" -> statement
```
**Expressions:**
``` F#
x > 4 -> expression
```
Many things can be part of expressions
- Function declarations
- if-statements
- Matches
- Calculations
#### Expressions and statements are not interchangeable
``` F#
"result is: " +
if (x > 4) then
return "gt4"
else
return "lt4"
```
**IS NOT a vaild program**
#### Expressions and statements are more expression oriented
``` F#
"result is: " +
if (x > 4) then
"gt4"
else
"lt4"
```
**IS a vaild program**
### Anonymous functions
Functions can be used as values or parameters to other functions just like standard integers or booleans
So we also have expressions that define functions, without declaring them with a name.
Function expressions with general patterns
``` F#
function
| [] -> "Empty"
| [x] -> "One"
| [x;y] -> "Two"
| [x; y; z] -> "Three"
| _ -> "Many"
```
returns a function that has type *a* list -> string
*This function is polymorphic (⍺ list) where ⍺ can be any type (int, bool, another list, …). F# writes ‘a, ‘b, ‘c in ascii where we write ⍺, β, and ɣ in plain text
We will cover polymorphism shortly*
#### Simple function expression
``` F#
fun r -> System.Math.PI * r * r
```
returns a function that has type float -> float
#### Currying
``` F#
fun x y z -> x + y + z
```
returns a function that has type int -> int -> int
is the same function as
``` F#
fun x -> fun y -> fun z -> x + y + z
```
which is the same function as
``` F#
fun x y -> fun z -> x + y + z
```
### Function composition
#### Function declarations
``` F#
let f x = e
means
let f = fun x -> e
```
Conceptually NO differenct to other declarations
``` F#
let a = 5
let b = true
let c = 'Q'
let d = (5, "meters")
let e = 2,781345
let f = fun x -> x + 3
```
#### Infix operators
Infix operators ⊕ have prefix versions (⊕)
and are curried
``` F#
(+) : int -> int -> int
(-) : int -> int -> int
(*) : int -> int -> int
(/) : int -> int -> int
```
These all have overleaded versions for other (but always the same) numeric types
``` F#
(+) 5 6
is the same as
5 + 6
```
Infix operators can be partially applied
``` F#
(+) 5
is the same as
fun x -> 5 + x
```
You can define your own infix operators
``` F#
let (.+.) = fun x y -> x + y
or
let (.+.) x y = x + y
```
*Many for the next assignment* :wink:
#### Function composition
Functions can be composed in mathematics we write
```
(f ◦ g)(x) = f(g(x))
```
In F# we write
``` F#
f << g
or
g >> f
```
*The arrow point towards the outermost function*
##### Example
#### Operators |> and <|
The operator |> means “send the value as argument to the function on the right”
```
x |> f is equivalent to f x`
```
The operator <| means “send the value
as argument to the function on the left”
```
f <| x is equivalent to f x
```
*This just semmes like wasted effort... x |> f is arder to read then f x*
### Types and exceptions
It is possible to declare your own types and exceptions
Theres is 3 ways to do this Tuples, Records and Tagged
Tuples, records and
tagged values are treated as “first-class citizens” in F#: They can enter into expressions and
the value of an expression can be a tuple, a record or a tagged value. Functions on tuples,
records or tagged values can be defined by use of patterns.
#### Tuples
Tuples are used in expressing “functions of several variables” where the argument is a tuple, and in expressing functions where the result is a tuple
**Example**
``` F#
(10, true);;
val it : int * bool = (10, true)
(("abc",1),-3);;
val it : (string * int) * int = (("abc",1),-3)
```
#### Tagged
Tagged values are used when we
group together values of different kinds to form a single set of values
#### Example
### Nested let-statements
Nested let-statements let us reuse results from previous computations
>*Indentation Matters!*
Typically useful for local functions
``` F#
let power x n =
let rex aux =
funtion
| 0 -> 1.0
| m -> x * aux (m - 1)
aux n
```
### Records
Records allow us to structure data
``` F#
type person =
{ firstname : string;
lastname : string;
age : int }
```
Records can be of arbitrary size
Records are declared by proviiding input to all of their fields (no partial application)
``` F#
let Olga =
{ firstname = "Olga";
lastname = "Jensen";
age = 67; }
val Olga : person =
{ firstname = "Olga";
lastname = "Jensen";
age = 67; }
```
> *All field names must match with an already declared type*
Indvidual fields are accessed using their name
``` F#
Olga.firstname;;
val it : string = "Olga"
Olga.lastname;;
val it : string = "Jensen"
Olga.age;;
val it : int = 67
```
#### let-patterns
It is possible to obtain values from compound statements
``` F#
let { firstname = fn;
lastname = ln;
age = x} = Jesper in
(fn, ln, x);;
val it : string * string * int = (“Jesper", "Bengtson", 41)
or
let (a, b) = (5, true) in (b, a);;
val it : bool * int = (true, 5)
```
### Polymorphism
Consider the function swap interchaning the components of a pair:
``` F#
let swap (x,y) = (x,y);;
val swap : 'a * 'b -> 'b * a'
swap ('a',"ab");;
val it : string * char = ("ab", 'a')
swap ((1,3), ("ab", true));;
val it : (string * bool) * (int*int) = ((1,3), ("ab", true))
```
The examples show that the function applies to all kinds of pairs. This is reflected in the type
of the function: ’a * ’b -> ’b * ’a.
The type of swap expresses that the argument (type ’a * ’b) must be a pair, and that
the value will be a pair (type ’b * ’a) such that the first/second component of the value is
of same type as the second/first component of the argument.
The type of swap contains two type variables ’a and ’b. A type containing type variables is called a polymorphic type and a function with polymorphic type like swap is called a polymorphic function. Polymorphic means “of many forms”: In our case the F# compiler is able to generate a single F# function swap working on any kind of pairs and which is hence capable of handling data of many forms.
**Polymorphism** is related to overloading as we in both cases can apply the same function name or operator to arguments of different types, but an overloaded operator denotes different F# functions for different argument types (like + denoting integer addition when applied to int’s and floating-point addition when applied to float’s).
### Lists
#### List constructors
Recall hat lists are generated as follows
- [] is the empty list
- x::xs returns a list with head x and tail xs
``` F#
> 5::3::-23::[];;
val it : int list = [5; 3; -23]
```
#### Length of a list
We recurse over the constructors
``` F#
let rec length =
function
| [] -> 0
| x::xs -> 1 + length xs
```
*Has type a list -> int*
#### Appending lists
We recurse over the constructors
``` F#
let rec (@) xs ys =
match xs with
| [] -> ys
| x::xs -> x :: (xs @ ys)
```
*Has type a list -> a list -> a list*
#### Higher-order functions
- Higher-order functions are functions that take other functions as arguments (we have seen a few, |>, <|, >> and <<, for instance)
- With lists these become very powerful and elegant
- What we show here is also available for other datatypes (maps, sets, arrays, …)
##### Patterns
They follow the same pattern - given a list
`[x1; x2; ...; xN]`
and a function f, they return
`[f x1; f x2; …; f xN]`
##### Maps
List.map is a library function
Given a function f,
``` F#
List.map f [x0; x1; ...; xN-1]
```
return
``` F#
[f x0; f x1; ...; f xN-1]
```
**Example**
##### Maps vs for loops
In general a loop of this shape
``` F#
for(int i = 0; i<xs.Length, i++)
{
ys[i] = f (xs[i]);
}
```
is replaced be map like this
``` F#
let ys = map f xs
```
#### Filters
For a predicate
``` F#
p : 'a -> bool, filter p [x1; x2; ...; xN]'
```
returns a list of all elements xi such that p xi = true
**Example**
#### Exists
For a predicate
``` F#
p : 'a -> bool, exists p [x1; x2; ...; xN]'
```
returns true if there is an element xi such that p xi holds, and false otherwise
**Example**
#### Forall
For a predicate
``` F#
p : 'a -> bool, forall p [x1; x2; ...; xN]'
```
returns true if p xi holds for all elements xi, and false otherwise
**Example**
#### Foldback (loops)
For a function f and an initial value acc,
``` F#
foldback f [x1; x2; ...; xN] acc
returns
f x1 (f x2 ( ... f xN-1 ( f xN acc)...))
```
This particular fold is called a foldBack in F# because it starts at the end of the list
**Example**
#### Folds (loops)
For a function f and an initial value acc,
``` F#
fold f acc [x1; x2; ...; xN]
returns
f (...(f (f acc x1) x2) ... xN-1) xn
```
**Example**
### Piping and HoFs
A typical way to write functional programs is as a pipline of higher-order functions
``` F#
xs |> map (f >> g) |> fold h y
```
*Create a function that given a list of second degree polynomials (as defined before), return the smallest non-negative root smaller than 100*
> Start with the list of polyminals
> Solve the polynomials
> Flatten the list of solutions - rather than a list of pairs of roots return a list of roots
> Remove all roots smaller than zero
> Return the smallest root that is smaller than 100.0
> See solution:
> ``` F#
> sdps
> |> List.map solve
> |> List.fold (fun acc (a,b) -> a::b::acc) []
> |> List.filter ((<) 0.0)
> |> List.fold min 100.0
> ```
### Tuples and patterns
These two function expressions are identical:
## Lecture 3
### Agenda
- Collections (sets and maps)
- Inductively defined datatypes
- Expression trees
- Live coding
### Collections
F# has support for all collections from the .NET framework
- Lists
- Sets
- Maps
- Hash tables
#### Sets
- Represents mathematical sets
- Intersection, union, ...
- Not mutable
- Unordered
- Can only store values of comparison type
- Created inline by `Set.ofList [a1; a2; ...; an]`
##### Sets (some functions)
``` F#
Set.empty: Set<a>
Set.singleton: a -> Set<a>
Set.union: Set<a> -> Set<a> -> Set<a>
Set.intersect: Set<a> -> Set<a> -> Set<a>
Set.contains: a -> Set<a> -> bool
```
##### Sets (HoFs)
```F#
Set.map: (a -> b) -> Set<a> -> Set<b>
Set.filter: (a -> bool) -> Set<a> -> Set<a>
Set.fold: (b -> a -> b) -> b -> Set<a> -> b
```
#### Maps / dictionaries
- Represents mathematical maps
- add, lookup, ...
- Not mutable
- Unordered
- Can only have keys of camparison type
##### Maps (some functions)
``` F#
Map.empty: Map<a, b>
Map.add: a -> b -> Map<a, b> -> Map<a, b>
Map.find: a -> Map<a, b> -> b
Map.map: (a -> b -> c) -> Map<a, b> -> Map<a, c>
Map.filter: (a -> b -> bool) -> Map<a, b> -> Map<a, b>
Map.fold: (c -> a -> b -> c) -> c -> Map<a, b> -> c
```
#### Higher-order functions
For lists you can potentially get away without using higher-order functions by using recursion
For sets and maps you still can (translate them to lists, work on the lists and then translate them back) but this is a **really** bad idea.
Practice using higher-order functions :)
##### Example: Relations
Relations are sets of tuples `Set<a * b>`
This allows to have many ’a related to many ’b
Example: items and producers
``` F#
let producedBy : Set< ItemId * ProducerId >
```
*In Relational Databases it is called a many-to-many relation.*
**Some relations are more specific**
``` F#
let teachers : Map< TeacherId , Name >
```
There shouldn’t be teachers with the same
Id but different names.
More accurate:
``` F#
let teachers : Set<TeacherId, Name>
```
*This is a many-to-one relation.*
### Inductively defined types
- ... or algebraic datatypes
- ... or disjoint unions
Allow us to concisely say hoe members of types are created
``` F#
type month =
| January | February | March | April | May | June | July | August | September | October | November | December
type weekDay =
| Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
```
> *Observation 1*
>We use 'type', not 'let'
> *Observation 2*
> Behave similarly to enum-types in Java
``` F#
let numberOfDays =
function
| January | March | May | July | August | October | December -> 31
| February -> 28
| _ -> 30
```
> We can pattern match on algebraic types
``` F#
let nextWeekday =
function
| Monday -> Tuesday
| Tuesday -> Wednesday
| Wednesday -> Thursday
| Thursday -> Friday
| _ -> Monday
```
#### Arguments
Algebraic types can take arguments
``` F#
type shape =
| Circ of float (* radius *)
| Rect of float * float (* sides *)
let area =
function
| Circ r -> System.Math.PI * r * r
| Rect (w, h) -> w * h
```
#### Recursive
Algebraic types can be recursive
``` F#
type ‘a myList =
| Nil (* empty list *)
| App of ‘a * ‘a myList (* cons *)
let rec length =
function
| Nil -> 0
| App (_, lst) -> 1 + length lst
```
### The option type
Options are used to encode partial functions
``` F#
type ‘a option =
| None (* No result *)
| Some of ‘a (* result *)
```
You can think of options as terms that can be set to null (but nice, and type-safe, and do not cause as many bugs)
*Some useful functions*
``` F#
Option.get : ‘a option -> ‘a
Option.map : (‘a -> ‘b) -> ‘a option -> ‘b option
Option.defaultValue : ‘a -> ‘a option -> ‘a
Map.tryFind : ‘a -> Map<‘a,‘b> -> ‘b option
```
### Exression trees
- Expression trees are heavily used by compilers
- Nodes contain operators
- Leaves contain values
Expression trees are really easy to code
``` F#
type term =
| Const of int
| Add of term * term
| Sub of term * term
| Mul of term * term
| Div of term * term
```
***In the example above***
``` F#
Add (Div (Mul (Const 2, Const 3), Sub (Const 2, Const 1)), Mul Const 5, Sub (Const 4, Const 1))
```
... are really easy to recurse over
``` F#
let rec show : term -> string =
function
| Const f -> sprintf “%n” f
| Add (t1, t2) -> “(“ @ show t1 @ “ + “ @ show t2 @ “)”
| Sub (t1, t2) -> “(“ @ show t1 @ “ - “ @ show t2 @ “)”
| Mul (t1, t2) -> “(“ @ show t1 @ “ * “ @ show t2 @ “)”
| Div (t1, t2) -> “(“ @ show t1 @ “ / “ @ show t2 @ “)”
```
***Recall the expression tree from before***
``` F#
let t : term =
Add (Div (Mul (Const 2, Const 3) ,Sub (Const 2, Const 1)) ,Mul (Const 5, Sub (Const 4, Const 1))
> show t;;
val it : string = “(((2 * 3) / (2 - 1)) + (5 * (4 - 1)))“;;
```
### Binary search trees
- All elements in the left subtree are smaller than or equal to the root
- All elements in the right subtree are greater than the root
### Program interpreters
Functional languages are great for working directly on abstract syntax trees
### An imperative language
type aExp = ...
type bExp = ...
Assuming we have types for arithmetic and boolean expression
The abstract syntax tree of our language is defined like this
``` F#
type stm =
| Skip
| Ass of string * aExp
| Seq of stm * stm
| ITE of bExp * stm * stm
| While of bExp * stm
```
### State
In order to keep track of program state we need mapping from program variables to values
``` F#
type state = Map<string, int>
```
#### State (some function)
``` F#
type state = Map<string, int>
let update x v e = Map.add x v e
let s = update “x” 0 Map.empty
Map.find “x” s = 0
Map.find “x” (update “x” 1 s) = 1
```
#### State (some functions)
```F#
type state = Map<string, int>
let unop : (‘a -> ‘b)
-> (state -> ‘a)
-> state -> ‘b
= fun f x -> f (x s)
let binop : (‘a -> ‘b -> ‘c)
-> (state -> ‘a)
-> (state -> ‘b)
-> state -> ‘c
= fun f x y s -> f (x s) (y s)
```
### Arithmetic expressions
``` F#
type aExp =
| N of int
| V of string
| Add of (aExp * aExp)
| Mul of (aExp * aExp)
| Sub of (aExp * aExp)
```
Arithmetic expressions can be evaluated in the context of a state
``` F#
evalA : aExp -> state -> int
let rec evalA =
function
| N n -> fun _ -> n
| V v -> fun s -> Map.find v s
| Add(a, b) -> binop (+) (evalA a) (evalA b)
| Mul(a, b) -> binop (*) (evalA a) (evalA b)
```
### Boolean expression
``` F#
type bExp =
| TT
| FF
| Eq of (aExp * aExp)
| Lt of (aExp * aExp)
| Neg of bExp
| Con of (bExp * bExp)
```
*Boolean expressions can be evaluated in the context of a state*
```F#
evalB: bbExp -> state -> bool
let rec evalB = <Assignment for this week>
```
### Evaluating a program
``` F#
type stm =
| Skip
| Ass of string * aExp // x := e
| Seq of stm * stm // p1;p2
| ITE of bExp * stm * stm
| While of bExp * stm
```
*Programs evaluation is done by updating the state *
```
evalS: stm -> state -> state
let rec evalS = <Assignment for this week>
```
*Here's the fist 3 cases:*
```F#
let rec evalS =
function
| Skip -> fun s -> s
| Ass (var,p) -> fun s ->
let v = evalA p s
update var v s
| Seq (p1,p2) -> evalS p1 >> evalS p2
```
## Lecture 4
### Last week
- Discriminated unions
- Maps
- Sets
- Data representation
### This week
- Modules
- More maps and sets (the assignment)
- Some more programming examples
- Stateful programs - non-functional properties
### This weeks assignment
- Create a multiset
- Create a dictionary (two options, easy and slow, or harder and efficient)
You will be able to port the multiset and the efficient dictionary immediately into your scrabble project
You will get full assignment credit for the slow dictionary, but you will not be able to pass all of the tests, or use it in Scrabble later
Work both in parallel
### Modules
- Modular programming design
- Encapsulation
- Abstraction
- Reuse of components
- A module is characterised by
- A signature (.fsi -file)
- A matching implementation (.fs file)
#### Signatures
Signatures are given in .fsi-files
``` #F
module ModuleName
type T (required type)
val f : <type> (required function)
val g : <type> (required function)
…
…
```
.fsi-files list the types (if any) that must be defined, and the visible functions (if any) that must be implemented
#### Implementations
Implementations are given in .fs-files
``` #F
module ModuleName (same as .fsi)
type T = <def> (must be discrete
union or record)
let f = <implementation>
let g = <implementation>
…
…
```
implementation types must match .fsi types
> [must be discrete
union or record] = Important!
> You will get very weird error messages if you say 'type T = int', for instance
### Rational numbers
Lets write a small library for rational numbers
- Create an .fsi file and define the signatures
- Create an .fs file and write the implementation
#### Title Text
``` #F
module Rational1
type Rat
val mkRat : int -> int -> Rat
val ( + ) : Rat -> Rat -> Rat
val ( - ) : Rat -> Rat -> Rat
val ( * ) : Rat -> Rat -> Rat
val ( / ) : Rat -> Rat -> Rat
module Rational1
type Rat = R of int * int
let mkRat a b = R (a, b)
let ( + ) (R (a, b)) (R (c, d)) = R (a * d + b * c, b * d)
let ( - ) (R (a, b)) (R (c, d)) = R (a * d - b * c, b * d)
let ( * ) (R (a, b)) (R (c, d)) = R (a * c, b * d)
let ( / ) r (R (c, d)) = r * R (d, c)
```
``` #F
open Rational1
printfn "%A" (mkRat 12 2 + mkRat 12 4)
printfn "%A" (mkRat 12 2 - mkRat 12 4)
printfn "%A" (mkRat 12 2 * mkRat 12 4)
printfn "%A" (mkRat 12 2 / mkRat 12 4)
printfn "%A" (5 + 3)
```
> (5 + 3) = Typing error!
##### Problem
We have replaced the definition of +. It
can now only be used for operations on
rational numbers
##### Solutions?
- Replace (+) with something else, like (.+.) (works, but wont scale)
- Override the definition of + (F# is object oriented after all)
``` #F
module Rational2
[<Sealed>]
type Rat =
static member ( + ) :
Rat * Rat -> Rat
static member ( - ) :
Rat * Rat -> Rat
static member ( * ) :
Rat * Rat -> Rat
static member ( / ) :
Rat * Rat -> Rat
val mkRat : int -> int -> Rat
```
> Static member - this smells object oriented, and it is!
``` #F
module Rational2
type Rat =
| R of int * int
static member ( + ) (R (a, b), R (c, d)) = R (a * d + b * c, b * d)
static member ( - ) (R (a1, b1), R (a2, b2)) = R (a * d - b * c, b * d)
static member ( * ) (R (a, b), R (c, d)) = R (a * c, b * d)
static member ( / ) (r, R (c, d)) = r * R (d, c)
let mkRat a b = R (a, b)
```
``` #F
open Rational2
printfn "%A" (mkRat 12 2 + mkRat 12 4)
printfn "%A" (mkRat 12 2 - mkRat 12 4)
printfn "%A" (mkRat 12 2 * mkRat 12 4)
printfn "%A" (mkRat 12 2 / mkRat 12 4)
printfn "%A" (5 + 3)
```
> (5 + 3) = No typing error - overloading works
##### Problem
We do not have uniwue representations of rational numbers
##### Solution
Euclid's algorithm
``` #F
module Rational2
[<Sealed>]
type Rat =
static member ( + ) :
Rat * Rat -> Rat
static member ( - ) :
Rat * Rat -> Rat
static member ( * ) :
Rat * Rat -> Rat
static member ( / ) :
Rat * Rat -> Rat
val mkRat : int -> int -> Rat
```
> Exactly the same as before!
``` #F
module Rational3
type Rat =
| R of int * int
let gcd a b
let rec aux a =
function
| 0 -> a
| b -> aux b (a % b)
aux (max a b) (min a b)
let gcdRat (R (a, b)) =
let c = gcd a b in R (a / c, b / c)
type Rat with
static member ( + ) (R (a, b), R (c, d)) =
R (a * d + b * c, b * d) |> gcdRat
```
> Here we have a type extension
##### Final problem
When we print we expose implementation details (R (a, b) should be internal to the module)
##### Solution
Override the ToString method
``` #F
module Rational4
type Rat =
| R of int * int
override q.ToString() =
match q with
| R (a, b) -> sprintf "(%d / %d)" a b
…
printfn "%A" (mkRat 3 6)
```
> Now outputs "(1 / 2)"
>
> Overriding not possible with type extensions
### Imperative features
- References
- Sequencing
- Mutable data
- Arrays
- Loops
#### Functional values
Functional values never change
``` #F
let x = 15;;
val x : int = 15
let y = fib x;;
val y : int = 987
x;;
val it : int = 15
```
> Calling fib does not change the value of x
#### Mutable Variables
- Mutable variables are defined using the ‘mutable’ keyword
- They are stored on the stack (when possible)
- They behave much more like variables in imperative languages do
- They are mutated using the <- operator
``` #F
let mutable x = 10;;
val mutable x : int = 10
let mutable y = x;;
val mutable y : int = 10
x <- 20;;
val it : unit = ()
x;;
val it : int = 20
y;;
val it : int = 10
```
#### References
References are stored on the heap
> Updating a reference is a side effect. The value of the calculation is () (unit)
>
> This is standard - operations with side effects (writing to files, memory, stdout…) typically return ()
#### Sequencing
Similarly to imperative languages we can
string together expressions with ;
- This expression has the same type as e2
- If e1 has any other type than unit then a warning will be generated
- ; separates expressions, it does not end them
> Sequencing should only be used to string together expressions with side effects and then finally return a value
##### You can do weird stuff
> There are very few places where references are useful (and never do this particular thing)
#### Arrays
- Arrays function as in imperative languages
- Not functional
- They still have many uses for performance reasons
##### Array update
> Note that updating the array is a side effect
##### Array library
Go through the Array library
- Initialisers
- Maps
- Folds
- Iterators
- …
#### While-loops
While loops do exist
While b is true, do e, and throw away the result - only works on side effects
> While expression always has type unit
##### Example
``` #F
let f arr =
let mutable x = 0;
while x < Array.length arr do
arr.[x] <- arr.[x] * 3;
x <- x + 1;;
val f : arr:int [] -> unit
let arr = Array.init 5 (fun x -> x + 7);;
val arr : int [] = [|7; 8; 9; 10; 11|]
f arr;;
val it : unit = ()
arr;;
val it : int [] = [|21; 24; 27; 30; 33|]
```
> This might seem familiar, but do not use loops. We dock points if you do.
``` #F
let arr = Array.init 5 (fun x -> x + 7);;
val arr : int [] = [|7; 8; 9; 10; 11|]
Array.map (( * ) 3) arr;;
val it : int [] = [|21; 24; 27; 30; 33|]
```
- Shorter, cleaner, nicer
- No risk for infinite loops
#### Iterators
Iterators are higher-order functions that use side effects
``` #F
Array.iter;;
val it : (('a -> unit) -> 'a [] -> unit)
Array.iter (printfn "element: %d")
[|7; 8; 9; 10; 11|];;
element: 7
element: 8
element: 9
element: 10
element: 11
val it : unit = ()
```
``` #F
Array.iteri;;
val it : ((int ->’a -> unit) -> 'a [] -> unit)
Array.iteri (printfn “index: %d\t element: %d")
[|7; 8; 9; 10; 11|];;
index: 0 element: 7
index: 1 element: 8
index: 2 element: 9
index: 3 element: 10
index: 4 element: 11
val it : unit = ()
```
#### Dictionary<'a, b'>
Dictionary<'a,'b> is an imperative map type.
``` #F
let dict = Dictionary<char,int>();;
val dict : Dictionary<char,int> = dict []
> dict.['a'] <- 0;;
val it : unit = ()
> dict.['a'];;
val it : int = 0
```
> Note that this is not the "dictionary" you should implement in the assignment. But it can be used to do so.
#### Tries
Tries, or prefix trees, are efficient data structures for dictionaries
- Lookup and insertion is linear with respect to the size of the word
- Consists of a tree with one sub-tree per letter of the alphabet
- Every node and leaf has a boolean flag to tell if a complete word has been found at this point
#### Binary tries
Binary tries can be usd to store integers
- Lookup and insertion is O(log n) where n is the number we are working with
- We go left if the last bit is 0
- We go right if the last bit is 1
- We shift n right when we go down
- We set or check the flag f n is 0
##### n-ary tries
Work the same, but typically use Map or Dictionary in the nodes - one element per letter in the alphabet
- If using Dictionary:
- Be aware that Dictionary are imperative so the trie will be permanently changed by insertion.
## Lecture 5: Efficiency - Iterative functions and optimisations
### Last week
- Models
- .fs-files and .fsi-files
- Imperative features
- loops
- mutable state (references, mutable data)
### This week
- The memory model of F#
- Optimisation
- Tail recursion (iteration, continuations)
- Mutual recursion
### Iterative functions
- Also called tail-recursive functions
- avoid evaluations with huge amounts of pending operations, e.g.
```
(1 + (2 + (3 + ( ... + (x + f n)...))))
```
- avoid spurious uses of the (@)-operator
- iterative functions with accumulators correspond to loops or folds
- **Continuations** generalise the concept and are useful when accumulators are not sufficient
### The Memory model of F#
#### The factorial function
Consider the factorial function:
``` F#
let rec fact =
function
| 0 -> 1
| x -> x * fact (x - 1)
```
Compute factorial 5:
``` F#
fact 5 ⤳
5 * fact 4 ⤳
5 * (4 * fact 3) ⤳
5 * (4 * (3 * fact 2)) ⤳
5 * (4 * (3 * (2 * fact 1))) ⤳
5 * (4 * (3 * (2 * (1 * fact 0)))) ⤳
5 * (4 * (3 * (2 * (1 * 1)))) ⤳
120
```
> This product cannot be evaluated!
> It must be kept in memory until the final iteration of fact has been computed
> For large input values this requires a lot of memory
**Time and memory usage are both proportinal to the input value**
>Is this satisfactory?
#### The memory model of F#
- Primitive values are allocated on the stack
- Composite values are allocated on the heap
``` F#
let xs = [5; 6; 7]
let ys = 3::4::xs
let zs = xs @ ys
let n = 27
```
- The linked list xs is **not copied** when constructing ys
- xs is **only copied** when building xs @ys
#### Stack frames
What happens if this let binding of zs is evaluated?
``` F#
let zs = let xs = [1; 2]
let ys = [3; 4]
xs @ ys
```
Initial stack and heap prior to the evaluation of the right-hand side:
Local declarations are avaluated by pushing a new stack frame onto the stack
The top stack frame is popped when the evaluation of the let-expression is done
#### Stack overflow
- The problems we observed with fact have stemmed from the fact that we have **run out of stack space**
- **Each recursive call adds a new stack frame**, which is only released after the recursive call finished
``` F#
fact 5 ⤳
5 * fact 4 ⤳
… ⤳ … ⤳ … ⤳
5 * (4 * (3 * (2 * (1 * fact 0))))
```
### Recursion on Lists
#### Two more examples
- We have seen poor memory performance of factorial
- You might not use factorial all that often in practice
- But: many other recursive functions have the same problem (and worse!)
- Let’s look at two list functions to illustrate this:
- List append (@)
- List reversal (rev)
### List append
Let’s write our own list append function. (what can possibly go wrong)
``` F#
let rec (@) xs ys =
match xs with
| [] -> ys
| x :: xs -> x :: (xs @ ys)
```
Append...
``` F#
[1; 2; 3] @ [4; 5] ⤳
1 :: ([2; 3] @ [4; 5]) ⤳
1 :: (2 :: ([3] @ [4; 5])) ⤳
1 :: (2 :: (3 :: ([] @ [4; 5]))) ⤳
1 :: (2 :: (3 :: [4; 5])) ⤳
[1; 2; 3; 4; 5]
```
> Time and memory usage are both proportional to the input value.
> Is this satisfactory?
**What about the built-in list append?
(not the one we just made)**
``` F#
> [1; 2; 3] @ [1..1000000];;
val it : int list = [1; 2; 3; 1; 2; 3; 4; 5; …]
> [1..1000000] @ [1; 2; 3];;
val it : int list = [1; 2; 3; 4; 5; 6; 7; …]
```
### List reversal
The naive version of list reversal can be written as follows
``` F#
let rec rev =
function
| [] -> []
| x :: xs -> rev xs @ [x]
```
Try..
``` F#
rev [1; 2; 3; 4] ⤳
(rev [2; 3; 4]) @ [1] ⤳
((rev [3; 4]) @ [2]) @ [1] ⤳
(((rev [4]) @ [3]) @ [2]) @ [1] ⤳
((((rev []) @ [4]) @ [3]) @ [2]) @ [1] ⤳
((([] @ [4]) @ [3]) @ [2]) @ [1] ⤳
[4; 3; 2; 1]
```
> Space complexity = ??? = Linear
> Time complexity = ??? = qudradric
> Worst yet! Is this acceptable?
### Iterative Functions
- **Iterative functions** have all recursive calls as their last operation (**= tail recursion**)
- F# will optimise iterative functions so that they don’t increase the stack
**=> No stack overflows!**
- Use **accumulators** or **continuations** to make recursive functions iterative
### Accumulators
Accumulators store the value that has been computed so far
> Original factorial function
``` F#
let rec fact =
function
| 0 -> 1
| x -> x * fact (x - 1)
```
> Factorial with an accumulator
``` F#
let rec factA acc =
function
| 0 -> acc
| x -> factA (acc * x) (x - 1)
```
Try...
``` F#
factA 1 5 ⤳ factA (1 * 5) (5 - 1) ⤳
factA 5 4 ⤳ factA (5 * 4) (4 - 1) ⤳
factA 20 3 ⤳ factA (20 * 3) (3 - 1) ⤳
factA 60 2 ⤳ factA (60 * 2) (2 - 1) ⤳
factA 120 1 ⤳ factA (120 * 1) (1 - 1) ⤳
factA 120 0 ⤳ 120
```
> Compared to fact, factA rewuires no intermediate values
> ``` F#
> Instead of
> 5 * (4 * (3 * (2 *(1 * 1))))
> we compute
> ((((1 * 5) * 4) * 3) * 2) * 1
> ```
>
> Time: linear
> Space: constant
#### Putting a bow on it
This function exposes implementation
details:
``` F#
factA : int -> int -> int
let rec factA acc =
function
| 0 -> acc
| x -> fact (acc * x) (x - 1)
```
We can avoid this by nesting functions:
``` F#
factA : int -> int
let factA x =
let rec aux acc =
function
| 0 -> acc
| x -> aux (x * acc) (x - 1)
aux 1 x
```
#### List reversal
``` F#
let revA xs =
let rec aux acc =
function
| [] -> acc
| x :: xs -> aux (x :: acc) xs
aux [] xs
```
> Time: linear
> Space: linear
Try...
``` F#
revA [1; 2; 3; 4] ⤳ aux [] [1; 2; 3; 4] ⤳
aux [1] [2; 3; 4] ⤳ aux [2; 1] [3; 4] ⤳
aux [3; 2; 1] [4] ⤳ aux [4; 3; 2; 1] [] ⤳
[4; 3; 2; 1]
```
### Measuring time & memory usage
The **#time** comman enables time and ~~memory~~ measurements in the interactie environment
``` F#
#time
--> Timing now on
> rev [1..20000];;
Real: 00:00:17.506,
CPU:0:00:16.540,
GC gen0: 794, gen1: 0
val it : int list = [20000; 19999; 19998;…]
```
### The garbage collector
* The garbage collector reclaims unused memory
* The heap is divided into generations: gen0, gen1, gen2
* gen0 is the youngest and gen2 is the oldest
* Data typically dies young and the GC is designed to take advantage of that
* The #time command counts the number of GC passes that were performed
### Take-home message
The stack is large, but the heap is larger. Get into a habit of writing iterative functions!
#### Observation
- We can use an accumulator if we can can compute the same result in a different order
- For example, fact 5 computes
```
5 * (4 * (3 * (2 * (1 * 1))))
```
- whereas factA 5 computes
```
((((1 * 5) * 4) * 3) * 2) * 1
```
- Multiplication is associative!
#### Example: rev
- Similarly, rev [1;2;3;4] computes
```
((([] @ [4]) @ [3]) @ [2]) @ [1]
```
- whereas revA [1;2;3;4] computes
```
[4] @ ([3] @ ([2] @ ([1] @ [])))
```
- which is equal to
```
4 :: (3 :: (2 :: (1 :: [])))
```
- @ is associative!
### When accumulators fail
* Accumulators are great when they work
* But they **do not work all of the time**, e.g. when
* we cannot reorder the way a function computes its results (e.g. the foldBack function)
* we have multiple recursive calls that cannot be combined into one (e.g. tree traversal)
#### Append
* An **accumulator will not work** (not directly at least).
* Instead, we use a **continuation** to get tail recursion.
* A continuation is a function that is meant **to be called after** the recursive function is finished
``` F#
let rec append xs ys =
match xs with
| [] -> ys
| x :: xs -> x :: (append xs ys)
```
> (append xs ys) -> not a tail call
* **Idea**: make the recursive call, but remember that x still has to be added afterwards
* **Goal**: write a recursive function appendC that takes an additional argument `c : ‘a list -> ‘a list` such that
* appendC `xs xy c = c (append xs ys)`
``` F#
let rec appendC xs ys c =
match xs with
| [] -> c ys
| x :: xs' -> appendC xs' ys (fun r -> c (x :: r))
```
> fun r -> c (x :: r)) = after the recursion is complete: add x and then apply the continuation
```
let (@) xs ys = appendC xs ys id
```
This definition works if we have the equation
`appendC xs xy c = c (append xs ys)`
Try...
```F#
[1;2] @ [3] ⤳
apC [1;2] [3] id ⤳
apC [2] [3] (fun r -> id (1::r)) ⤳
apC [] [3] (fun r -> (fun r -> id (1::r)) (2::r)) ⤳
(fun r -> (fun r -> id (1::r)) (2::r)) [3] ⤳
(fun r -> id (1::r)) [2;3] ⤳
id [1;2;3] ⤳
[1;2;3]
```
#### Example: Tree traversal
``` F#
type BinTree =
| Leaf
| Node of BinTree * int * BinTree
let rec sum (t : BinTree) : int =
match t with
| Leaf -> 0
| Node (l,n,r) -> sum l + sum r + n
let t = genTree 1000000
printfn "%d" (sum t)
=> Stack overflow
```
> let t -> generates a tree of height 1,000,000
**Lets try with an Accumulator**
``` F#
let rec sumA (t : BinTree) (acc : int) =
match t with
| Leaf -> acc
| Node (l,n,r) ->
sumA r (sumA l (n + acc))
```
> (sumA l (n + acc)) -> not a tail call
*We need a way to say “compute sum of l and afterwards continue
with r” in one recursive call*
**Goal**: write a recursive function
```
sumC : BinTree -> (int -> int) -> int
```
such that
```
sumC t c = c (sum t)
```
```F#
let rec sumC (t : BinTree) (c : int -> int) : int =
match t with
| Leaf -> c 0
| Node (l,n,r) -> sumC l (fun vl -> sumC r (fun vr -> c (vl + vr + n)))
```
Try...
``` F#
sumC (Node (Leaf, 4, Leaf)) id
⤳ sumC Leaf (fun vl -> sumC Leaf
(fun vr -> id (vl + vr + 4)))
⤳ sumC Leaf (fun vr -> id (0 + vr + 4))
⤳ id (0 + 0 + 4) ⤳ 4
```
**Why does this work?**
With **continuation** we can **store computations** to be
executed in the future.
Given a function `f : τ1 -> τ2 `
we write a function `fC : τ1 -> (τ2 -> τ2) -> τ2` so that
`fC v0 c0 ⤳ fC v1 c1 ⤳ … ⤳ fC vn cn ⤳ cn (f vn) `
and `ck (f vk) = f v0` for all k
### Mutual Recursion
Recursive type declaration:
``` F#
type BinTree = Leaf
| Node of BinTree * int * BinTree
```
**Mutual recursive** type declaration:
``` F#
type RoseTree = Leaf
| Node of int * Children
and Children = RoseTree list
```
Two types that a are defined in terms of each other
To traverse mutual recursive types we need **mutually recursive functions**, i.e. functions that call each other:
``` F#
let rec sumRose (t : RoseTree) : int =
match t with
| Leaf -> 0
| Node (n,ts) -> n + sumChildren ts
and sumChildren (ch : Children) : int =
match ch with
| [] -> 0
| (t::ts) -> sumRose t + sumChildren ts
```
Try...
``` F#
sumRose (Node (4, [Leaf;Leaf]))
⤳ 4 + sumChildren [Leaf;Leaf]
⤳ 4 + (sumRose Leaf + sumChildren [Leaf])
⤳ 4 + (0 + (sumRose Leaf + sumChildren []))
⤳ 4 + (0 + (0 + 0)) ⤳ 4
```
Continuations
``` F#
let rec sumRoseC t (c : int -> int) : int =
match t with
| Leaf -> c 0
| Node (n,ts) -> sumChildrenC ts (fun s -> c (s + n))
and sumChC ch (c : int -> int) : int =
match ch with
| [] -> c 0
| (t::ts) -> sumRoseC t
(fun s -> sumChildrenC ts (fun s' -> c (s + s')))
```
Try...
``` F#
sumRoseC (Node (4, [Leaf])) id
⤳ sumChildrenC [Leaf] (fun s -> id (s + 4))
⤳ sumRoseC Leaf (fun s -> sumChildrenC []
(fun s’ -> (fun s -> id (s + 4)) (s + s’))
⤳ sumChC [] (fun s’ -> (fun s -> id (s + 4)) (0 + s’))
⤳ (fun s -> id (s + 4)) (0 + 0) ⤳ id (0 + 4) ⤳ 4
```
**The type of continuations**
``` F#
let rec sumC t (c : int -> ) : =
match t with
| Leaf -> c 0
| Node (l,n,r) -> sumC l (fun vl ->
sumC r (fun vr -> c(vl + vr + n)))
```
If you don’t provide type annotations F# will infer a more general type for the continuations.
```F#
let rec sumC t (c : int -> ) : =
match t with
| Leaf -> c 0
| Node (l,n,r) -> sumC l (fun vl ->
sumC r (fun vr -> c(vl + vr + n)))
```
This general type is beneficial: Forgetting to call the continuation or recursion in a non-tail position will give a type error!
### Polymorphic Continuations
Sometimes this polymorphic type of continuations is necessary for mutual recursion, e.g. for this function:
``` F#
let rec incRose (t : RoseTree) : RoseTree =
match t with
| Leaf -> Leaf
| Node (n, ts) -> Node (n+1,incCh ts)
and incCh (ch : Children) : Children =
match ch with
| [] -> []
| t :: ts -> incRose t :: incCh ts
```
Continuations need to be polymorphic here!
``` F#
let rec incRoseC t (c : RoseTree -> 'a) : 'a =
match t with
| Leaf -> c Leaf
| Node (n, ts) ->
incChC ts (fun r -> c (Node (n+1, r)))
and incChC ch (c : Children -> 'a) : 'a =
match ch with
| [] -> c []
| t :: ts ->
incRoseC t (fun t' ->
incChC ts (fun ts' -> c (t' :: ts')))
```
### Summary
- Recursive functions use the stack to remember where they are in the recursion
- This can lead to a stack overflow
- Solution: transform recursive functions into iterative functions, where recursive calls are always last
- Two approaches: accumulator (does not always work) & continuation (works always)
- This can also lead to algorithmic improvements (e.g. in rev)
## Lecture 6
### This week
- Monads
- in practical terms, not much theory
- “railway-oriented programming”
- Computation expressions
### Railway-Oriented Programming
## Lecture 7
Sign in with Wallet
Connect another wallet