Advanced Programming (in F#)

Lecturers

Juhan Ernits, Hendrik Maarand, Ian Erik Varatalu, Department of Software Science, TalTech

---

Lecture 1 — Introduction

1. Course Overview

This course focuses on functional programming in F#, emphasizing higher-level abstraction, declarative programming, and modern software engineering practices.

Objectives: - Understand functional programming paradigms.
- Apply F# to real-world problems.
- Learn asynchronous and parallel programming in a functional style.
- Explore theoretical and historical foundations of programming languages.

---

2. Course Details

Component	Details
Course Code	ITT8060
Duration	16 weeks
Lectures	Room ICO-221 (recorded)
Labs	Wednesdays 12:00, ICT-401
Online Access	Moodle, Teams
Instructor Contact	juhan.ernits@taltech.ee
Course Site	https://fsharp.pages.taltech.ee

---

3. Assessment Structure

Component	Weight	Description
Coursework	36%	9 assignments (4% each), must be individual. AI tools may be used intelligently.
In-Class Test	4%	Week 9 (Oct 29, 2025) – attendance mandatory.
Exam	60%	Written, ≥50% required to pass. Exam dates: Dec 18, Jan 7, 14, 21.

---

4. Textbooks

• Hansen & Rischel – Functional Programming Using F#
• Petricek & Skeet – Real-World Functional Programming
• Syme – Expert F# 3.0 / 4.0
• Online: fsharp.org/learn

---

5. Why F#?

• Functional-first, .NET-supported language in the ML family.
• Strong typing, immutability, referential transparency.
• Seamless .NET integration.
• Inspired modern language features like async/await.

“Converting synchronous to asynchronous code in F# requires just async { ... } and let! — a concept later adopted by C#.”
— Don Syme, The Early History of F#

---

6. Topics Covered

• Functions & modules (higher-order)
• Pipelines and composition
• Lists, arrays, sequences
• Pattern matching & active patterns
• Type inference & recursion
• Record and discriminated unions
• Option types, units of measure
• Async programming, computation expressions
• Type providers

---

7. Imperative vs Declarative Programming

Imperative Style:
Focuses on how tasks are performed using loops and mutable state.

Declarative Style:
Focuses on what should be computed using composition and expressions.

Products
|> Seq.filter (fun p -> p.UnitPrice > 75.0M)
|> Seq.map (fun p -> sprintf "%s - $%M" p.ProductName p.UnitPrice)

Advantages: - Easier parallelization
- Faster prototyping
- More readable and composable

---

8. Example: Parallel Processing

let updated =
    monsters
    |> Seq.map (fun m -> m.PerformStep())
    |> Seq.filter (fun nm -> nm.IsAlive)
    |> Async.Parallel

Declarative syntax enables effortless concurrency via PLINQ or F#’s Async.Parallel.

---

9. Course Goals

• Teach functional reasoning and structured thinking.
• Identify domains suited for functional programming.
• Demonstrate testing, async, and parallel paradigms.
• Show how business and scientific applications benefit from F#.

---

10. F# in Practice

Example of type providers for structured data:

[<Literal>]
let eventUri = __SOURCE_DIRECTORY__ + "\events24s.json"
type Event = JsonProvider<eventUri>
let event = Event.Load(eventUri)

---

11. Applications and Research

• World’s fastest regex engine RE# developed in F#.
• https://cs.taltech.ee/staff/iavara/regex
• Paper: https://arxiv.org/abs/2407.20479
• Used in AI, finance, compilers, and web apps.

---

12. Historical Background

Lambda Calculus

Origin of functional computation (Church & Kleene, 1930s).
Core principle: functions as first-class citizens, no side effects.

Curry–Howard Isomorphism

Establishes a relationship between logic (proofs) and programs (types).
Key contributors: Curry (1934), Howard (1969).

LISP

First functional-style programming language (McCarthy, 1950s) for AI.

ML and Miranda

Introduced strong typing and function composition in the 1970s.

F# and the ML Family

Derived from SML and OCaml, combining theory and practicality in .NET.

---

13. Key Takeaways

• F# unites mathematical rigor and industrial usability.
• Functional programming enhances clarity, modularity, and concurrency.
• Lambda calculus and type systems form the theoretical foundation.
• F# influences mainstream programming and continues evolving in the AI era.

---

“Functional programming is not just about syntax—it’s a mindset of clarity, safety, and composition.”

---

Lecture 2 — Identifiers, Values, Expressions, Functions, and Types

1. Main Goal

Learn abstraction, not just programming syntax.
Focus on: - Modeling - Design - Programming

Why: To solve complex problems elegantly and understandably.
How: Apply functional programming concepts and theory across paradigms.

---

2. F# Language Capabilities

• First-class functions
• Structured values (lists, trees, tuples, etc.)
• Strong typing and polymorphism
• Type inference
• Imperative and object-oriented features (loops, arrays, I/O)
• High-level declarative modeling (B, Z, VDM, RAISE)

---

3. Getting Started

Functional ingredients: - Interactive environment (fsi) - Values, expressions, types, and patterns - Recursive declarations - Bindings and environments - Type inference

---

4. Interactive Environment Example

2 * 3 + 4;;
val it : int = 10

• val – value keyword
• 10 – computed result
• int – inferred type
• it – name of last computed value
• Binding: it ↦ 10

---

5. Value Declarations

Syntax:

let identifier = expression

Example:

let price = 25 * 5;;
let newPrice = 2 * price;;

Bindings:

price ↦ 125
newPrice ↦ 250
it ↦ false

---

6. Function Declarations

let circleArea r = System.Math.PI * r * r;;
val circleArea : float -> float

Usage:

circleArea 1.0;;
val it : float = 3.141592654

---

7. Anonymous Functions

Example:

fun x ->
    match x with
    | 2 -> 28
    | 4 | 6 | 9 | 11 -> 30
    | _ -> 31

Simplifies repetitive conditionals using pattern matching.

---

8. Recursion

Factorial:

let rec fact n =
    match n with
    | 0 -> 1
    | n -> n * fact(n-1)

fact 3 → 6

---

9. Recursion Example – Power Function

let rec power (x,n) =
    match x,n with
    | _, 0 -> 1.0
    | x, n -> x * power(x,n-1)

power(4.0,2) → 16.0

---

10. If–Then–Else

let rec fact n =
    if n=0 then 1 else n * fact(n-1)

Pattern matching is often clearer than if expressions.

---

11. Booleans

Type: bool
Values: true, false

Operators: - not, &&, || (lazy evaluation) Example:

1 < 2 || 5/0 = 1  // evaluates to true

---

12. Strings

"abc" + "de"           // "abcde"
String.length("abc")   // 3
string(6+18)           // "24"

Operators: concatenation, length, comparison, conversion.

---

13. Types

Every expression has a type e : τ.

Basic types: | Type | Example | |-------|----------| | int | 0, 42 | | float | 0.0, 3.14 | | bool | true, false |

Pairs (tuples):

(e1, e2) : τ1 * τ2

Functions:

f : τ1 -> τ2

Example:

power : float * int -> float

---

14. Type Inference

Example:

let rec power = function
    | (_,0) -> 1.0
    | (x,n) -> x * power(x,n-1)

F# infers:

float * int -> float

---

15. Lists

Lists = sequences of same-type elements.

Examples:

[2;3;6]                 // int list
["a";"b";"c"]           // string list
[sin; cos]              // (float -> float) list
[[]; [1]; [1;2]]        // int list list

List structure: - Head: first element
- Tail: remaining list

---

16. Summary

Concepts introduced: - F# REPL interaction
- Value and function declarations
- Bindings and recursion
- Type inference
- Lists and tuples

This lecture provides a “breadth-first” overview of F# fundamentals — deeper exploration continues in later sessions.

---

Lecture 3 — Lists, Functions, Basic Types and Tuples

1. Overview

Lecture topics: - Lists and their structure - Recursion on lists - Higher-order and curried functions - Basic types, equality, ordering, and polymorphism - Tuples and patterns

Goal: Familiarize with the key functional features of F#.

---

2. Lists

A list is a finite sequence of elements of the same type.

[2;3;6]           // int list
["a";"ab";"abc"]  // string list
[sin;cos]         // (float->float) list
[[];[1];[1;2]]    // int list list

• [] = empty list
• Immutable, homogeneous
• ;; used only in interactive mode (not in .fsx)

---

3. List Constructors

• [] – empty list
• :: – cons operator: x :: xs

Right-associative:

x1 :: x2 :: xs = x1 :: (x2 :: xs)

A non-empty list [x1; x2; ...; xn]: - Head: x1 - Tail: [x2; ...; xn]

---

4. Recursion on Lists

Example – Sum of a list:

let rec suml xs =
    match xs with
    | [] -> 0
    | x::xs' -> x + suml xs'

Evaluation:

suml [1;2]
→ 1 + suml [2]
→ 1 + (2 + suml [])
→ 3

Recursion follows the structure of lists.

---

5. Anonymous Functions

Example:

fun x ->
    match x with
    | 2 -> 28
    | 4 | 6 | 9 | 11 -> 30
    | _ -> 31

Simplified:

function
| 2 -> 28
| 4 | 6 | 9 | 11 -> 30
| _ -> 31

---

6. Currying and Partial Application

Curried functions allow partial application.

fun x y -> x + x*y   // int -> int -> int

Equivalent to:

fun x -> (fun y -> x + x*y)

Example:

let f = it 2
f 3   // 8

Functions are first-class citizens.

---

7. Function Declarations

let addMult x y = x + x*y
let f = addMult 2
f 3   // 8

Equivalent to nested anonymous functions.

---

8. Example – Liquid Weight

let weight ro s = ro * s ** 3.0
let waterWeight = weight 1000.0
waterWeight 2.0   // 8000.0

Partial application for custom constants.

---

9. Pattern Matching in Functions

let rec power = function
| (_,0) -> 1.0
| (x,n) -> x * power(x,n-1)

Alternative:

let rec power(x,n) =
    match n with
    | 0 -> 1.0
    | n' -> x * power(x,n'-1)

---

10. Function Composition

let f y = y+3
let g x = x*x
let h = f << g
h 4   // 19

<< composes functions: (f << g)(x) = f(g(x))

---

11. Basic Types and Comparison

compare 7.4 2.0   // 1
compare "abc" "def"   // -3

Pattern matching with guards:

let ordText x y =
    match compare x y with
    | t when t > 0 -> "greater"
    | 0 -> "equal"
    | _ -> "less"

Polymorphic type:

'a -> 'a -> string when 'a : comparison

---

12. Characters

let isLowerCaseVowel ch =
    System.Char.IsLower ch &&
    (ch='a' || ch='e' || ch='i' || ch='o' || ch='u')

Access character from string:

"abc".[0]   // 'a'

---

13. Overloaded Operators & Type Inference

let square x = x * x           // int -> int
let square (x:float) = x * x   // float -> float

F# infers types from context automatically.

---

14. Tuples

Tuples group heterogeneous data:

(3, false)
(1, 2, ("ab", true))

Comparison component-wise:

(1, 2.0, true) = (2-1, 2.0*1.0, 1<2)  // true

Pattern matching:

let ((x,_),(_,y,_)) = ((1,true),("a","b",false))

---

15. Local Declarations

let g x =
    let a = 6
    let f y = y + a
    x + f x

a and f are visible only within g.

---

16. Declaring Types and Exceptions

Quadratic solver:

type Equation = float * float * float
type Solution = float * float
exception Solve

let solve(a,b,c) =
    if b*b - 4.0*a*c < 0.0 || a = 0.0 then raise Solve
    else ((-b + sqrt(b*b - 4.0*a*c))/(2.0*a),
          (-b - sqrt(b*b - 4.0*a*c))/(2.0*a))

---

17. Rational Numbers Example

type qnum = int * int
exception QDiv

let rec gcd = function
| (0,n) -> n
| (m,n) -> gcd(n % m, m)

let canc(p,q) =
    let sign = if p*q < 0 then -1 else 1
    let ap, aq = abs p, abs q
    let d = gcd(ap,aq)
    (sign * (ap/d), aq/d)

Arithmetic rules:

let (.+.) (a,b) (c,d) = canc(a*d + b*c, b*d)
let (.-.) (a,b) (c,d) = canc(a*d - b*c, b*d)
let (.*.) (a,b) (c,d) = canc(a*c, b*d)
let (./.) (a,b) (c,d) = (a,b) .*. mkQ(d,c)

---

18. Recursion and Pattern Matching Example

let rec unzip = function
| [] -> ([],[])
| (x,y)::rest ->
    let (xs, ys) = unzip rest
    (x::xs, y::ys)

Result:

unzip [(1,"a");(2,"b")] = ([1;2], ["a";"b"])

---

19. Summary

Covered: - Lists, constructors, recursion - Curried and higher-order functions - Type inference, polymorphism - Tuples, patterns, and exceptions - Function composition and local scope

“You are now acquainted with a major part of the F# language.”

---

Lecture 4 — Discriminated Unions, Lists, Higher-Order Functions

Discriminated Unions

type StringsOrInts =
  | Strings of string * string
  | Left of int
  | Right of int

Pattern Matching

let foo soi =
  match soi with
  | Strings (s1, s2) -> s1 = s2
  | Left n when n < 0 -> true
  | Left n -> n % 2 = 0
  | Right _ -> true

Option Types

type 'a option = None | Some of 'a

Example

let rec indexOf el xs =
  match xs with
  | [] -> None
  | x::xs' ->
      if x = el then Some 0
      else match indexOf el xs' with
           | None -> None
           | Some i -> Some (i + 1)

---

Lecture 5 — Sets and Maps as Abstract Data Types

Mathematical Sets

• {1, 3, 5, 7, 9}
• Order and repetition don’t matter.
• Operations:
• Union: A ∪ B
• Intersection: A ∩ B
• Difference: A \ B

F# Examples

let a = set [1;3;5;7;9]
let b = set [5;7;11]
a + b // union
a - b // difference

Abstract Data Types

• A type with a set of operations.
• Implementation details are hidden.

---

Lecture 6 — Recursive Data Types

Binary Trees

type Tree =
  | Lf
  | Br of Tree * int * Tree

Insert Function

let rec insert i tree =
  match tree with
  | Lf -> Br(Lf, i, Lf)
  | Br(t1, j, t2) as tr ->
      match compare i j with
      | 0 -> tr
      | n when n < 0 -> Br(insert i t1, j, t2)
      | _ -> Br(t1, j, insert i t2)

In-order Traversal

let rec inOrder tree =
  match tree with
  | Lf -> []
  | Br(t1, j, t2) -> inOrder t1 @ [j] @ inOrder t2

---

Lecture 8 — Tail Recursion

Motivation

• Avoid growing call stacks.
• Use accumulator parameters to maintain state.

Factorial Examples

let rec fact x =
  match x with
  | 0 -> 1
  | n -> n * fact (n - 1)

let rec factA (x, acc) =
  match x with
  | 0 -> acc
  | n -> factA (n - 1, n * acc)

Tail-Recursive List Reversal

let rec revA (lst, ys) =
  match lst with
  | [] -> ys
  | x::xs -> revA(xs, x::ys)