Chapter 52 — Functions as Programs

# --- Visualization: Pure vs Impure Functions and their mathematical equivalents ---
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')

# Demonstrating that pure functions produce consistent, plottable surfaces
# while impure functions do not.

# Pure function: same x → same y, always
def pure_f(x):
    return np.sin(x) * np.exp(-0.1 * x)

x = np.linspace(0, 10 * np.pi, 500)
y_pure = pure_f(x)

# Impure function: same x → different y (random noise added)
# This is NOT a mathematical function — it is non-deterministic.
def impure_f(x):
    return np.sin(x) * np.exp(-0.1 * x) + np.random.normal(0, 0.3)

# Call impure 3 times at same x — get 3 different "outputs"
y_impure_1 = np.array([impure_f(xi) for xi in x])
y_impure_2 = np.array([impure_f(xi) for xi in x])

fig, axes = plt.subplots(1, 2, figsize=(14, 5))

axes[0].plot(x, y_pure, color='steelblue', linewidth=1.5)
axes[0].set_title('Pure Function: f(x) = sin(x)·e^{-0.1x}\nSame input → always same output')
axes[0].set_xlabel('x')
axes[0].set_ylabel('f(x)')

axes[1].plot(x, y_impure_1, color='crimson', alpha=0.6, linewidth=1, label='Call 1')
axes[1].plot(x, y_impure_2, color='darkorange', alpha=0.6, linewidth=1, label='Call 2')
axes[1].set_title('Impure Function: adds random noise\nSame input → different outputs each call')
axes[1].set_xlabel('x')
axes[1].set_ylabel('f(x)')
axes[1].legend()

plt.tight_layout()
plt.show()

# --- Mathematical Formulation: Higher-order functions as set operations ---
import numpy as np
from functools import reduce

# The input set S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
S = list(range(1, 11))

# map: apply f to every element
# Mathematical: { x² : x ∈ S }
squares = list(map(lambda x: x**2, S))
print("map (x²):", squares)

# filter: keep only elements satisfying a predicate
# Mathematical: { x ∈ S : x is even }
evens = list(filter(lambda x: x % 2 == 0, S))
print("filter (even):", evens)

# reduce: fold an operation over the set
# Mathematical: x1 + x2 + ... + xn = Σ xᵢ
total = reduce(lambda acc, x: acc + x, S, 0)
print("reduce (sum):", total)

# Composing: sum of squares of even numbers
# Mathematical: Σ { x² : x ∈ S, x even }
result = reduce(lambda acc, x: acc + x,
                map(lambda x: x**2,
                    filter(lambda x: x % 2 == 0, S)), 0)
print("Sum of squares of evens:", result)  # 4+16+36+64+100 = 220

# Verify:
print("Verify with numpy:", sum(x**2 for x in range(1,11) if x % 2 == 0))

# --- Implementation: Function utilities — memoization and profiling ---
import numpy as np
import time

def memoize(f):
    """
    Memoize a pure function: cache results so each input is only computed once.
    
    Mathematically valid ONLY for pure functions — since f(x) is always the same,
    we can safely cache it. For impure functions, memoization would give wrong results.
    
    Args:
        f: callable, a pure function
    Returns:
        callable: memoized version of f
    """
    cache = {}
    def memoized(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    memoized.cache = cache  # expose for inspection
    return memoized

# Naive recursive Fibonacci — exponential time
def fib(n):
    """Fibonacci sequence: fib(n) = fib(n-1) + fib(n-2), fib(0)=0, fib(1)=1."""
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# Memoized version — polynomial time
@memoize
def fib_memo(n):
    """Memoized Fibonacci."""
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

# Time comparison
N = 30

t0 = time.time()
result_naive = fib(N)
t_naive = time.time() - t0

t0 = time.time()
result_memo = fib_memo(N)
t_memo = time.time() - t0

print(f"fib({N}) = {result_naive}")
print(f"Naive time:    {t_naive:.4f}s")
print(f"Memoized time: {t_memo:.6f}s")
print(f"Speedup: {t_naive/max(t_memo, 1e-9):.1f}x")

# Memoization is sound BECAUSE fib is a pure function.
# The mathematical property (same input → same output) enables this optimization.

# --- Experiment 1: Function pipeline — composing transformations ---
# Hypothesis: Chaining pure functions produces a predictable composite transformation.
# Try changing: the order of the pipeline steps, or the functions themselves.

import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')

# Build a pipeline of transformations
pipeline = [
    ('shift_right', lambda x: x - 2),       # x → x - 2
    ('square',      lambda x: x**2),          # x → x²
    ('normalize',   lambda x: x / (x.max() + 1e-8)),  # x → x / max(x)
]

x = np.linspace(-5, 5, 300)
stages = [x]
labels = ['Input x']

current = x.copy()
for name, fn in pipeline:
    current = fn(current)
    stages.append(current.copy())
    labels.append(name)

fig, axes = plt.subplots(1, 4, figsize=(16, 4))
for ax, stage, label in zip(axes, stages, labels):
    ax.plot(x, stage, color='steelblue', linewidth=1.5)
    ax.set_title(label)
    ax.set_xlabel('Original x')
    ax.set_ylabel('Value')

plt.suptitle('Function Pipeline: Each step transforms the previous output', fontweight='bold')
plt.tight_layout()
plt.show()

# --- Experiment 2: Purity test ---
# Hypothesis: Adding a global state variable to a function makes it impure.
# Try: run the pure and impure versions multiple times and compare outputs.

# IMPURE version — depends on external state
global_bias = 0.0

def impure_add(x):
    """NOT a mathematical function — reads external state."""
    global global_bias
    global_bias += 0.1  # mutates external state
    return x + global_bias

# PURE version
def pure_add(x, bias):
    """Mathematical function — all inputs explicit."""
    return x + bias

print("Calling impure_add(5) three times:")
print(impure_add(5))  # different each time!
print(impure_add(5))
print(impure_add(5))

print("\nCalling pure_add(5, 0.1) three times:")
print(pure_add(5, 0.1))  # same every time
print(pure_add(5, 0.1))
print(pure_add(5, 0.1))

# Lesson: to make an impure function pure, make all its dependencies explicit arguments.

# --- Mini Project: Functional Data Processing Pipeline ---
# Problem: Process a dataset of temperature readings through a series of
#          pure transformation functions: clean → scale → smooth → analyze.
# Dataset: Simulated hourly temperature data with noise and outliers.
# Task: Build a composable, pure-function pipeline and report key statistics.

import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')

# --- Generate dataset ---
np.random.seed(7)
N_HOURS = 168  # one week
true_temp = 20 + 8 * np.sin(2 * np.pi * np.arange(N_HOURS) / 24)  # daily cycle
noisy_temp = true_temp + np.random.normal(0, 1.5, N_HOURS)
# Add outliers
outlier_idx = np.random.choice(N_HOURS, 10, replace=False)
noisy_temp[outlier_idx] += np.random.choice([-15, 15], 10)

# --- Pure transformation functions ---
def remove_outliers(x, z_threshold=2.5):
    """Replace values > z_threshold std deviations from mean with interpolated values."""
    mean, std = x.mean(), x.std()
    cleaned = x.copy()
    mask = np.abs(x - mean) > z_threshold * std
    # Replace outliers with linear interpolation
    indices = np.arange(len(x))
    cleaned[mask] = np.interp(indices[mask], indices[~mask], x[~mask])
    return cleaned

def celsius_to_fahrenheit(x):
    """Linear scaling: C → F."""
    return x * 9/5 + 32

def moving_average(x, window=5):
    """Smooth with a centered moving average."""
    return np.convolve(x, np.ones(window)/window, mode='same')

# TODO: Build the pipeline and visualize each stage
stages = {
    'Raw (°C)':        noisy_temp,
    'Cleaned (°C)':    remove_outliers(noisy_temp),
    'Fahrenheit':      celsius_to_fahrenheit(remove_outliers(noisy_temp)),
    'Smoothed (°F)':   moving_average(celsius_to_fahrenheit(remove_outliers(noisy_temp)))
}

fig, axes = plt.subplots(2, 2, figsize=(14, 8))
hours = np.arange(N_HOURS)
colors = ['crimson', 'darkorange', 'steelblue', 'darkgreen']

for ax, (label, data), color in zip(axes.flat, stages.items(), colors):
    ax.plot(hours, data, color=color, linewidth=1.2)
    ax.set_title(label)
    ax.set_xlabel('Hour')
    ax.set_ylabel('Temperature')

plt.suptitle('Pure Function Pipeline: Temperature Data Processing', fontsize=13, fontweight='bold')
plt.tight_layout()
plt.show()