History & Functional Programming Primer

Notes:

1. Overview of Programming Language Evolution

Originated when computers were programmed directly with machine or assembly instructions. Fortran (1957) was one of the first higher-level attempts: let scientists describe calculations without flipping switches.
C (1972) gave more control, letting programmers manage memory and write code that could run on many different machines.
Analogy: imperative code is like giving someone step-by-step cooking instructions: 'chop onions, then sauté, then stir for 5 minutes.'
Strengths: simple to understand, efficient, close to the hardware.
Weaknesses: code bases become hard to manage as they grow, because every variable can change at any time.
- Debugging and maintenance challenges
- Example:
  - The first item you need 1 cup
  - The next item 1 teaspoon
  - But if you want to add something at the beginning it will mess up the order for the quantities

Inspired by lambda calculus (Alonzo Church, 1930s) — a mathematical model of computation.
Lisp (1958) pioneered functional ideas: recursion, lists as a data structure, automatic memory management.
- Everything is a list in Lisp
- Evolved to Scheme
Instead of telling the machine how to compute, you describe what the result should be.
- Focus on 'what' to compute, not 'how'
- In functional programming you may have a list and you map what you want to do to each item
Example: sum of array - imperative vs. functional

Example comparison:
Imperative (C):

total = 0; for(i = 0; i < n; i++) total += arr[i];

Functional (Haskell):

total = sum arr

Why Functional Programming?

Emerged in the 1980s with Smalltalk, then C++ and Java.
Key insight: organize code into objects that bundle data (fields) and behavior (methods).
Makes large systems easier to design by modeling real-world entities: e.g., a BankAccount object that 'knows' how to deposit and withdraw.
Strengths: modularity, reusability, and a natural way to think about systems.

Today’s popular languages combine these traditions. Python supports imperative loops, OOP classes, and functional constructs like lambdas. JavaScript started imperative but now has classes and functional methods (map, reduce).
The point: learning paradigms isn’t just about languages — it’s about gaining mental flexibility.
- Paradigms = mental toolkits

A pure function always returns the same output for the same input, with no hidden state changes.
Examples: Pure: f(x) = x * 2. Impure: print(x) or timeNow().
Why it matters:
- Pure functions are easy to test (just give them input).
- They’re predictable — no surprises from outside changes.
- They enable referential transparency: you can replace a function call with its result anywhere in the program.

In FP, data structures don’t change once created.
Example: instead of updating a list, you create a new list with the change.
Benefits:
- No 'who modified this variable?' bugs.
- Easier debugging, because values don’t mysteriously change.
- Concurrency is safer: if nothing changes, multiple threads can safely use the same data.
Persistent data structures reuse most of the existing structure behind the scenes to stay efficient (reuse memory).

fact 0 = 1
fact n = n * fact (n-1)

This definition mirrors the mathematical definition.
Recursion + immutability go hand in hand: instead of incrementing variables, you break problems into smaller parts.

In functional languages, functions are values. You can pass them around like numbers or strings.
Examples:
- map (*2) [1,2,3] --> [2,4,6]
  - Does not change the size of the set
- filter even [1..10] --> [2,4,6,8,10]
  - The size of the result can be any from 0 to the whole set
    - "Filter out everybody older than 120"
      - Same set size as it is right now
    - "Filter everybody over 4"
      - Result would probably be zero
- foldr (+) 0 [1..5] --> 15
  - Take a list, do something with it, and get a number back
  - Gives you one thing.
These build on purity, immutability, and recursion to create concise, powerful code.

Haskell Enforces Purity:

In mixed-paradigm languages, students can revert to imperative habits.
In Haskell, purity and immutability are enforced by the language itself. This forces a deeper understanding.

Strong Type System:

Types are not just about safety; they shape how you think.
- Types as documentation + contracts
In Haskell, the compiler tells you when something doesn’t match your intent.
- Compiler catches mismatches early
- If it compiles, it likely works correctly

Example:

add :: Int -> Int -> Int
add x y = x + y

Different by Design:

No loops, minimal syntax, recursion everywhere.
Whitespace significant
Example: list comprehensions
Forces new problem-solving habits
At first, it feels strange. But that’s the point: it forces students to think differently.

Contrast with Everyday Languages:

In Java: build classes, mutate fields.
In Python: write loops, increment counters, variable updates.
In Haskell: compose functions, use recursion, trust types, immutability, higher-order functions.
By working in Haskell first, students expand their problem-solving repertoire before moving to OOP in Java.
- Shifts mindset for better abstraction

The Payoff:

After struggling through functional programming, you return to Java with new clarity.
You’ll recognize where immutability helps, or how recursion maps to iteration.
You’ll be better at debugging, better at reasoning about code, and more flexible across languages.