Prerequisities

There are no formal requirements. However you are expected to know basic functional programming concepts (evaluation, recursion, abstract data types, pattern matching,
lists (including comprehensions), higher-order functions, . . .). The expected knowledge basically corresponds to the functional programming part of the  IB015 Non-imperative programming course. 

We will use mostly Haskell, but if you know Standard ML, OCaml or F#, you should be fine. To catch up on differences to Haskell, I recommend one of the two Haskell books below.

Exam

The exam will have two parts: midterm test (20% of the total points) and final exam (the remaining 80%). Both are written. The questions will be in English, but you are allowed to answer in Czech if you prefer to. You need >50 % to pass. In case you get C or B, and want a better mark, you can try and take an oral exam.

Midterm test will take part at the time of the lecture sometimes around the half of the semester. I will let you know at least two weeks in advance. 

Sample midterm exam from 2014

FInal exam: Multiple dates in the exam period (normally four), as usual.

You are allowed to complete the course with colloqium (k) or zápočet (z) if you prefer to.

For both midterm and final exams you will be provided with a copy of the Lambda Calculus Cheatsheet

Literature

There is no single book which covers the entire course. For each lecture I'll be giving a list of papers/book chapters which cover the topic. The papers will be mostly research or survey paper freely availble to students of this course. The book chapters will be references to the two books below.

B. O’Sullivan, J. Goerzen and D. Stewart: Real World Haskell

Available for free at http://book.realworldhaskell.org/ I will abbreviate this book as RWH throughout the course.

M. Lipovača: Learn You a Haskell for Great Good!

Also available for free, this time at http://learnyouahaskell.com/ I will abbreviate this book as LYaH throughout the course.

I have not read the following book (yet!), but it has been highly recommended to me. Note this one is not free.

C. Allen, J. Moronuki: Haskell Programming: From First Principles (http://haskellbook.com)

Some of the other books, which may be useful to you, are:

• H. Barendregt: Lambda Calculus : Its Syntax and Semantics
• G. Michaelson: An Introduction to Functional Programming Through Lambda Calculus
• B. Pierce: Types and Programming Languages

For the second half of the course, some useful stuff can be found on Stephen Diehl's excellent page:

• What I Wish I Knew When Learning Haskell

Lecture dates

19. 2. 2018

Reading

On the importance of functional programming and lambda calculus

J. Hughes: Why Functional Programming Matters [PDF]

If you read only one paper, then choose this one. You should be able to answer the question in the title.

H. Barendregt: The impact of the lambda calculus in logic and computer science [JSTOR]

History of lambda-calculus

Cardone, Hindley: History of Lambda-calculus and Combinatory Logic [PDF]

History of functional programming

D. A. Turner: Some History of Functional Programming Languages (2012) [PDF]

A (very) short history of functional languages

P. Hudak: The Conception, Evolution and Applications of Functional Programming Languages (1989) [PDF]

While being a quarter of century old, this is still a very good introduction to functional programming languages.

 

If you are really interested in the history, tou should also go and read the original papers referenced in the lecture. They can be easily found on the internet (often at JSTOR, otherwise use Google Scholar) and make really good reading.

Slides

Lecture dates

19. 2. 2018, 26. 2. 2018, 5. 3. 2018

Reading

There are many different texts on (untyped) lambda calculus you can use. To get you started, here is a selection:

Books

• H. Barendregt: Lambda calculus : its syntax and semantics. Rev. ed. Amsterdam: Elsevier, 1998. xv, 621 s. ISBN 0-444-86748-1
• J. Hindley, P. Seldin: Introduction to combinators and the lambda-calculus. Cambridge: Cambridge University Press, 1986. 359 s. ISBN 0-521-31839-4.
• J. Zlatuška: Lambda-kalkul. Vyd. 1. Brno: Masarykova univerzita, 1993. 264 s. ISBN 80-210-0826-1

The last book is in Czech​. Pierce's book also covers lambda calculus in necessary detail.

Other sources

H. Barendregt: Introduction to lambda calculus [PDF]

Wikipedia entry on Lambda Calculus

Stanford Encyclopedia of Philosophy entry on Lambda Calculus

H. Barendregt: Lambda Calculi with Types [PDF]

Lambda calculus evaluator

Lambda calculus reduction workbench (IT University of Copenhagen)

Slides

Lecture dates

12. 3. 2018

Reading

Books

• [Pierce], chapters 9 and 11

​Other

• H. Barendregt: Lambda Calculi with Types [PDF]
• M. Sagiv: Typed Lambda Calculus [PDF] (lecture notes)
• M. Sagiv: Extensions to Typed Lambda Calculus [PDF] (lecture notes)

Slides

Lecture dates

19. 3. 2018 (parametric polymorphism, system HM, type inference), 26. 3. 2018 (system F and beyond)

Reading

Books

• [Pierce], chapter 23
• H. Barendregt: Lambda Calculi with Types [PDF]

​Other

• L. Damas and R. Milner: Principal type-schemes for functional programs [PDF]
  • ​The original  paper describing the type inference algorithm W
• E. Marquart: Hindley-Milner Type Inference [PDF]
  • Easily accessible write-up on the type inference algorithm, by a student at TUM.
• L. Cardelli, P. Wegner: On Understanding Types, Data Abstraction, and Polymorphism [ACM DL] (accessible from MU)
• Wikipedia page on Hindley-Milner type system

Slides

Lecture dates

26. 3. 2018, 9. 4. 2018

Reading

Primary papers

P. Wadler, S. Blott: How to make ad-hoc polymorphism less ad  hoc. POPL'89. [PS]

The paper which introduced type classes. Still great place to start with type classes. You will recognize some material from the lecture.

M. Jones: Functional Programming with Overloading and  Higher-Order Polymorphism. AFPT Spring School 1995. [PDF]

Sums  up the qualified types and constructor classes. Very accessible.

Additional material

M. Jones: A theory of qualified types. ESOP’92.

The paper which introduced qualified types.

M. Jones: A system of cnstructor classes. FPCA’93.

Constructor classes were introduced here.

M. Jones: Type Classes with Functional Dependencies. ESOP'00.

Introduced the correct way of handling multiparameter type classes.

A History of Haskell: Being Lazy With Class. 2007. (Section 6) [PDF]

J. Peterson and M. Jones: Implementing Type Classes. PLDI'93. [PS]

C. Hall, K. Hammond, S. Peyton Jones, P. Wadler: Type classes in Haskell. ESOP'94. [PS]

Corresponding book chapters

• [RWH] chapter 6 "Using Typeclasses" 
• [LYAH] chapter 3 (section Typeclasses 101), chapter 7 (section Typeclasses 102 and onwards)

Slides

Lecture dates

23. 4. 2018, 30. 4. 2018

Reading

P. Wadler: Monads for functional programming. Marktoberdorf 1992.  [PDF]

Great introduction to monads. The "monad tutorial" part of the lecture was adapted from this paper. Highly recommended, even though it's more than 20 years old.

The Typeclassopedia [haskellwiki]

Read this! Functors, applicative functors and more.

All About Monads [haskellwiki]

D. Piponi: You Could Have Invented Monads! (And Maybe You Already Have.)

Relevant book chapters

(I suggest you start with LYAH).

• [LYAH] chapters "11 Functors, Applicative Functors and Monoids" and "12 A Fistful of Monads" 
• [RWH] chapter "14 Monads"

Lecture dates

7. 5. 2018

Reading

S. Liang, P. Hudak, M. Jones: Monad Transformers and Modular Interpreters. POPL'96. [ACM DL]

The paper which introduced the monad transformers and still a good reading. Focused on the interpreters, though.

M. Grabmüller: Monad Transformers Step by Step. [link]

Probably the best monad transformer tutorial.

D. Piponi: Grok Haskell Monad Transformers. [link]

Relevant book chapters

• [RWH] chapter "18 Monad Transformers"

Lecture dates

14. 5. 2018 

Reading

A. Dergunov: Generalized Algebraic Data Types in Haskell. The Monad Reader, Issue 22. [PDF]

If you want just one reference, this is it.

Haskell/GADT on wikibooks 

A brief introduction to GADTs. Contains significantly less material than the link above.

GHC Users Guide: Chapter 7  GHC Language Features

• 7.4.7. Generalised Algebraic Data Types (GADTs)
• 7.7. Type families
• 7.8. Kind polymorphism and promotion

D. Gratzer: Introduction to Dependent Types: Haskell on Steroids [link]

Additional material

See the references provided in the GHC Users Guide (in the sections linked above).

Lecture dates

NOT COVERED THIS YEAR - WON'T BE EXAMINED !!! 
We only briefly discussed dependent types in the last lecture (14.5.), the materials here are intended only for those who are interested in learning more.

Reading

Programming in IDRIS: A Tutorial [PDF]

Read Section 3. Types and Functions

A. Bove, P. Dybjer: Dependent Types at work. [PDF]

Additional material

Read the materials explaining how to simulate dependent types in Haskell using GADTs, type families etc. in Lecture VIII.

Content not published.

Installing Haskell

There are many ways to install Haskell - both the compiler (GHC) and libraries. I personally use The Haskell Tool Stack. For Linux, I would prefer the newest original packages, rather than use those including in your distribution.  For Windows, The Haskell Tool Stack webpage includes a nice installer.

Which version of  GHC?

In the lectures I use GHC 8.2.2 and Stackage LTS 11.2 packages. If you use the Haskell Tool Stack, this is what you get by default. All code provided is tested to work with this setup. 
For monad and monad transformer code to work correctly you need to install the mtl library.

Where to find information on packages etc.?

Use the search provided by Stackage.

To get the monad transformers source codes to work, you need to install the mtl library.

Which IDE?

It is totally up to you, you should be fine with a plain command line. I personally use Emacs and the Haskell mode. I also find the Interactive Haskell feature quite handy.

Some useful GHCi commands?

Sure, here you go:

:browse[!] [[*] ⟨module⟩]

Displays the identifiers exported by the module ⟨module⟩, which must be either loaded into GHCi or be a member of a package. If ⟨module⟩ is omitted, the most recently-loaded module is used.
 

:info[!] ⟨name⟩

Displays information about the given name(s). For example, if ⟨name⟩ is a class, then the class methods and their types will be printed; if ⟨name⟩ is a type constructor, then its definition will be printed; if ⟨name⟩ is a function, then its type will be printed. If ⟨name⟩ has been loaded from a source file, then GHCi will also display the location of its definition in the source.

:kind[!] ⟨type⟩

Infers and prints the kind of ⟨type⟩

:type ⟨expression⟩

Infers and prints the type of ⟨expression⟩, including explicit forall quantifiers for polymorphic types.

The commands above can be shortened to :bro, :i, :k, and :t respectively.
To print the explicit "forall" quantifiers, use :set -fprint-explicit-foralls
The full documentation can be found here.

Do I need to actually run Haskell to pass the course?

No, you do not. But playing around with Haskell and trying out the concepts covered in the lectures helps a lot.