Crates for functional programming


#1

Are there any good crates for functional programming? That is, crates that provide useful but relitively trivial traits/functions for functional programming? For example, I needed a function to pull out the first element of a pair so I could call my_pair_option.map(first) instead of my_pair_option.map(|(a, _)| a) as I find the former more readable. I could use the following but implementing things like this myself for every project doesn’t really make sense (it’s easier to just write my_pair_option.map(|(a, _)| a)).

pub trait Pair {
    type First;
    type Second;
    fn first(self) -> Self::First;
    fn second(self) -> Self::Second;
}

impl<A, B> Pair for (A, B) {
    type First = A;
    type Second = B;

    fn first(self) -> A {
        self.0
    }
    fn second(self) -> B {
        self.1
    }
}

impl<'a, A, B> Pair for &'a (A, B) {
    type First = &'a A;
    type Second = &'a B;

    fn first(self) -> &'a A {
        &self.0
    }
    fn second(self) -> &'a B {
        &self.1
    }
}

pub fn first<P: Pair>(pair: P) -> P::First {
    pair.first()
}
pub fn second<P: Pair>(pair: P) -> P::Second {
    pair.second()
}

#2

itertools is pretty amazing.


#3

I know but that’s for iterators only. I’m talking about general purpose tools: id, first, second, third, flip, etc.


#4

uh oh, one more question and you’ll soon be responsible for maintaining such a crate :stuck_out_tongue:


#5

Here’s a fun idea. Overload firstness so that first((1, 2)) == 1 and first(&(1, 2)) == &1

implementation @ playground


#6

And so it begins…

Crate: https://crates.io/crates/tool


#7

Unfortunately, many of the fun tools require features rust doesn’t currently have: HKT, variadic arguments, custom implementations of Fn* (unstable), etc…


#8

Hm, are higher-order functions possible on stable?

let slice: &[(T,U)] = /* ... */;
let vec: Vec<T> = slice.iter().map(cloning(first)).collect();

// or maybe
let vec: Vec<T> = slice.iter().map(compose(Clone::clone, first)).collect();

// :D
let vec: Vec<i32> = xs.zip(ys).map(uncurry(Add::add)).collect();

(never mind that uncurry is a terrible name for a Rust function)


#9

Not on stable. On nightly, one can directly implement Fn* (unlikely to be stabilized) or return a closure using impl Trait syntax (hopefully going to be stabilized in the near future). Here’s a compose function:

pub fn compose<A, B, C, F, G>(mut f: F, mut g: G) -> impl FnMut(A) -> C
    where G: FnMut(A) -> B,
          F: FnMut(B) -> C,
{
    move |a: A| { f(g(a)) }
}

Unfortunately, this restricts the impl to FnMut. With the fn_traits and unboxed_closures features, it’s possible to abstract over FnMut, FnOnce, and Fn. Example:


pub struct Uncurry<F>(F);

impl<T, F> FnOnce<(T,)> for Uncurry<F>
    where F: FnOnce<T>
{
    type Output = F::Output;

    extern "rust-call" fn call_once(self, (args,): (T,)) -> F::Output {
        self.0.call_once(args)
    }
}

impl<T, F> FnMut<(T,)> for Uncurry<F>
    where F: FnMut<T>
{
    extern "rust-call" fn call_mut(&mut self, (args,): (T,)) -> F::Output {
        self.0.call_mut(args)
    }
}

impl<T, F> Fn<(T,)> for Uncurry<F>
    where F: Fn<T>
{
    extern "rust-call" fn call(&self, (args,): (T,)) -> F::Output {
        self.0.call(args)
    }
}


pub fn uncurry<A, F>(f: F) -> Uncurry<F> {
    Uncurry(f)
}

#10

I… wow. It never occurred to me that impl Trait could be used for the Fn traits. I currently have my own ungodly solution for making functions like these, in the form of a unboxed-closure-generating macro; I wonder how many of my usages of it could be replaced with an impl Fn*.

…then again, it also never occurred to me that Fn traits could be a candidate for conditional trait implementation, which kind of tosses the idea right back out the window! Though I guess it’s at least good enough for impl FnOnce :stuck_out_tongue:

(it occurs to me now that I apparently already knew the answer to my own question; but I had forgotten until I saw your example)


#11

Here’s an odd and unpolished functional tool, a helper for recursive closures: Fix from crate odds. The crate doesn’t otherwise have any “functional tools” I think…

Its only ever real use looks like this:

// check all parent links
let check_parents = |f: Fix<_, _>, entry| {
    let entry: &Entry<_, _> = entry;
    entry.children.iter().all(|c| ptr_eq(c.parent, entry) && f.call(&**c))
};
assert!(Fix(&check_parents).call(&*m.root));

With unstable features, the explicit .call() can be removed. Not sure if the other lifetime and type inference related drawbacks can be improved upon.

Edit: Ok, adding a simple fix function makes it much easier to call the combinator and have type inference work with you. Updated usage:

// check all parent links
assert!(fix(&*m.root, |f, entry| {
    entry.children.iter().all(|c| ptr_eq(c.parent, entry) && f.call(&**c))
}));