Chapter 2 Types and Functions

• 2.1 Who Needs Types
• 2.2 Types Are About Composability
• 2.3 What Are Types?
• 2.4 Why Do We Need a Mathematical Model?
• 2.5 Pure and Dirty Functions
• 2.6 Examples of Types
• 2.7 Challenges
  • Challenge 2.1 Higher-order memoize
  • Challenge 2.2 Memoize RNG
  • Challenge 2.3 Memoize RNG with seed
  • Challenge 2.4 Which is pure
  • Challenge 2.5 Bool to Bool
  • Challenge 2.6 Draw category

2.1 Who Needs Types

2.2 Types Are About Composability

2.3 What Are Types?

Here, sets can be finite or infinite.

Ideally we can consider types to be sets and functions to be mathematical functions between sets. But we will encounter the halting problem since there are functions that never terminate. That is why we introduce \(\bot\), which means a non-terminating computation. So a function with the following signature:

fn f(x: bool) -> bool {}

may return true, false, or \(\bot\).

For example, the following program:

fn f(x: bool) -> bool {
    !f(x)
}

fn main() {
    println!("{}", f(true));
}

compiles but never terminate.

Such functions are called partial functions, as opposed to total functions, which return valid results for every possible argument.

2.4 Why Do We Need a Mathematical Model?

An alternative is denotational semantics, which is based on math.

Difficulty: computational effects (e.g., I/O)

Solution: mapping to monads (by Eugenio Moggi)

2.5 Pure and Dirty Functions

2.6 Examples of Types

Empty set: Haskell Void (not C++ void, which is actually unit).

Singleton set: C++ void, Haskell/Rust ().

A function without explicit arguments does not mean it takes nothing. This is best shown in Haskell:

f44 :: () -> Integer 
f44 () = 44

The function f44 above obviously takes (), which is the only element in the singleton unit set.

#![allow(unused)]
fn main() {
fn unit<T>(x: T) {}
}

Two-element set: C++/Rust bool, Haskell Bool. Functions to these two-element sets are called predicates.

2.7 Challenges

Challenge 2.1 Higher-order memoize

use std::collections::HashMap;
use std::hash::Hash;

fn memoize<A, B, F>(f: F) -> impl FnMut(A) -> B
where
    F: Fn(A) -> B,
    A: Eq + Hash + Clone,
    B: Clone,
{
    let mut cache: HashMap<A, B> = HashMap::new();
    move |arg| {
        if let Some(result) = cache.get(&arg) {
            result.clone()
        } else {
            println!("Evaluated!");
            let result = f(arg.clone());
            cache.insert(arg, result.clone());
            result
        }
    }
}

fn main() {
    let mut f = memoize(|n| 2 * n);
    println!("{}", f(20)); // First-time call, evaluated
    println!("{}", f(20)); // Memoization used
}

Challenge 2.2 Memoize RNG

This cannot be reached.

Challenge 2.3 Memoize RNG with seed

extern crate rand;
extern crate rand_chacha;
use rand::prelude::*;
use rand_chacha::ChaCha8Rng;

fn main() {
    let mut memoized_rng = |seed: u64| {
        let mut rng = ChaCha8Rng::seed_from_u64(seed);
        rng.gen::<u64>()
    };
    println!("{}", memoized_rng(0));
    println!("{}", memoized_rng(0));
    println!("{}", memoized_rng(1));
    println!("{}", memoized_rng(1));
}

Challenge 2.4 Which is pure

The factorial function is pure. Other functions have side effects (input, output, global state).

Challenge 2.5 Bool to Bool

#![allow(unused)]
fn main() {
fn id(x: bool) -> bool {
    x
}

fn not(x: bool) -> bool {
    !x
}

fn always_true(x: bool) -> bool {
    true
}

fn always_false(x: bool) -> bool {
    false
}
}

Challenge 2.6 Draw category

flowchart LR
    Void
    Unit
    Unit -->|id| Unit
    Bool
    Bool -->|unit| Unit
    Unit -->|true| Bool
    Unit -->|false| Bool
    Bool -->|id| Bool
    Bool -->|not| Bool
    Bool -->|true| Bool
    Bool -->|false| Bool