Expressions and Reduction

Expressions vs. Statements

In functional programming, computation is expressed through expressions rather than statements, which is a fundamental difference from imperative languages.

See also: Functions and Equations, Evaluation Strategies, Equational Reasoning, Polymorphism

Imperative Languages	Functional Languages
Use statements: instructions that are executed sequentially	Everything is an expression that reduces to a value
Modify program state and control flow	Don’t modify state; expressions are evaluated
Example: x = x + 1; (modifies x)	Example: let x' = x + 1 in ... (creates new value)

Key Points

• In Haskell, everything is an expression
• All expressions eventually reduce to values
• Even control structures (like if-then-else) are expressions that return values

See: Pattern Matching and Recursion, Lists and List Comprehensions

Examples

Conditional as expression:

if 2 < 3 then
  "two is less than three"
else
  "three is less than two"

Let expressions:

let msg =
  if 2 < 3 then
    "two is less than three"
  else
    "three is less than two"
in
  "Result: " ++ msg

Reduction

Reduction is the process of evaluating an expression to produce a value.

Church-Rosser Property

Functional reduction satisfies the Church-Rosser property:

• Regardless of the order in which subexpressions are evaluated
• The final result will always be the same (if evaluation terminates)

This property is central to functional programming and enables:

• Equational Reasoning
• Referential transparency
• Functional parallelism

Example of Reduction

1 + (2 + (3 + 4))
→ 1 + (2 + 7)
→ 1 + 9
→ 10

Different reduction paths lead to the same result:

(10 * 4) + (5 * 3)
↙         ↘
40 + (5 * 3)    (10 * 4) + 15
↘         ↙
      55

Types

In Haskell, every expression has a type that classifies values:

See: Polymorphism, Algebraic Data Types

5 :: Int
True :: Bool
(1, "Hello") :: (Int, String)

Types help prevent nonsensical expressions (e.g., 5 + True would be a type error).

Type Inference

Haskell infers types automatically, but it’s good practice to add type signatures for top-level functions:

addOne :: Int -> Int
addOne x = x + 1

Summary

• Statements are instructions in imperative languages; expressions reduce to values in functional languages
• Reduction is the process of evaluating expressions to values
• The Church-Rosser property ensures consistent results regardless of evaluation order
• Every expression in Haskell has a type