(TDA 452/DIT 142)

- Study Period 2
- Course homepage. Shortcut: bit.ly/tda452-home
- Lecturer: Thomas Hallgren
- These slides: bit.ly/2otsGS5

- It will make you think differently about programming.
- Mainstream programming is all about
*state*and how to*transform*state. - Functional programming is all about
*values*and how to construct values using*functions*.

- Mainstream programming is all about
- It will make you a better programmer
- whatever programmer language you use in the future.

- Programmer productivity
- Software quality
- Security

- 1930s: Lambda Calculus (Alonzo Church)
- 1966: ISWIM (Peter Landin: The next 700 programming languages)
- 1970s: ML, Hope, SASL, ...
- 1977: FP (John Backus: Can programming be liberated from the von-Neumann Style?)
- Turing award lecture

- 1980s: FPCA (a conference), Standard ML, Lazy ML, Miranda, ...
- 1990: Haskell 1.0
- 1990s: HBC (The first Haskell compiler, from Chalmers), GHC, ICFP (a conference)
- 2010: Haskell 2010

- von Neumann style, word-at-a-time programming:
scalarProduct(a,b,n) { s=0;
**for**(i=0;i<n;i++) s=s+a[i]*b[i];**return**s; } - Whole-value programming:
`scalarProduct`**=**`sum``.``map`(×) . zip- Leaves room for parallel implementations

- The language used in this course.
- Home page: www.haskell.org.
- The most widely used
*pure*functional language- Functions have no side effects
- Good for modularity, helps testing and debugging

- Provides the most "uncompromising" approach to functional programming

- Light-weight, concise syntax
- Easy-to-use lists and user-defined data types
- with pattern matching & automatic memory management

- Powerful type system
- Parametric polymorphism
- Automatic type inference

- Higher order functions
- An advanced optimising compiler (GHC)
- An interpreter for interactive testing during development

- These slides: formatting and syntax high-lighting.
- Fudgets: GUI library in Haskell (early 1990s)
- WebFudgets (2017)
- Alfa: GUI for the proof assisant Agda (mid 1990s)
- A web browser in Haskell (mid 1990s)
- Programatica project: Haskell compiler front-end (2001-2006)
- House: a prototype operating system in Haskell (2004-2006)
- Hardware emulation (6502, 8-bit processor, used in C-64)
- An e-commerce system in Haskell (2006-2009)

- Efficient divide-and-conquer sorting algorithm, invented by Tony Hoare in 1959
- O(
`n`log`n`)- Best known before this: O(
`n`^{2})

- Best known before this: O(

- Sorting an array (from Wikipedia)
- quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) partition(A, lo, hi) is pivot := A[hi] i := lo - 1 for j := lo to hi - 1 do if A[j] ≤ pivot then i := i + 1 swap A[i] with A[j] swap A[i+1] with A[hi] return i + 1

- Sorting the elements of a list
`quickSort`[]**=**[]`quickSort`(`x1`**:**`xs`)**=**`quickSort`[`x`**|**`x`**<-**`xs`,`x``<=``x1`]`++`[`x1`]`++``quickSort`[`x`**|**`x`**<-**`xs`,`x``>``x1`]

`quickSort`**::****Ord**`a`**=>**[`a`]**->**[`a`]- The compiler automatically infers this generic type
- The argument is a list with elements of an arbitrary type
- The result is a list with elements of the
*same*type - It must be possible to compare the elements with the and
`<=`operators`>`

`sortBy`**::**(`a`**->**`a`**->****Ordering**)**->**[`a`]**->**[`a`]- A generic, higher order function
- The first argument is a function for comparing the elements of the list
- The second argument is the list to be sorted

- void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
`void *`

means "a pointer to anything".- Example of an unsafe API.
- The never-ending stream of critical security vulnerabilities in software like Firefox can be directly blamed on the use of unsafe languages like C...

- Lectures
- Self-study exercises & drop-in office hours
- Weekly assignments:
- 1: a small warmup exercise to get started with Haskell
- 2A & 2B: A Card Game
- 3A & 3B: Sudoku solver
- 4: you choose!
- Standard lab: a graph drawing calculator (a web application).

- Written exam