transducers-rs

Cargo.toml

[package]
name = "transducers"
version = "0.1.0"
authors = ["Arnavion <[email protected]>"]
edition = "2018"

[dependencies]
num-traits = { version = "0.2", default-features = false }

[dev-dependencies]
rand = "0.8"

lib.rs

#![feature(
    generic_associated_types,
    min_type_alias_impl_trait,
)]
#![deny(rust_2018_idioms, warnings, clippy::all, clippy::pedantic)]
#![allow(
    incomplete_features,
    clippy::default_trait_access,
    clippy::must_use_candidate,
    clippy::shadow_unrelated,
    clippy::too_many_lines,
)]

//! A Rust implementation of [Clojure transducers.](https://clojure.org/reference/transducers)
//!
//! Historical context:
//!
//! - <https://clojure.org/news/2012/05/08/reducers>
//! - <https://clojure.org/news/2012/05/15/anatomy-of-reducer>
//! - <https://clojure.org/news/2014/08/06/transducers-are-coming>
//!
//! # Example
//!
//! ```rust
//! // https://github.com/ianrumford/clojure-transducer-examples/blob/master/doc/2014-08-08-Some-trivial-examples-of-using-Clojure-Transducers.org
//!
//! use transducers::{
//!     collect, count, filter, id, map,
//!     FnMutFolder,
//!     FoldExt, Transducer,
//! };
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! enum Home {
//!     North,
//!     South,
//!     West,
//!     East,
//! }
//!
//! impl rand::distributions::Distribution<Home> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Home {
//!         *rand::seq::SliceRandom::choose(&[Home::North, Home::South, Home::West, Home::East][..], rng).unwrap()
//!     }
//! }
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! enum Sex {
//!     Male,
//!     Female,
//! }
//!
//! impl rand::distributions::Distribution<Sex> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Sex {
//!         *rand::seq::SliceRandom::choose(&[Sex::Male, Sex::Female][..], rng).unwrap()
//!     }
//! }
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! enum Role {
//!     Parent,
//!     Child,
//! }
//!
//! impl rand::distributions::Distribution<Role> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Role {
//!         *rand::seq::SliceRandom::choose(&[Role::Parent, Role::Child][..], rng).unwrap()
//!     }
//! }
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! struct Family(&'static str);
//!
//! impl rand::distributions::Distribution<Family> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Family {
//!         Family(rand::seq::SliceRandom::choose(&["smith", "jones", "brown", "williams", "taylor", "davies"][..], rng).unwrap())
//!     }
//! }
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! struct Name(&'static str);
//!
//! impl rand::distributions::Distribution<Name> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Name {
//!         Name(rand::seq::SliceRandom::choose(&["chris", "jim", "mark", "jon", "lisa", "kate", "jay", "june", "julie", "laura"][..], rng).unwrap())
//!     }
//! }
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! struct Age(u32);
//!
//! impl rand::distributions::Distribution<Age> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Age {
//!         Age(rng.gen_range(0..100))
//!     }
//! }
//!
//! #[derive(Clone, Copy, Debug, Eq, PartialEq)]
//! struct Person {
//!     home: Home,
//!     family: Family,
//!     name: Name,
//!     age: Age,
//!     sex: Sex,
//!     role: Role,
//! }
//!
//! impl rand::distributions::Distribution<Person> for rand::distributions::Standard {
//!     fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> Person {
//!         Person {
//!             home: rng.gen(),
//!             family: rng.gen(),
//!             name: rng.gen(),
//!             age: rng.gen(),
//!             sex: rng.gen(),
//!             role: rng.gen(),
//!         }
//!     }
//! }
//!
//! let village = [
//!     Person { home: Home::North, family: Family("smith"), name: Name("sue"), age: Age(37), sex: Sex::Female, role: Role::Parent },
//!     Person { home: Home::North, family: Family("smith"), name: Name("stan"), age: Age(35), sex: Sex::Male, role: Role::Parent },
//!     Person { home: Home::North, family: Family("smith"), name: Name("simon"), age: Age(7), sex: Sex::Male, role: Role::Child },
//!     Person { home: Home::North, family: Family("smith"), name: Name("sadie"), age: Age(5), sex: Sex::Female, role: Role::Child },
//!
//!     Person { home: Home::South, family: Family("jones"), name: Name("jill"), age: Age(45), sex: Sex::Female, role: Role::Parent },
//!     Person { home: Home::South, family: Family("jones"), name: Name("jeff"), age: Age(45), sex: Sex::Male, role: Role::Parent },
//!     Person { home: Home::South, family: Family("jones"), name: Name("jackie"), age: Age(19), sex: Sex::Female, role: Role::Child },
//!     Person { home: Home::South, family: Family("jones"), name: Name("jason"), age: Age(16), sex: Sex::Female, role: Role::Child },
//!     Person { home: Home::South, family: Family("jones"), name: Name("june"), age: Age(14), sex: Sex::Female, role: Role::Child },
//!
//!     Person { home: Home::West, family: Family("brown"), name: Name("billie"), age: Age(55), sex: Sex::Female, role: Role::Parent },
//!     Person { home: Home::West, family: Family("brown"), name: Name("brian"), age: Age(23), sex: Sex::Male, role: Role::Child },
//!     Person { home: Home::West, family: Family("brown"), name: Name("bettie"), age: Age(29), sex: Sex::Female, role: Role::Child },
//!
//!     Person { home: Home::East, family: Family("williams"), name: Name("walter"), age: Age(23), sex: Sex::Male, role: Role::Parent },
//!     Person { home: Home::East, family: Family("williams"), name: Name("wanda"), age: Age(3), sex: Sex::Female, role: Role::Child },
//! ];
//!
//! {
//!     let expected_num_persons = village.len();
//!     let actual_num_persons = village.iter().transduce(id(), count());
//!     println!("0: {}", actual_num_persons);
//!     assert_eq!(expected_num_persons, actual_num_persons);
//! }
//!
//! let is_child = |person: &&Person| person.role == Role::Child;
//! {
//!     let expected_num_children = village.iter().filter(is_child).count();
//!     let actual_num_children = village.iter().transduce(filter(is_child), count());
//!     println!("1: {}", actual_num_children);
//!     assert_eq!(expected_num_children, actual_num_children);
//! }
//!
//! let is_brown = |person: &&Person| person.family.0 == "brown";
//! {
//!     let expected_num_brown_children = village.iter().filter(is_child).filter(is_brown).count();
//!     let actual_num_brown_children = village.iter().transduce(filter(is_brown).then(filter(is_child)), count());
//!     println!("2: {}", actual_num_brown_children);
//!     assert_eq!(expected_num_brown_children, actual_num_brown_children);
//! }
//!
//! let name_starts_with_j = |person: &&Person| person.name.0.starts_with('j');
//! {
//!     let expected_num_children_whose_name_starts_with_j = village.iter().filter(is_child).filter(name_starts_with_j).count();
//!     let actual_num_children_whose_name_starts_with_j = village.iter().transduce(filter(is_child).then(filter(name_starts_with_j)), count());
//!     println!("3: {}", actual_num_children_whose_name_starts_with_j);
//!     assert_eq!(expected_num_children_whose_name_starts_with_j, actual_num_children_whose_name_starts_with_j);
//! }
//!
//! {
//!     let expected_children_whose_name_starts_with_j = village.iter().filter(is_child).filter(name_starts_with_j);
//!     let actual_children_whose_name_starts_with_j: Vec<_> = village.iter().transduce(filter(is_child).then(filter(name_starts_with_j)), collect());
//!     println!("4: {:?}", actual_children_whose_name_starts_with_j);
//!     assert!(expected_children_whose_name_starts_with_j.eq(actual_children_whose_name_starts_with_j.iter().copied()));
//! }
//!
//! {
//!     let is_on_or_below_equator = |person: &&Person| match person.home { Home::North => false, Home::South | Home::West | Home::East => true };
//!     let age = |person: &Person| person.age.0;
//!
//!     let expected_average_age_of_children_on_or_below_equator =
//!         village.iter().filter(is_child).filter(is_on_or_below_equator).fold((0, 0_usize), |(age_sum, num), person| (age_sum + age(person), num + 1));
//!
//!     let actual_average_age_of_children_on_or_below_equator =
//!         village.iter().transduce(
//!             filter(is_child).then(filter(is_on_or_below_equator)).then(map(age)),
//!             (
//!                 FnMutFolder::new(|(age_sum, num), age| (age_sum + age, num + 1)),
//!                 (0_u32, 0_usize),
//!             ),
//!         );
//!
//!     println!(
//!         "5: {}",
//!         f64::from(actual_average_age_of_children_on_or_below_equator.0) /
//!             { #[allow(clippy::cast_precision_loss)] { actual_average_age_of_children_on_or_below_equator.1 as f64 } }
//!     );
//!
//!     assert_eq!(expected_average_age_of_children_on_or_below_equator, actual_average_age_of_children_on_or_below_equator);
//! }
//!
//! {
//!     let mut rng = rand::thread_rng();
//!     let visitors = rand::Rng::sample_iter(&mut rng, &rand::distributions::Standard).take(/*10000000*/ 1000);
//!     let is_child = |person: &Person| person.role == Role::Child;
//!     let is_brown = |person: &Person| person.family.0 == "brown";
//!     let actual_num_visiting_brown_children = visitors.transduce(filter(is_brown).then(filter(is_child)), count());
//!     println!("7: {}", actual_num_visiting_brown_children);
//! }
//! ```

/// Aggregates an initial `Self::Result` and zero or more `TInput`s into a `Self::Result`.
pub trait Folder<TInput> {
    type Result;

    fn apply(&mut self, previous: Self::Result, current: TInput) -> Self::Result;
}

pub struct FnMutFolder<F, TResult>(F, std::marker::PhantomData<TResult>);

impl<F, TResult> FnMutFolder<F, TResult> {
    pub fn new(f: F) -> Self {
        FnMutFolder(f, Default::default())
    }
}

impl<F, TResult, TInput> Folder<TInput> for FnMutFolder<F, TResult> where F: FnMut(TResult, TInput) -> TResult {
    type Result = TResult;

    fn apply(&mut self, previous: Self::Result, current: TInput) -> Self::Result {
        (self.0)(previous, current)
    }
}

/// Returns a counting [`Folder`] and the initial value for use with [`FoldExt::transduce`].
pub fn count<TInput>() -> (impl Folder<TInput, Result = usize>, usize) {
    (FnMutFolder::new(|previous, _| previous + 1), 0)
}

/// Returns a summing [`Folder`] and the initial value for use with [`FoldExt::transduce`].
pub fn sum<
    TInput,
    TResult: num_traits::Zero + std::ops::Add<TInput, Output = TResult>,
>() -> (impl Folder<TInput, Result = TResult>, TResult) {
    (FnMutFolder::new(|previous, current| previous + current), num_traits::Zero::zero())
}

/// Returns a [`Folder`] that collects the elements into a `TResult` collection,
/// and the empty collection for use as the initial value with [`FoldExt::transduce`].
pub fn collect<
    TResult: Default + CollectionAppend,
>() -> (impl Folder<<TResult as CollectionAppend>::Element, Result = TResult>, TResult) {
    (FnMutFolder::new(CollectionAppend::append), Default::default())
}

/// Provides zero or more `TInput` as the inputs of a [`Folder`].
pub trait Fold<TInput>: Sized {
    fn fold<TInputFolder: Folder<TInput>>(self, folder: TInputFolder, init: TInputFolder::Result) -> TInputFolder::Result;
}

pub trait FoldExt<TInput>: Fold<TInput> {
    /// Transduce this `Fold` with the given [`Transducer`] and [`Folder`].
    fn transduce<
        TOutput,
        TTransducer: Transducer<TInput, TOutput>,
        TOutputFolder: Folder<TOutput>,
    >(
        self,
        transducer: TTransducer,
        (merge, initial): (TOutputFolder, TOutputFolder::Result),
    ) -> TOutputFolder::Result {
        self.fold(transducer.apply(merge), initial)
    }
}

impl<TInput, F: Fold<TInput>> FoldExt<TInput> for F {}

impl<I: IntoIterator> Fold<I::Item> for I {
    fn fold<TInputFolder: Folder<I::Item>>(self, mut folder: TInputFolder, init: TInputFolder::Result) -> TInputFolder::Result {
        Iterator::fold(self.into_iter(), init, |previous, current| folder.apply(previous, current))
    }
}

/// A collection to which an element can be appended.
pub trait CollectionAppend {
    type Element;

    fn append(self, element: Self::Element) -> Self;
}

impl<T> CollectionAppend for Vec<T> {
    type Element = T;

    fn append(mut self, element: Self::Element) -> Self {
        self.push(element);
        self
    }
}

/// A `Transducer<TInput, TOutput>` converts a [`Folder`]`<TOutput>` into a [`Folder`]`<TInput>` with the same `Result`.
pub trait Transducer<TInput, TOutput>: Sized {
    type InputFolder<TOutputFolder: Folder<TOutput>>: Folder<TInput, Result = TOutputFolder::Result>;

    fn apply<TOutputFolder: Folder<TOutput>>(self, output_folder: TOutputFolder) -> Self::InputFolder<TOutputFolder>;

    /// Composes `self` with the given `Transducer<TOutput, TOutput2>` to produce a `Transducer<TInput, TOutput2>`.
    fn then<
        TOutput2,
        TTransducerOther: Transducer<TOutput, TOutput2>,
    >(self, other: TTransducerOther) -> ComposeTransducer<Self, TTransducerOther, TOutput> {
        ComposeTransducer(self, other, std::marker::PhantomData)
    }
}

pub struct ComposeTransducer<TTransducer1, TTransducer2, TIntermediate>(
    TTransducer1,
    TTransducer2,
    std::marker::PhantomData<TIntermediate>,
);

impl<
    TInput,
    TIntermediate,
    TOutput,
    TTransducer1: Transducer<TInput, TIntermediate>,
    TTransducer2: Transducer<TIntermediate, TOutput>,
> Transducer<TInput, TOutput> for ComposeTransducer<TTransducer1, TTransducer2, TIntermediate> {
    type InputFolder<TOutputFolder: Folder<TOutput>> = TTransducer1::InputFolder<TTransducer2::InputFolder<TOutputFolder>>;

    fn apply<TOutputFolder: Folder<TOutput>>(self, output_folder: TOutputFolder) -> Self::InputFolder<TOutputFolder> {
        self.0.apply(self.1.apply(output_folder))
    }
}

/// An identity transducer returns the output folder as the input folder.
pub fn id<TInput>() -> impl Transducer<TInput, TInput> {
    struct IdentityTransducer;

    impl<TInput> Transducer<TInput, TInput> for IdentityTransducer {
        type InputFolder<TOutputFolder: Folder<TInput>> = TOutputFolder;

        fn apply<TOutputFolder: Folder<TInput>>(self, output_folder: TOutputFolder) -> Self::InputFolder<TOutputFolder> {
            output_folder
        }
    }

    IdentityTransducer
}

/// A map transducer takes an `FnMut(TInput) -> TOutput` and uses it
/// to convert a [`Folder`]`<TOutput>` into a [`Folder`]`<TInput>` with the same `Result`
/// by converting all `TInput`s to `TOutput`s before feeding them to the output folder.
pub fn map<TInput, TOutput, F: FnMut(TInput) -> TOutput>(f: F) -> impl Transducer<TInput, TOutput> {
    struct MapTransducer<F>(F);

    impl<TInput, TOutput, F: FnMut(TInput) -> TOutput> Transducer<TInput, TOutput> for MapTransducer<F> {
        type InputFolder<TOutputFolder: Folder<TOutput>> = impl Folder<TInput, Result = TOutputFolder::Result>;

        fn apply<TOutputFolder: Folder<TOutput>>(mut self, mut output_folder: TOutputFolder) -> Self::InputFolder<TOutputFolder> {
            FnMutFolder::new(move |previous, current| {
                output_folder.apply(previous, (self.0)(current))
            })
        }
    }

    MapTransducer(f)
}

/// A filter transducer takes an `FnMut(&TInput) -> bool` and uses it
/// to convert a [`Folder`]`<TInput>` into a [`Folder`]`<TInput>` with the same `Result`
/// by only feeding those `TInput`s to the folder for which the `FnMut` returns `true`.
pub fn filter<TInput, F: FnMut(&TInput) -> bool>(f: F) -> impl Transducer<TInput, TInput> {
    struct FilterTransducer<F>(F);

    impl<TInput, F: FnMut(&TInput) -> bool> Transducer<TInput, TInput> for FilterTransducer<F> {
        type InputFolder<TOutputFolder: Folder<TInput>> = impl Folder<TInput, Result = TOutputFolder::Result>;

        fn apply<TOutputFolder: Folder<TInput>>(mut self, mut output_folder: TOutputFolder) -> Self::InputFolder<TOutputFolder> {
            FnMutFolder::new(move |previous, current| {
                if (self.0)(&current) {
                    output_folder.apply(previous, current)
                }
                else {
                    previous
                }
            })
        }
    }

    FilterTransducer(f)
}