Foundations of Computer Science – SML

Deep, Clear Explanations + Interactive Quiz

Introduction to SML & Functional Programming

Introduces the foundations of Standard ML (SML), a functional programming language. Unlike Python or Java, which follow a step‑by‑step sequence of commands, SML focuses on:

1. Expressions

Everything in SML is an expression that produces a value. There are no “do this then that” commands — only expressions that evaluate. 

3 + 4
true andalso false
"Hello" ^ " World"

2. Types

SML is strongly typed and statically typed. This means:

Common types:

3. Functions

Functions are the heart of SML. They take inputs and return outputs — no side effects. 

fun square x = x * x

4. Let Bindings

Let-expressions in Standard ML (SML) create temporary variables inside a block. These variables exist only within the block and disappear afterward. 


let
  val x = 5
in
  x * x
end

Explanation:

  • val x = 5 creates a local binding named x that exists only inside the let ... in ... end block.
  • x * x uses that local binding.
  • The whole expression evaluates to 25.
  • After the end, x disappears — it does not affect anything outside.

Key Concepts

  • Immutability: Once x is bound to 5, it cannot change.
  • Expressions instead of statements: let ... in ... end produces a value.
  • No side effects: Nothing outside the block is modified.

Context

SML does not use statements like Python. Everything is an expression that evaluates to a value. A let-expression is SML’s way of creating local bindings for temporary variables inside a block.

5. Tuples & Lists

Tuples can hold different types. Lists must hold the same type. 

(1, "hi", true)
[1, 2, 3]

6. Basic Pattern Matching

Pattern matching lets you “take apart” data structures and work with their components directly. 


fun head (x::xs) = x

Explanation:

  • The pattern (x::xs) matches any non-empty list by splitting it into two parts:
    • x — the first element (the head)
    • xs — the remaining elements (the tail)
  • When you call head [1,2,3]:
    • x = 1
    • xs = [2,3]
    and the function returns 1.
  • This is a structural match, not a runtime check or loop. It happens as part of the function definition.
  • The list [1,2,3] is shorthand for 1 :: (2 :: (3 :: [])).

Examples:

  • (x :: xs) matches [10,20,30] → x = 10, xs = [20,30]
  • (x :: xs) matches ["a","b"] → x = "a", xs = ["b"]
  • (x :: xs) matches [99] → x = 99, xs = []

Pattern matching only fails on an empty list [], which is why functions often include a second pattern: 


fun head [] = raise Empty
  | head (x::xs) = x

Context

Pattern matching is a core feature of SML’s functional style. It allows you to handle data structures directly in function definitions without loops or conditional statements.

Recursion, Pattern Matching & List Processing

Introducing the most important tools in functional programming:

  • Recursion
  • Pattern matching
  • Higher‑order functions
  • Polymorphism
  • Option types

1. Recursion

Functional languages avoid loops. Instead, they use recursion — a function calling itself. 

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

2. Pattern Matching (Advanced)

Pattern matching is used heavily with lists. It allows you to match different shapes of data and handle each case appropriately. 


fun length [] = 0
  | length (_::xs) = 1 + length xs

Explanation:

  • [] matches the empty list. When the input list has no elements, the length is 0.
  • _ :: xs matches any non-empty list.
    • The underscore _ means “I don’t care about the first element”.
    • xs is the rest of the list (the tail).
    • This case counts 1 for the first element and then recursively computes the length of the tail.
  • Together, these two patterns cover every possible list.

Step-by-step Evaluation


For the list [1,2,3]:

length [1,2,3]
→ 1 + length [2,3]
→ 1 + (1 + length [3])
→ 1 + (1 + (1 + length []))
→ 1 + (1 + (1 + 0))
→ 3

Each step removes one element using the (_ :: xs) pattern until the list becomes empty.

Rules & Analogy

  • 🟦 Rule 1: If the list is empty → length [] = 0
  • 🟧 Rule 2: If the list has a first item and the rest → length (_ :: xs) = 1 + length xs
    • The _ means “I don’t care what the first item is”.
    • This is like counting items in a backpack:
      • If the backpack is empty → 0 items
      • Otherwise → take out one item, count what’s left, and add 1
    • Exactly what the SML function does for lists.

3. Higher‑Order Functions

A higher‑order function is any function that does at least one of the following:

  • Takes another function as an input
  • Returns a function as an output
This section emphasizes functions that take other functions as arguments. map is the classic example.

In short, higher‑order functions are functions that take other functions as inputs. 


map (fn x => x * 2) [1,2,3]

How map works:

  • map has two inputs: a function and a list.
  • The function (fn x => x * 2) is an anonymous function that doubles a number.
  • The list [1,2,3] is the input to process.
  • map applies the function to every element and returns a new list: [2,4,6].

Higher‑Order Functions in Python

Python treats functions as values, so you can pass them into other functions just like numbers or strings. This mirrors the SML concept. 


# Example — A simple higher-order function
def apply_twice(func, value):
    return func(func(value))

def add_one(x):
    return x + 1

print(apply_twice(add_one, 5))  # 7

Why this is higher‑order: apply_twice takes a function (func) as an argument and calls it twice on a value.

Why Higher‑Order Functions Matter

  • Avoid writing repetitive loops
  • Express logic more clearly
  • Build powerful abstractions
  • Write code that mirrors the structure of the data

They come right after recursion and pattern matching in functional programming because they are the next key building block.

Why They Exist

Higher-order functions solve a common problem: you often want to perform the same kind of operation but with different rules. Examples include:

  • “Do something to every item in a list”
  • “Repeat an action many times”
  • “Filter out items based on a rule”
  • “Combine items using some rule”

Instead of rewriting the same loop every time, you write one general function and pass the specific rule into it.

4. Polymorphism

Some functions work on any type. For example, length works on:

  • int list
  • string list
  • bool list

5. Option Type

Option types in SML help prevent errors like “head of empty list” by explicitly representing the possibility of a missing value. 


fun safeHead [] = NONE
  | safeHead (x::xs) = SOME x

Explanation:

  • If the list is empty → return NONE.
  • If the list has a first element → return SOME x.
  • This prevents the classic error “head of empty list.”

Comparison with Python


# Python might crash
[].pop(0)   # IndexError

# Or return None in some cases, but Python doesn't force you to check

SML forces you to handle the possibility of NONE, because the type system requires it. This makes programs safer.

Why the Option Type Matters

Some operations are unsafe because the value you want might not exist. Examples include:

  • Taking the first element of an empty list
  • Looking up a key that isn’t in a dictionary
  • Dividing by zero
  • Searching for something that might not be found

In many languages, these situations cause runtime errors (crashes). SML avoids this by using the Option type:

  • SOME x → a real value exists
  • NONE → no value exists

This forces you to handle the “missing value” case safely, making your code more robust.

Interactive Quiz