Functional Programming
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.
//! This example demonstrates the usage of the `itertools` crate. //! //! `itertools` provides extra iterator adaptors, functions and macros that //! expand the `Iterator` trait. //! //! Add to your `Cargo.toml`: //! ```toml //! itertools = "0.14.0" //! ``` use itertools::Itertools; use itertools::assert_equal; use itertools::chain; fn main() { // `assert_equal`: // This function asserts that two iterables produce equal sequences. assert_equal("hello world".split(' '), "hello world".split(' ')); // `chain` takes two iterables and creates a new iterator over both in // sequence. let mut result: Vec<i32> = Vec::new(); for element in chain(&[1, 2, 3], &[4]) { result.push(*element); } println!("Result: {:?}", result); assert_eq!(result, vec![1, 2, 3, 4]); // `cloned` creates an iterator that clones the elements of the original // iterator. Here, it's used to clone the bytes of the byte string // "abc" and check if the first element is 'a'. assert_eq!(itertools::cloned(b"abc").next(), Some(b'a')); // `dedup` removes consecutive duplicate elements from an iterator. // Here, it removes consecutive duplicates from the vector [1., 1., 2., 3., // 3., 2., 2.]. 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` groups elements of an iterator into a map based on a // key. 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]) // `itertools` also offers `all`, `any`, `concat`, `fold`, "join", // `partition`, `sorted`, etc. }
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.
//! # Immutable Data Structures with `im` //! //! The `im` crate provides immutable data structures. //! These data structures are especially useful in functional //! programming, where data is not modified in place but rather //! new data structures are created with the desired changes. //! //! This said, `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 optimizations. //! Most operations are O(log n) or better. //! //! 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 fast and cheap, with actual copying only //! occurring when modifications are made. `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`. use im::HashMap; use im::HashSet; use im::Vector; use im::hashmap; use im::vector; 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); }
rpds
rpds provides persistent data structures with structural sharing.
//! # RPDS (Rust Persistent Data Structures) Example //! //! This example demonstrates the use of the `rpds` crate, which provides //! purely functional (immutable) data structures with structural sharing for //! efficiency. use rpds::HashTrieMap; use rpds::Vector; fn main() { // Persistent Vector with immutable updates: let v1: Vector<i32> = Vector::new().push_back(1).push_back(2).push_back(3); // Create a new vector with index 1 set to 20: let v2 = v1.set(1, 20).unwrap(); println!("Original v1: {}", v1); // [1, 2, 3] println!("Modified v2: {}", v2); // [1, 20, 3] println!("v1 is unchanged: {}", v1); // [1, 2, 3] // Iterating: for item in v2.iter() { println!("Item: {}", item); } // Persistent map implemented with a hash array mapped trie: let m1: HashTrieMap<String, i32> = HashTrieMap::new(); let m2 = m1.insert("one".to_string(), 1).insert("two".to_string(), 2); let m3 = m2.insert("three".to_string(), 3); println!("m2 size: {}", m2.size()); // 2 println!("m3 size: {}", m3.size()); // 3 // Lookup: println!("Value for 'two': {:?}", m3.get(&"two".to_string())); // Some(2) // Removal (creates a new map): let m4 = m3.remove(&"one".to_string()); println!("m4 after removal: {}", m4); println!("m3 is unchanged: {}", m3); }
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