What you will learn

• Haskell
• GHCi
• Lambda calculus
• Beta reduction
• Combinators
• Graph reduction
• Pattern matching
• Recursion
• Type classes
• Algebraic data types
• Prolog
• Unification
• Backtracking
• Cut
• Findall
• DCG grammars
• DFS/BFS search

Course content (17 lessons)

1. Course Introduction: Two New Ways of Thinking About Programs — Welcome to Functional & Logic Programming Until now, almost every program you have written has been imperative — a sequence of commands that change variables step by step. This…
2. Unit 1: The Functional Paradigm & Getting Started with Haskell — 1.1 What is functional programming? In a functional language, a program is built entirely from expressions and function definitions . Computation means evaluating an expression to…
3. Unit 1: Basic Types, Definitions & Designing Programs — 2.1 The basic types of Haskell Type Values Example literals :--- :--- :--- Bool truth values True , False Int fixed-size integers (at least 30 bits) 42 , -7 Integer…
4. Unit 1: Tuples, Lists, Input/Output & Control Structures — 3.1 Tuples — fixed-size, mixed-type packages A tuple groups a fixed number of values that may have different types : For pairs, the standard projection functions are fst and snd :…
5. Unit 1: The Lambda Calculus — Syntax, Conversions & Church–Rosser — 4.1 Why the lambda calculus? The lambda calculus (Alonzo Church, 1930s) is the mathematical core of every functional language. It has exactly three kinds of expression, yet it can…
6. Unit 1: How Haskell Runs — Graph Reduction & the Three Instruction Machine — 5.1 From rewriting to running The lambda calculus says programs run by rewriting expressions . But real hardware runs instructions on memory. Graph reduction is the bridge:…
7. Unit 2: Programming with Lists & Building Vocabulary — 1.1 Building vocabulary — the standard list toolkit Fluent Haskell programmers compose programs from a small, powerful vocabulary of list functions. Learn these with their types —…
8. Unit 2: Pattern Matching & Recursion over Lists — 2.1 Pattern matching — branching on the shape of data A pattern appears on the left of a defining equation and does two jobs at once: it tests the shape of the argument and names…
9. Unit 2: Overloading, Type Classes & Type Checking — 3.1 The problem: one symbol, many types == should work on Int , Char , Bool , lists... but not on functions (equality of functions is undecidable). + should work on Int and Double…
10. Unit 2: Algebraic Data Types — 4.1 What "algebraic" means An algebraic data type (ADT) is built from two algebra-like operations: Sum ("or"): a value is one of several alternatives → multiple constructors.…
11. Unit 3: Introduction to Logic Programming & Basic Constructs — 1.1 The logic programming idea A logic program does not describe how to compute. It states facts and rules about a world, and computation happens when you ask a query — the system…
12. Unit 3: Database Programming & Recursive Programming — 2.1 Logic programs as databases A collection of facts is a relational database — predicates are tables, facts are rows: Rules then play the role of SQL queries and views:…
13. Unit 3: The Computation Model, Theory & Applications of Logic Programs — 3.1 The abstract interpreter (SLD resolution) A logic program runs by SLD resolution (Selective Linear Definite-clause resolution). State = the current list of goals (the…
14. Unit 4: Programming in Prolog — Syntax, Arithmetic & Control — 1.1 From theory to tool Unit 3 gave the model; this unit is hands-on Prolog (PROgramming in LOGique, Colmerauer & Roussel, 1972). Install SWI-Prolog (free, all platforms). Save…
15. Unit 4: Structure Inspection & Second-Order Programming — 2.1 Structure inspection — programs that examine terms Prolog terms are data structures you can take apart at runtime. The inspection built-ins: Type tests: Test Succeeds when…
16. Unit 4: Logic Grammars & Search Techniques — 3.1 Logic grammars — parsing by deduction Prolog was born for language processing. A context-free grammar can be written almost verbatim as a DCG (Definite Clause Grammar) using…
17. Lab Practicals: Haskell & Prolog Experiments — How to use this lesson The lab list for this subject has two halves — Haskell (experiments 1–6) and Prolog (experiments 7–10). Each practical below names the theory lesson it…

Course Introduction: Two New Ways of Thinking About Programs

Welcome to Functional & Logic Programming

Until now, almost every program you have written has been imperative — a sequence of commands that change variables step by step. This course introduces two radically different paradigms:

• Functional programming (Haskell): a program is a collection of mathematical functions. There are no assignment statements, no loops, and no changing state — only expressions that are evaluated.
• Logic programming (Prolog): a program is a collection of facts and rules. You don't tell the computer how to compute an answer — you describe what is true, ask a question, and the system searches for the answer itself.

The paradigm map

How this course is organised

Why learn paradigms you may never "use at work"?

1. They change how you think. Recursion, immutability and pattern matching — once they click in Haskell — make you a better Java/Python programmer too.
2. Mainstream languages are absorbing them. Lambdas in Java, list comprehensions in Python, Option/Result types in Rust, LINQ in C# — all came from functional programming.
3. They power real systems. Haskell runs in banking and compilers; Prolog-style logic powers SQL query planners, type checkers, expert systems and parts of AI reasoning.
4. Exams love them. The questions are predictable — evaluate a lambda expression, write a recursive list function, trace a Prolog query — and every one of them is practised in these lessons.

How to study this course

1. Install GHC (Haskell) and SWI-Prolog in week one. Both are free; both run on Windows/Linux/Mac. Every concept sticks 10× better after you type it into the REPL yourself.
2. Evaluate by hand first. Lambda-calculus reductions and Prolog query traces are pen-and-paper skills; the interpreter is only there to confirm your manual answer.
3. Do the lab experiments alongside the theory units — the lab lesson at the end of this course maps each experiment to the unit that explains it.
4. Trace every diagram. The Mermaid diagrams in this course show evaluation orders and search trees step by step — walk through them before moving on.

The three paradigms side by side (a favourite exam comparison)

A 5-mark "compare the programming paradigms" question is answered perfectly by reproducing this table and adding one two-line code sample per paradigm (e.g. factorial as a loop, as a recursive equation, and as a pair of clauses).

How the end-term exam typically samples this course

Two habits pay the most: always show every intermediate step in a trace (markers are awarded per step), and always give the type signature before a Haskell definition — both signal mastery instantly.

Self-check before you begin

1. Can you name two differences between declarative and imperative programming?
2. Which two language families sit under the declarative branch of the paradigm map above?
3. What does each unit of this course cover, in one phrase per unit?
4. Which tools should be installed in week one, and what are their REPL commands called?

Unit 1: The Functional Paradigm & Getting Started with Haskell

1.1 What is functional programming?

In a functional language, a program is built entirely from expressions and function definitions. Computation means evaluating an expression to a value — never executing commands that overwrite memory.

1.2 Key properties of functional languages

• Purity / no side effects. Calling f 5 today, tomorrow, or twice in a row always gives the same answer. This property is called referential transparency — any expression can be replaced by its value without changing the program's meaning.
• First-class functions. Functions are values: they can be passed as arguments, returned as results and stored in lists. A function that takes or returns functions is called a higher-order function.
• Lazy evaluation (Haskell-specific). An expression is evaluated only when its value is actually needed. This allows infinite data structures like [1..] (the list of all positive integers).
• Strong static typing. Every expression has a type known at compile time; type errors are caught before the program runs.

1.3 Getting started with GHC and GHCi

GHC (Glasgow Haskell Compiler) is the standard Haskell compiler. GHCi is its interactive shell (REPL) — you type expressions, it evaluates them.

-- Start the REPL by typing:  ghci
ghci> 2 + 3 * 4
14
ghci> (2 + 3) * 4
20
ghci> not True
False
ghci> "hello " ++ "world"
"hello world"

Useful GHCi commands (all start with a colon):

1.4 Your first script

Save this as First.hs and load it with :l First.hs:

-- First.hs : our first Haskell definitions
square :: Int -> Int          -- type signature: Int to Int
square x = x * x              -- definition: an EQUATION, not a command

areaOfCircle :: Double -> Double
areaOfCircle r = pi * r * r

greet :: String -> String
greet name = "Hello, " ++ name ++ "!"

ghci> square 7
49
ghci> areaOfCircle 2.0
12.566370614359172
ghci> greet "Asha"
"Hello, Asha!"

Notice what is missing: no return, no braces, no semicolons, no parentheses around arguments. square 7 — function application is written by juxtaposition (a space) and binds tighter than any operator, so square 3 + 1 means (square 3) + 1 = 10.

1.5 Function application vs operators

• f x y applies f to two arguments.
• Operators like + are just functions with symbolic names; (+) 2 3 is the same as 2 + 3.
• A two-argument function can be used as an infix operator by wrapping its name in backquotes:

7 `div` 2      -- infix form: exactly the same as  div 7 2  →  3

1.6 The evaluation model: rewriting

Haskell evaluates by rewriting expressions using the defining equations, just like simplifying in algebra:

square (3 + 1)
= square 4            -- arithmetic (or later, if lazy)
= 4 * 4               -- by the equation  square x = x * x
= 16

This "calculation" view is the heart of the whole subject — the lambda-calculus lesson makes it formal, and the graph-reduction lesson shows how the machine actually does it.

1.7 Referential transparency — the exam definition

Definition. An expression is referentially transparent if it can be replaced by its value (or by any other expression equal to it) anywhere in the program without changing the program's meaning. A language is referentially transparent when every expression in it has this property.

Why imperative code breaks it — a side-by-side you can reproduce in the exam:

// C-like, with hidden state:          -- Haskell, pure:
int c = 0;                             f :: Int -> Int
int f(int x) {                         f x = x + 1
    c = c + 1;
    return x + c;                      -- f 5 is ALWAYS 6, so
}                                      -- f 5 + f 5  ==  2 * f 5   ✓ holds
// f(5) + f(5) = 6 + 7 = 13
// 2 * f(5)    = 2 * 6 = 12   → NOT equal! equational reasoning fails

Consequences worth listing in an answer: (1) the compiler may evaluate sub-expressions in any order; (2) repeated expressions can be computed once and shared; (3) expressions can safely run in parallel; (4) programs can be verified by substituting equals for equals, exactly like algebra.

1.8 Eager vs lazy evaluation — first taste

The same expression can be reduced in two different orders. Both reach the same answer here (the Church–Rosser theorem of the lambda-calculus lesson guarantees answers never disagree), but the work done differs:

Applicative order (eager — C, Java, Python):     Normal order + sharing (lazy — Haskell):
square (3 + 1)                                    square (3 + 1)
= square 4          -- argument first             = x * x  where x = (3+1)   -- ONE shared node
= 4 * 4                                           = 4 * 4                     -- forced once
= 16                                              = 16

Where laziness visibly changes behaviour:

ghci> fst (1, undefined)     -- lazy: undefined never touched
1
ghci> take 3 [1..]           -- works on an INFINITE list
[1,2,3]

An eager language would crash on the first and loop forever on the second. Remember the slogan: lazy evaluation computes a value at most once, and only if it is needed.

1.9 Advantages and limitations of functional programming (classic 5-mark question)

Advantages

1. Easier reasoning and testing — referential transparency means a function is fully specified by its input/output table; no hidden state to set up.
2. Conciseness — higher-order functions and recursion replace boilerplate loop code (quicksort in ~3 lines, Unit 2).
3. Fewer bugs by construction — no aliasing, no race conditions on shared mutable state; strong static types catch errors at compile time.
4. Free parallelism opportunities — independent pure expressions can be evaluated concurrently.
5. Mathematical foundation — programs can be proved correct by induction (Unit 2) because programs are equations.

Limitations

1. I/O and state need special machinery (IO actions, Unit 1's data & I/O lesson) — less direct than imperative assignment.
2. Performance can be harder to predict — l

Frequently asked questions

Is the Functional & Logic Programming course really free?

Yes. The entire Functional & Logic Programming course on Siksha Sarovar is free to read with no account required. You can optionally sign in with Google to save your progress.

Do I get a certificate for Functional & Logic Programming?

Yes — finish the lessons and pass the quiz to earn a free, verifiable certificate you can share on LinkedIn or with recruiters.

Can I run code while learning?

Yes. The built-in online compiler runs C, C++, Python, Java, PHP, JavaScript, C# and SQL directly in your browser — no installation needed.