Functional Programming

Recipe	Crates	Categories
Compose Iterators
Use a general purpose sum type with either
Use Functional Programming Data Structures and Type-level Programming Tools with frunk
Create Immutable Data Structures with im

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

Rust is not a purely functional language, but incorporates many features from functional programming. By default, variables in Rust are immutable. Rust treats functions as first-class citizens, meaning they can be passed as arguments to other functions, returned from functions, and assigned to variables. Closures, which are anonymous functions that can capture their environment, are also a powerful tool for functional programming in Rust. Other functional features include pattern matching, algebraic data types, and higher-order functions, such as map, filter, and fold.

The following explores some notable Rust crates that aid in functional programming:

• itertools⮳ is often used with iterator chains, enhancing the standard iterator functions.
• im⮳ replaces standard collections when immutability is required.
• frunk⮳ is used for complex functional programming needs, especially those involving type-level programming.

Compose Iterators

itertools⮳ includes extra iterator adapters, functions and macros.

It offers a wide range of functions for combining, grouping, and manipulating iterators, for example itertools::zip_longest, itertools::group_by.

fn main() {
    use itertools::Itertools;
    use itertools::assert_equal;
    use itertools::chain;

    // Assert that two iterables produce equal sequences
    assert_equal("hello world".split(' '), "hello world".split(' '));

    // Chain
    let mut result: Vec<i32> = Vec::new();

    for element in chain(&[1, 2, 3], &[4]) {
        result.push(*element);
    }
    assert_eq!(result, vec![1, 2, 3, 4]);

    // Cloned
    assert_eq!(itertools::cloned(b"abc").next(), Some(b'a'));

    // Deduplicate
    let data = vec![1., 1., 2., 3., 3., 2., 2.];
    itertools::assert_equal(data.into_iter().dedup(), vec![1., 2., 3., 2.]);

    // `into_group_map`
    let data = vec![(0, 10), (2, 12), (3, 13), (0, 20), (3, 33), (2, 42)];
    let lookup = data.into_iter().into_group_map();

    assert_eq!(lookup[&0], vec![10, 20]);
    assert_eq!(lookup.get(&1), None);
    assert_eq!(lookup[&2], vec![12, 42]);
    assert_eq!(lookup[&3], vec![13, 33])
}

Create Immutable Data Structures with im

im⮳ provides immutable data structures, such as lists, maps, and sets. It facilitates functional programming by providing data structures that cannot be modified in place. Use it when you need to ensure that data does not change in unexpected ways.

use im::HashMap;
use im::HashSet;
use im::Vector;
use im::hashmap;
use im::vector;

// `im` provides a safe default choice for the most common kinds of data
// structures, allowing you to defer careful thinking about the right data
// structure for the job until you need to start looking for optimisations.

// The most obvious benefit of _immutable data structures_ - avoiding the
// accidental mutation of data - is already handled so well by Rust’s type
// system that it’s just not something a Rust programmer needs to worry about.
// Their most prominent advantage in Rust is therefore _structural sharing_. If
// two data structures are mostly copies of each other, most of the memory they
// take up will be shared between them. Therefore, making copies of an immutable
// data structure is cheap. `im` is thus often the right choice for larger data
// sets modified infrequently.

// Because `im` makes copies of shared nodes in its data structures before
// updating them, the values you store must implement `Clone`. If you want to
// store values for which cloning is expensive, or values that don’t implement
// `Clone`, you need to wrap them in `Rc` or `Arc`.

fn main() {
    // Immutable Vector (based on RRB trees),
    // i.e. a sequence of elements in insertion order.
    // Practically every operation is O(log n), except push/pop on both sides,
    // which will be O(1) amortized, and O(log n) in the worst case.

    let mut v1 = Vector::new();
    // Push values to the back of a vector.
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);

    // Clone the Vector and modify.
    // `im` uses _lazy cloning_. The initial `clone` is instant, and as you
    // modify the cloned data structure, it will clone chunks only where you
    // change them, so that if you change the entire thing you will
    // eventually have performed a full clone.
    let mut v2 = v1.clone();
    v2.push_back(4);

    println!("Original vector: {:?}", v1);
    println!("Modified vector: {:?}", v2);

    // Create a new vector with the value at index index updated.
    let v3 = v2.update(1, 10);
    println!("Updated vector: {:?}", v3);

    // Simpler: use the `vector!` macro.
    assert_eq!(5, vector![1, 2, 3, 4, 5].len());

    // The `im` maps - HashMap and OrdMap - generally perform similarly to their
    // equivalents in the standard library, but tend to run a bit slower on the
    // basic operations. On the other hand, they offer the cheap copy and
    // structural sharing between copies that you’d expect from immutable
    // data structures.

    // Let's explore the Immutable HashMap (based on hash array mapped tries).
    // Most operations on this map are O(logx n) for a suitably high x that it
    // should be nearly O(1) for most maps. Keys will need to implement
    // `Hash` and `Eq`.
    assert_eq!(
        3,
        hashmap! {
        1 => 11,
        2 => 22,
        3 => 33
        }
        .len()
    );

    // Or construct a hash map with a single mapping.
    let map0 = HashMap::unit("key0", 0);
    assert_eq!(map0.get("key0"), Some(&0));

    // Or use `insert`:
    let mut map1 = HashMap::new();
    map1.insert("key1", 100);
    map1.insert("key2", 200);

    // Clone the map and modify.
    let mut map2 = map1.clone();
    map2.insert("key3", 300);

    println!("Original map: {:?}", map1);
    println!("Modified map: {:?}", map2);

    // Immutable HashSet
    let mut set1 = HashSet::new();
    set1.insert(1);
    set1.insert(2);

    // Create a new set with a modification.
    let mut set2 = set1.clone();
    set2.insert(3);

    println!("Original set: {:?}", set1);
    println!("Modified set: {:?}", set2);
}

Use a general purpose sum type with either

The enum Either⮳ with variants Left and Right is a general purpose sum type with two cases. This is useful for representing values that can take on one of two different forms, which is a common pattern in functional programming. Either⮳ has methods that are similar to Option and Result, and it also implements traits like Iterator. This crate also includes macros try_left!() and try_right!() to use for short-circuiting logic, similar to how the ? operator is used with Result.

Note that Either⮳ is general purpose. For describing success or error, use the regular Result enum.

// COMING SOON

Use Functional Programming Data Structures and Type-level Programming Tools with frunk

Frunk is a functional programming toolbelt for Rust. It provides developers with a number of functional programming data structures and type-level programming tools like HList (heterogeneous lists), Coproduct, Generic, LabelledGeneric, Validated, Monoid, Semigroup and friends. It is useful for complex data transformations and metaprogramming.

// // COMING SOON