rust types for functional programming

The Rust typing system is a functional language! It was only after stumbling across this by myself for the first time that I realized it’s actually a wide-spread topic of discussion. I still find it very cool and this serves as personal notes for how it works.

objects

struct Cons {
    val: i32,
    next: Option<Box<Cons>>
}

can be written as the following. Note that we do need a PhantomData placeholder to keep the compiler happy.

struct Cons<Val, Next>(PhantomData<(Val, Next)>);

numbers

Use Peano numbers!

struct Zero;
struct Succ<N>(PhantomData<N>);

Then we can write

type One = Succ<Zero>;
type Two = Succ<One>;
// etc.

And equivalently in Rust for future reference is:

enum PeanoNumber {
    Zero,
    Succ(Box<PeanoNumber>)
}

functions

enum PeanoNumber {
    Zero,
    Succ(Box<PeanoNumber>)
}
fn sub_one(x: PeanoNumber) -> PeanoNumber {
    match x {
        PeanoNumber::Zero => PeanoNumber::Zero,
        PeanoNumber::Succ(y) => 
    }
}

can be written as

struct Zero;
struct Succ<N>(PhantomData<N>);

trait AddOne {
    type Output;
}
impl AddOne for N {
    type Output = Succ<N>;
}

fibonacci

Putting it all together we get:

#![allow(dead_code)]
use std::marker::PhantomData;

// we can technically use a trait Nat to "group" Zero and Succ
struct Zero;
struct Succ<N>(PhantomData<N>);

trait Add {
    type Output;
}

impl<N> Add for (N, Zero) {
    type Output = N;
}

impl<N, M> Add for (N, Succ<M>)
where
    (Succ<N>, M): Add,
{
    type Output = <(Succ<N>, M) as Add>::Output;
}

type One = Succ<Zero>;

trait Fibonacci {
    type Output;
}

impl Fibonacci for Zero {
    type Output = Zero;
}

impl Fibonacci for One {
    type Output = One;
}

impl<N> Fibonacci for Succ<Succ<N>>
where
    N: Fibonacci,
    Succ<N>: Fibonacci,
    (<Succ<N> as Fibonacci>::Output, <N as Fibonacci>::Output): Add,
{
    type Output = <
        (
            <Succ<N> as Fibonacci>::Output, 
            <N as Fibonacci>::Output
        ) as Add
    >::Output;
}

trait Print {
    const OUTPUT: u32;
}

impl Print for Zero {
    const OUTPUT: u32 = 0;
}

impl<N: Print> Print for Succ<N> {
    const OUTPUT: u32 = <N as Print>::OUTPUT + 1;
}

fn main() {
    type Two = <(One, One) as Add>::Output;
    type Four = <(Two, Two) as Add>::Output;
    type Eight = <(Four, Four) as Add>::Output;

    type Ans = <Eight as Fibonacci>::Output;
    println!("{}", <Ans as Print>::OUTPUT); // 21
}