Currying in rust Part 3 (The circle of life ... aka why borrowchecker ... why?!)

We stopped last time with changing our explicit curried function into a generic application. Also I added an addendum about 1 advantage of using generics over explicit definitions.

fn add<T>(x: T) -> impl Fn(T)-> T
    where T: num::Num + Copy
{
    move |y: T| x + y
}

Victor Moroz was kind enough to point out in comment that we don't need the num trait and can stay without external dependencies for the moment. And I am a huge fan of reducing the dependency graph if we can.

His suggestion was:

fn add<T: Add<Output=T> + Copy>(x: T) -> impl Fn(T) -> T {
  move | y: T | x + y 
}

which can be expressed in the following form as well:

fn add<T>(x: T) -> impl Fn(T)-> T
    where T: Add<Output=T> + Copy
{
    move |y: T| x + y
}

The where clause is mainly to move parts of the rules for our type based behaviour out of the function definition .

We will now take a look at the changes just to be sure we understand the differences what has happened:

  • we remove the num trait
  • we replaced it with the std::ops::Add; trait
  • we defined the output type of Add has to be the same type as our type we apply our function to
  • it still has to implement the Copy trait (because we're moving x into a closure and never return it)

The Copy trait is our first contact with the borrow checker and the 'cheap' solution. Instead of thinking about lifetimes and references in our program, we just copy the value.

Now no one wonders why our new starting point is:

fn add_curry<T>(x: T) -> impl Fn(T)-> T
    where T: Add<Output=T> + Copy
{
    move |y: T| x + y
}

Today we're going to take a look at the 'pipe' function my friend has written and why all of the sudden lifetimes get important esp. when using references.

Lets start at the problem that pipe solves. Pipe is, as the name suggests, a pipeline which means we prepare a pipeline and everything inside the pipeline gets applied to the value that gets passed into the pipeline.

This sound easy enough. Lets start with an arbitrary use case of application.

use std::ops::Add;

fn main() {
    let add1 = add(1);
    let add2 = add(2);
    let add3 = add(3);

    let result = add3(add2(add1(1)));

    println!("{}", result); // prints 7
}

fn add<T>(x: T) -> impl Fn(T)-> T
    where T: Add<Output=T> + Copy
{
    move |y: T| x + y
}

as we can see we prepare our 3 lambdas, apply them on the value 1 and print the result (the code is copy and paste ready give it a try)

This is nice but what if we want to reapply our 3 lambdas over and over again?

use std::ops::Add;

fn main() {
    let add1 = add(1);
    let add2 = add(2);
    let add3 = add(3);

    let result = add3(add2(add1(1)));
    let result2 = add3(add2(add1(2)));
    let result3 = add3(add2(add1(3)));

    println!("{}", result); // prints 7
    println!("{}", result2); // prints 8
    println!("{}", result3); // prints 9
}

fn add<T>(x: T) -> impl Fn(T)-> T
    where T: Add<Output=T> + Copy
{
    move |y: T| x + y
}

This no to bad, but as programmers we want to have less work maintaining our code. Which means we want to prepare add1, add2 and add3 only one time, then apply it over and over again so we just have to maintain it a 1 point.

if we want to do 1 thing over and over again, what would be our normal solution? Usually ... a loop. however we are able to achieve it (recursions, gotos for example) .

We will try to solve it with both ways, recursions (recursion in the next article) and loops but we will start with loops since most of us are more familiar writing 'for/do-while/while/loop' than applying the more functional recursion pattern. Gotos are - to my knowledge - not supported as of yet.

In order to store and use our functions as a pipeline we need a data-structure to put our functions in. A short disclaimer: Yes it's possible with macros we just don't want to have to many moving parts in one topic.

So lets talk about data structures in rust and which one to pick.

  • We in general only go in 1 direction.
  • We are not that interested in changing the parts inside of our structure.
  • We are not interested in addressing a particular member from the outside.

1 direction? multiple members? Vector to the rescue.

So we need to build our vector containing the prepared functions:

fn main() {
    let add1 = add(1);
    let add2 = add(2);
    let add3 = add(3);

    let mut pipeline = Vec::new();
    pipeline.push(&add1);
    pipeline.push(&add2);
    pipeline.push(&add3);

    // let pipeline = vec![&add1, &add2, &add3];
    let mut input = 1;

    for apply_on in pipeline.iter() {
        input = apply_on(input);
    }

    println!("{}", input); // prints 7
}

In it's very basic form this already all we need, but it's hard to reuse this code so we have to extract it to another function, but first a small cleanup to reduce some of the noise

fn main() {
    let add1 = add(1);
    let add2 = add(2);
    let add3 = add(3);

    let pipeline = vec![
        &add1,
        &add2,
        &add3
    ];
     .......
}

using the macro vec! for creating our vector lets us move into a more declarative form of writing code.

now we want to extract our business logic / intent / behaviour into a function so we can reuse it.

Why use let on the the add function and don't just pass in the results of our function invocation as reference? Well mainly because we are currently lazy and we want our compile to guess the needed information we're not providing at the moment. ;) We will however reach that state within this article and I hope by then it will be clear why we only change certain bits and parts to get to our goal.

fn pipe<T>(pipeline: Vec<Fn(T) -> T>, data: T) -> T {
    let mut _result = data;

    for apply_on in pipeline.iter() {
        _result = apply_on(_result);
    }

    _result
}

lets take a look at the parts of our pipe function definition:

  • name is pipe
  • T as our generic Type
  • it takes a vector of functions
    • those functions get our generic type T as input and return our generic type T as output
  • it takes a second parameter data of our type T
  • it returns something that is our type T

lets try and run it:

  --> src/main.rs:19:1
   |
19 | / fn pipe<T>(pipeline: Vec<Fn(T) -> T>, data: T) -> T
20 | | {
21 | |     let mut _result = data;
22 | |
...  |
27 | |     _result
28 | | }
   | |_^ `std::ops::Fn(T) -> T + 'static` does not have a constant size known at compile-time
   |
   = help: the trait `std::marker::Sized` is not implemented for `std::ops::Fn(T) -> T + 'static`
   = note: required by `std::vec::Vec`

not really what we want, lets look at the problem. The vector that needs to be prepared by our compiler does not know the actual size of itself.

Either we try to provide a certain size or since references in rust are always the same size we switch to references.

A brief summary: Pointers VS References

A reference is nothing but more like a meta pointer .... which doesn't really help if you're not familiar with those concepts I know!

Lets just say rather than copying a block of code in the memory (value based) we just point to an address in the memory and say 'hey look there'. That would be the idea of a pointer. The simplistic difference between a pointer and a reference is that a reference is something on its own in memory. It also allows us to add extra functionality where a pointer only points to a specific address.

This gets interesting with modern GCs (Garbage Collectors) for example in Java, JS or GO. One such use case would be the so called reference counting where the GC keeps track how many other parts of our code are using our reference so it can cleanup afterwards

Back to the problem at hand.

Lets just add the & in front of our pipe and our closures in our vector!

....
let pipeline = vec![
        &add1,
        &add2,
        &add3,
    ];
....
fn pipe<T>(pipeline: Vec<&Fn(T) -> T>, data: T) -> T

if we run this we get:

error[E0308]: mismatched types
  --> src/main.rs:14:23
   |
14 |     let result = pipe(pipeline, 1);
   |                       ^^^^^^^^ expected trait std::ops::Fn, found anonymized type
   |
   = note: expected type `std::vec::Vec<&std::ops::Fn(_) -> _>`
              found type `std::vec::Vec<&impl std::ops::Fn<({integer},)>>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0308`.

So it does not know what our types are. hmmm lets try something different

let pipeline = vec![
        |x: i32| x  + 1,
        |x: i32| x  + 2,
        |x: i32| x  + 3,
    ];

Now our compiler knows what's coming in ... and

error[E0308]: mismatched types
  --> src/main.rs:10:9
   |
10 |         |x: i32| x + 2,
   |         ^^^^^^^^^^^^^^ expected closure, found a different closure
   |
   = note: expected type `[closure@src/main.rs:9:9: 9:23]`
              found type `[closure@src/main.rs:10:9: 10:23]`
   = note: no two closures, even if identical, have the same type
   = help: consider boxing your closure and/or using it as a trait object

error[E0308]: mismatched types
  --> src/main.rs:14:23
   |
14 |     let result = pipe(pipeline, 1);
   |                       ^^^^^^^^ expected reference, found closure
   |
   = note: expected type `std::vec::Vec<&std::ops::Fn(_) -> _>`
              found type `std::vec::Vec<[closure@src/main.rs:9:9: 9:23]>`

error: aborting due to 2 previous errors

For more information about this error, try `rustc --explain E0308`

thanks for nothing .... it seam we need to change our approach. Lets return to our starting position where we changed our functions into references.

use std::ops::Add;

fn main() {
    let add1 = add(1);
    let add2 = add(2);
    let add3 = add(3);

    let pipeline = vec![
        &add1,
        &add2,
        &add3
    ];

    let result = pipe(pipeline, 1);

    println!("{}", result); // prints 7
}

fn pipe<T>(pipeline: Vec<&Fn(T) -> T>, data: T) -> T
{
    let mut _result = data;

    for apply_on in pipeline.iter() {
        _result = apply_on(_result);
    }

    _result
}

fn add<T>(x: T) -> impl Fn(T)-> T
    where T: Add<Output=T> + Copy
{
    move |y: T| x + y
}

changing the return type of add to fn (lowercase) wont help either since rust sees every closure as unique type .... hmm ... lets try something else .... lets put it in a box ... wait ... what is a box?

A box is to quote the rust documentation:

A pointer type for heap allocation.

great ... everything's clear now? I guess if you're a C / C++ Programmer who is really practicing it probably is ... but for us mere mortals who spend our life on the fruitful steps in proximity of our VM castles close to GC town .... we usually are not even sure what the heap and the stack is. So I will try to not embarrass myself to much but give an outline.

  • The Stack is the part of working memory that exists in context of our function calls
    • call over -> memory free for reuse
  • The Heap is the part of working memory that exists outside the function call context
    • call over -> memory still reserved for our stuff

So in our case the problem is that our compiler cannot resolve our closures as a specific type. So we move our closures outside of the function context into a Box and onto the heap. This way we can defer the unwrapped box to our closures. So we tell our compiler what is in the box and it does not define every closure as it's own type at compile time.

But what does this look like? first we need to change our add function and put the closure into a box

fn add<T>(x: T) -> Box<Fn(T)-> T>
    where T: Add<Output=T> + Copy
{
    Box::new(move |y: T| x + y)
}

what has changed?

  • we don't return an impl of Fn(T) -> T anymore but a Box containing a Fn(T) -> T
  • we put our entire closure into the Box and onto the Heap
fn pipe<T>(pipeline: Vec<&Box<Fn(T) -> T>>, data: T) -> T
    where T: Add<Output=T> + Copy
{
    let mut _result = data;

    for apply_on in pipeline.iter() {
        _result = apply_on(_result);
    }

    _result
}

what has changed?

  • we added a reference to a Box around our Fn inside the vector
  • we moved the T definition to the where clause

if we try to compile this we will get the following error message:

error[E0310]: the parameter type `T` may not live long enough
  --> src/main.rs:34:5
   |
31 | fn add<T>(x: T) -> Box<Fn(T)-> T>
   |        - help: consider adding an explicit lifetime bound `T: 'static`...
...
34 |     Box::new(move |y: T| x + y)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |

We got a lifetime issue our compiler does not know how to handle the lifetimes of our implementations. in our code we see it will work so we now need to convince our compiler it does as well.

fn add<'a, T>(x: T) -> Box<Fn(T)-> T + 'a>
    where T: Add<Output=T> + Copy, T: 'a
{
    Box::new(move |y: T| x + y)
}

So what did we do? we added a lifetime annotation: 'a and we tell our compiler that everything that we connect with 'a lives the same amount of time and as long as we're using one of the parts connected it should not clear the memory.

Now we can use our pipe function as intended :)

Thanks for reading :)

Comments (11)

Add a comment
Junfeng Liu's photo

You can define a compose function and create a pipeline with it:

use std::ops::Add;

fn main() {
    let add1 = add(1);
    let add2 = add(2);
    let add3 = add(3);

    let pipeline = compose(add3, compose(add2, add1));

    let result = pipeline(1);

    println!("{}", result); // prints 7
}

fn add<T>(x: T) -> impl Fn(T)-> T
    where T: Add<Output=T> + Copy
{
    move |y: T| x + y
}

fn compose<T,U,V>(f: impl Fn(V) -> T, g: impl Fn(U) -> V) -> impl Fn(U)-> T {
    move |x: U | f(g(x))
}
j's photo

stuff ;)

compose would've been the next one :) but first I wanted to go through macros, then unions and then composition :) because I wanted to go for some form of isomorphism :) But really cool thank you :)

Harald Hoyer's photo

You can implement a Pipeline trait for the Vec<>. Or here for anything returning an iterator, which iters over 'Fn(T) -> T' :-)

trait Pipeline<T> {
    fn pipe(self, data: T) -> T;
}

impl<T, U> Pipeline<T> for U
where
    U: IntoIterator,
    U::Item: Fn(T) -> T,
{
    fn pipe(self, data: T) -> T {
        let mut result = data;

        for apply_on in self.into_iter() {
            result = apply_on(result);
        }

        result
    }
}

Playground

j's photo

stuff ;)

Originally it was a trait something even similar, but we moved towards functions syntax (probably because to us it's a learning experience and we currently don't understand all the concepts in rust).

However :) since at some point it's going to be a lib we will likely implement them as traits again :)

thank you for the feedback! :)

Theo Belaire's photo

You don't need boxes!

play.rust-lang.org/?version=stable&mode..

I ran in to this when solving advent of code.

You can just write

    let pipeline = vec![
        &add1 as &Fn(_) -> _,
        &add2,
        &add3
    ];

and everything will work.

It solves the error

   |                       ^^^^^^^^ expected trait std::ops::Fn, found anonymized type

by casting the anonymized type to a trait.

You can also do

    let pipeline: Vec<&Fn(_) -> _> = vec![

If you prefer type annotations to casts.

Show all replies
endrin's photo

Modifying pipe signature to

fn pipe<T>(pipeline: Vec<impl Fn(T) -> T>, data: T) -> T

also solves the issue.

play.rust-lang.org/?version=stable&mode..

Larry Schirmer's photo

Having the compiler output in the article is a great addition. Compiler Driven Development! Great series and debugging life skills. Thanks

j's photo

stuff ;)

Thank you! :)

yes :D the compiler in rust is really awesome. I think it helps others to see my mistakes rather than just the solutions of problems. That's why I also try to put in different angles how to solve things :D and if you find anything I should add please let me know :)

I am really open to criticism :)

Geordon Worley's photo

You can also make a closure:

let my_add = |x: i32| add3(add2(add1(x)));
let seven = my_add(1);
let eight = my_add(2);
j's photo

stuff ;)

True :) thx :) i also already have a macro for it as well. I like your pragmatic approach though :)