Introduction to
Functional Programming
in Rust
Amit Dev (github.com/amitdev @amitdevr)
What is Functional Programming?
- Values + Pure functions
- Composition
- Reasoning
“A language that doesn't affect the way you think about programming, is not worth knowing”Alan Perlis
Why Rust
“Zero-overhead principle:Bjarne Stroustrup - Foundations of C++
What you don’t use, you don’t pay for, And further: What you do use, you couldn’t hand code any better.”
https://twitter.com/01k/status/1067788059989684224
Key Features
- Strongly Static Typed
- Type Inference
- Based on Linear Types
- Region based memory management
Ownership model
Immutable by default
fn main() {
let x = 3;
x = 5;
}
error[E0384]: cannot assign twice to immutable variable `x`
|
2 | let x = 3;
| -
| |
| first assignment to `x`
| help: make this binding mutable: `mut x`
3 | x = 5;
| ^^^^^ cannot assign twice to immutable variable
error: aborting due to previous error
For more information about this error, try `rustc --explain E0384`.
Move Semantics
fn main() {
let x = String::from("hello");
let y = x;
println!("x={}, y={}", x, y);
}
error[E0382]: borrow of moved value: `x`
|
2 | let x = String::from("hello");
| - move occurs because `x` has type `std::string::String`,
which does not implement the `Copy` trait
3 | let y = x;
| - value moved here
4 | println!("x={}, y={}", x, y);
| ^ value borrowed here after move
error: aborting due to previous error
For more information about this error, try `rustc --explain E0382`.
Clone
fn main() {
let x = String::from("hello");
let y = x.clone();
println!("x={}, y={}", x, y);
}
x=hello, y=helloCopy Trait
fn main() {
let x = 3;
let y = x;
println!("x={}, y={}", x, y);
}
x=3, y=3Mutable + Ownership
fn append_newline(original: String) -> String {
let mut result = original;
result.push_str("\n");
result
}
fn main() {
let x = String::from("Hello");
let y = append_newline(x);
println!("{}", y);
}
Mutable + Ownership
fn append_newline(original: String) -> String {
let mut result = original;
result.push_str("\n");
result
}
fn main() {
let x = String::from("Hello");
let y = append_newline(x);
println!("{}", y);
}
References
fn len(s: String) -> usize {
s.len()
}
fn main() {
let x = String::from("hello");
println!("{}", len(x));
println!("{}", x);
}
References
fn len(s: &String) -> usize {
s.len()
}
fn main() {
let x = String::from("hello");
println!("{}", len(&x));
println!("{}", x);
}
Mutable References
fn len(s: &mut String) -> usize {
s.len()
}
fn main() {
let x = String::from("hello");
println!("{}", len(&mut x));
println!("{}", x);
}
Ownership Overview
- Every value has a single owner, when owner goes out of scope the value is dropped.
- There can be either one mutable reference or any number of immutable references.
- References have lifetimes.
Basic types
| Type | Builtin | Example |
|---|---|---|
| Integer | u8 | u16 | u32 | u64 | u128 |
2 |
i8 | i16 | i32 | i64 | i128 |
-2, 0xff |
|
| Floating Point | f32 | f64 |
1.23 |
| Character | char |
'a','ℤ', '😻' |
| Boolean | bool |
true, false |
Algebraic Data Types
0 values
Rust
enum Void {}
Haskell
data Void1 value
Rust
(g ∘ f): X → Z
(g ∘ f): X → Z
(g ∘ f): X → Z
enum Unit { Unit }or()
Haskell
data Unit = Unitor()
1 + 1
Rust
enum Direction { Up, Down }orbool
Haskell
data Direction = Up | DownorBoolean
1 + A
Rust
enum Option<A> {
Some(A),
None
}
Haskell
data Maybe a = Just a | NothingA + B
Rust
enum Result<A, B> {
Ok(A),
Err(B)
}
Haskell
data Either a b = Left a | Right bA * B
Rust
(A, B)
//or
struct Tuple { a: A, b: B }
Haskell
data (a, b) = (a, b)L = 1 + AL
Rust
enum List<A> {
Nil,
Cons(A, List<A>)
}
Haskell
data List a =
Nil |
Cons a (List a)
error[E0072]: recursive type `List` has infinite size
--> src/main.rs:1:1
|
1 | enum List<A> {
| ^^^^^^^^^^^^ recursive type has infinite size
2 | Nil,
3 | Cons(A, List<A>)
| ------- recursive without indirection
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at
some point to make `List` representable
L = 1 + AL
Rust
enum List<A> {
Nil,
Cons(A, Box<List<A>>)
}
Haskell
data List a =
Nil |
Cons a (List a)Pattern Matching
struct Person {
name: String,
address: Option<String>
}
//...
match person {
Person { name, address : Some(s) }
=> (name, s.len()),
Person { name, address : None}
=> (name, 0)
}
Pattern Matching
fn age_type(age: Option<i32>) -> &'static str {
match age {
Some(val) if val < 0 => "Negative",
Some(val @ 0 ... 18) => "Less than 18",
Some(val) if val > 150 => "Over 150",
Some(val) => "Adult",
None => "Empty"
}
}
Traits
pub trait Clone {
fn clone(&self) -> Self;
}
impl Clone for MyStruct {
fn clone(&self) -> Self {
...
}
}
Traits
pub trait Clone {
fn clone(&self) -> Self;
}
impl Clone for MyStruct {
fn clone(&self) -> Self {
...
}
}
Traits
use std::ops;
#[derive(Debug)]
struct Point(i64, i64);
impl ops::Add<Point> for Point {
type Output = Point;
fn add(self, other: Point) -> Point {
Point(self.0 + other.0, self.1 + other.1)
}
}
fn main() {
println!("{:?}", Point(1, 2) + Point(2, 1)); // Point(3,3)
}
Traits
use std::ops;
#[derive(Debug)]
struct Point(i64, i64);
impl ops::Add<Point> for Point {
type Output = Point;
fn add(self, other: Point) -> Point {
Point(self.0 + other.0, self.1 + other.1)
}
}
fn main() {
println!("{:?}", Point(1, 2) + Point(2, 1)); // Point(3,3)
}
Traits
pub trait TimeDuration {
fn days(&self) -> Duration;
}
impl TimeDuration for i64 {
fn days(&self) -> Duration {
Duration::days(*self)
}
}
date + 3.days();
Traits
pub trait TimeDuration {
fn days(&self) -> Duration;
}
impl TimeDuration for i64 {
fn days(&self) -> Duration {
Duration::days(*self)
}
}
date + 3.days();
Traits
pub trait TimeDuration {
fn days(&self) -> Duration;
}
impl TimeDuration for i64 {
fn days(&self) -> Duration {
Duration::days(*self)
}
}
date + 3.days() // Add 3 days to the given date
Factorial - Take 1
fn factorial(n: u64) -> u64 {
match n {
0 | 1 => 1,
n => n * factorial(n - 1),
}
}
Factorial - Take 1
fn factorial(n: u64) -> u64 {
match n {
0 | 1 => 1,
n => n * factorial(n - 1),
}
}
Closures
let square = |a| a * a;
square(3); // 9
let mul = |a, b| a * b;
mul(2, 3); // 6
let x = 5;
let add5 = |y| x + y;
add5(10); // 15
let side_effecty = || { ... };
Closures
let square = |a| a * a;
square(3); // 9
let mul = |a, b| a * b;
mul(2, 3); // 6
let x = 5;
let add5 = |y| x + y;
add5(10); // 15
let side_effecty = || { ... };
Closures
let square = |a| a * a;
square(3); // 9
let mul = |a, b| a * b;
mul(2, 3); // 6
let x = 5;
let add5 = |y| x + y;
add5(10); // 15
let side_effecty = || { ... };
Closures
let square = |a| a * a;
square(3); // 9
let mul = |a, b| a * b;
mul(2, 3); // 6
let x = 5;
let add5 = |y| x + y;
add5(10); // 15
let side_effecty = || { ... };
Factorial - Take 2
fn factorial(n: u64) -> u64 {
(1..n+1).fold(1, |acc, i| acc * i)
}
use std::ops::Mul;
fn factorial(n: u64) -> u64 {
(1..n+1).fold(1, Mul::mul)
}
Factorial - Take 3
fn factorial(n: u64) -> u64 {
(1..n+1).product()
}
factorial n = product [1..n]
Higher order functions
fn apply<F, A, B>(f: F, arg: A) -> B
where F: Fn(A) -> B {
f(arg)
}
fn square(a: i32) -> i32 { a * a }
// apply can take another function as argument
let n: i32 = apply(square, 4); // n = 16
// apply can also take a closure as argument
let n: i32 = apply(|x| x * x, 4); // n = 16
Higher order functions
fn apply<F, A, B>(f: F, arg: A) -> B
where F: Fn(A) -> B {
f(arg)
}
fn square(a: i32) -> i32 { a * a }
// apply can take another function as argument
let n: i32 = apply(square, 4); // n = 16
// apply can also take a closure as argument
let n: i32 = apply(|x| x * x, 4); // n = 16
Fn Trait Family
- FnOnce
Can be called only once. Closure takes ownership of captured variables - FnMut
Mutable borrows values and can change the environment - Fn
Immutably borrows values from the environment
Compose
f: X → Y, g: Y → Z(g ∘ f): X → Z
fn compose<X, Y, Z, F, G>(f: F, g: G) -> Fn(X) -> Z
where F: Fn(X) -> Y, G: Fn(Y) -> Z {
|x| g(f(x))
}
|
1 | fn compose<X, Y, Z, F, G>(f: F, g: G) -> Fn(X) -> Z
| ^^^^^^^^^^
| doesn't have a size known at compile-time
Compose
f: X → Y, g: Y → Z(g ∘ f): X → Z
fn compose<X, Y, Z, F, G>(f: F, g: G) -> impl Fn(X) -> Y
where F: Fn(X) -> Y, G: Fn(Y) -> Z {
|x| g(f(x))
}
error[E0373]: closure may outlive the current function, but it
borrows `g`, which is owned by the current function
|
3 | |x| g(f(x))
| ^^^ - `g` is borrowed here
| |
| may outlive borrowed value `g`
|
note: closure is returned here
Compose
f: X → Y, g: Y → Z(g ∘ f): X → Z
fn compose<X, Y, Z, F, G>(f: F, g: G) -> impl Fn(X) -> Y
where F: Fn(X) -> Y, G: Fn(Y) -> Z {
move |x| g(f(x))
}
Iterator
data.lines()
.filter(|line| line.contains(query))
.map(str::to_lowercase)
.take(2)
.collect()
}
Quick Sort
fn qsort<T>(lst: Vec<T>) -> Vec<T>
where T: PartialOrd {
if lst.len() == 0 {
return lst;
}
let pivot = lst[0];
let (lo, hi) = partition(lst, pivot);
let (left, right) = (qsort(lo), qsort(hi));
appended(left, pivot, right)
}
Parallel Quick Sort
fn qsort<T>(lst: Vec<T>) -> Vec<T>
where T: PartialOrd + Send {
if lst.len() == 0 {
return lst;
}
let pivot = lst[0];
let (lo, hi) = partition(lst, pivot);
let (left, right) = rayon::join(|| qsort(lo), || qsort(hi));
appended(left, pivot, right)
}
Is Rust a good functional programming language?
| Safe/Total functions | ✓ |
| Algebraic data types | ✓ |
| Immutability/Values | ✓ |
| Higher order functions | − |
| Advanced functional abstractions | − |
| Pure functions | ✕ |
Should I use Rust?
Domain
“We shape our tools and afterwards our tools shape us”- Marshall McLuhan