Storing a closure in a structure — cannot infer an appropriate lifetime

Question

I'm trying to implement the State monad in Rust (State is effectively a wrapper over a function which takes original state and returns modified state and some result). This is how one can implement State in Haskell (monad operations where renamed to unit and bind for sake of simplicity):

data State s u = State { run :: s -> (u, s) }

-- return
unit :: u -> State s u
unit u = State $ \s -> (u, s)

-- (>>=)
bind :: State s u -> (u -> State s a) -> State s a
bind m f = State $ \s ->
             let (u, s') = run m s
             in run (f u) s'

So I try to rewrite it in Rust:

pub struct State<'r, S, U> {
    priv run: 'r |S| -> (U, S)
}

pub fn unit<'r, S, U>(value: U) -> State<'r, S, U> {
    State {
        run: |state| (value, state)
    }
}

(Actually I'm not sure if the definition of the run field is legal — it's said to be a bug).

This code doesn't compile:

/some/path/lib.rs:31:12: 31:36 error: cannot infer an appropriate lifetime due to conflicting requirements
/some/path/lib.rs:31         run: |state| (value, state)
                                ^~~~~~~~~~~~~~~~~~~~~~~~
/some/path/lib.rs:29:52: 33:2 note: first, the lifetime cannot outlive the block at 29:51...
/some/path/lib.rs:29 pub fn unit<'r, S, U>(value: U) -> State<'r, S, U> {
/some/path/lib.rs:30     State {
/some/path/lib.rs:31         run: |state| (value, state)
/some/path/lib.rs:32     }
/some/path/lib.rs:33 }
/some/path/lib.rs:31:12: 31:36 note: ...so that closure does not outlive its stack frame
/some/path/lib.rs:31         run: |state| (value, state)
                                ^~~~~~~~~~~~~~~~~~~~~~~~
/some/path/lib.rs:29:52: 33:2 note: but, the lifetime must be valid for the lifetime &'r  as defined on the block at 29:51...
/some/path/lib.rs:29 pub fn unit<'r, S, U>(value: U) -> State<'r, S, U> {
/some/path/lib.rs:30     State {
/some/path/lib.rs:31         run: |state| (value, state)
/some/path/lib.rs:32     }
/some/path/lib.rs:33 }
/some/path/lib.rs:30:5: 30:10 note: ...so that types are compatible (expected `State<'r,S,U>` but found `State<,S,U>`)
/some/path/lib.rs:30     State {
                         ^~~~~
error: aborting due to previous error

Seems like I need to explicitly specify the lifetime for the closure expression when instantiating State in unit, but I just don't know how, so I need help here. Thanks.

---

EDIT: Unfortunately, I cannot use procs (as Vladimir suggested), because a State can be executed arbitrary number of times.

Answer 1

The error is completely legitimate. Currently it is completely impossible to return closures which can be called multiple times from functions (unless they were passed to these functions as arguments).

You can easily find out that you have made a mistake in lifetimes usage when you look for lifetime annotations position. When lifetime parameter is used only in arguments or only in return values, then there is a mistake in your code. This is exactly your case - unit has 'r lifetime parameter, but it is used only in return value.

Your code fails to compile because you're creating stack closure and are trying to store it inside an object which will be returned to the caller. But the closure is created on the stack, and when you return from the function, that stack space is invalidated, i.e. your closure is destroyed. Borrow checker prevents this.

Currently there are only two kinds of closures in Rust - stack boxed closures and one-off heap boxed closures (procs). You could do what you want with a proc, but you will be able to call it only once. I'm not sure if this is OK for your needs, but here you go:

pub struct State<S, U> {
    priv run: proc(S) -> (U, S)
}

pub fn unit<S: Send, U: Send>(value: U) -> State<S, U> {
    State {
        run: proc(state) (value, state)
    }
}

I had to add Send kind because procs need their environment to be sendable.

In future, when (or if) dynamically sized types land, you will be able to create regular boxed closure which can be called multiple times and which own their environment. But DST are still in design and development.