Type synonym for functions in Rust

I would like to have type synonyms for functions, so that they are less cluttersome. For instance, I would like something like this:

type MyType<T, V> = FnMut(T) -> (T, V);

fn compose<T, U, V>(fst: MyType<T, U>, snd: MyType<U, V>) -> MyType<T, V> {
    |mut& x| {
        let (t, u) = fst(x);
        let (_, v) = snd(u);
        (t, v)
    }
}

But it fails to compile. I can add dyn keywords but type aliases cannot be used as traits.

Something like this works in Haskell:

type MyType a b = a -> (a, b)

compose :: MyType a b -> MyType b c -> MyType a c
compose f g = \x ->
    let (a, b) = f x
        (_, c) = g b
    in  (a, c)

A less-toy-example use-case: The synonym needs to use FnMut, as I am trying to make synonyms based off nom's Parser.

Peter Hall's answer does a good job of explaining the differences in the type systems between Rust and Haskell. He is much more knowledgeable about that, so I will point to his answer for any explanations about that. Instead, I want to give you a practical way that you can accomplish what you want within Rust.

One of the things that's very different about Rust compared to other common languages is that traits in Rust can be implemented on pretty much any type, including types your crate doesn't define. This allows you to declare a trait and then implement it on anything else, in contrast to languages where you can only implement interfaces on types that you are defining. This gives you an incredibly large amount of freedom, and it takes some time to fully grasp the potential this freedom grants you.

So, while you can't create aliases for traits, you can create your own trait that is automatically implemented on anything that implements the other trait. Semantically this is different, but it winds up being close enough to the same thing that you can use it like an alias in most cases.

trait MyType<T, V>: FnMut(T) -> (T, V) {}

This declares the trait MyType with the same generic arguments, but requires that anything implementing this trait must also implement the closure trait. This means when the compiler sees something implementing MyType<T, V>, it knows it also implements the closure supertrait. This is important so that you can actually invoke the function.

That's half of the solution, but now we need MyType to actually be implemented on anything implementing the closure trait. This is pretty easy to do:

impl<F, T, V> MyType<T, V> for F
where F: FnMut(T) -> (T, V) {}

So now we have a trait that:

• Can only be implemented on things that also implement the required closure trait, implying that the closure trait is also implemented.
• Is automatically implemented on everything implementing the required closure trait.

These are two sides of the equation that makes MyType<T, V> and FnMut(T) -> (T, V) effectively equivalent, even if they aren't actually the same trait within the type system. They aren't the same trait, but you can use them almost interchangeably.

Now, we can adjust the definition of compose around our new trait:

fn compose<T, U, V>(
    mut fst: impl MyType<T, U>,
    mut snd: impl MyType<U, V>,
) -> impl MyType<T, V> {
    move |x| {
        let (t, u) = fst(x);
        let (_, v) = snd(u);
        (t, v)
    }
}

A few important changes here:

• We use impl MyType<_, _> so that the function can receive anything implementing your trait, which includes the closure types you're trying to target. Note there is no dyn which also means there is no dynamic dispatch. This removes a level of indirection.
• We also return impl MyType<_, _> which means we can return a closure without boxing it, which both prevents an unnecessary heap allocation as well as an unnecessary level of indirection.
• Because of the prior two points, the compiler can potentially fully inline both calls to compose as well as calls to the closure it returns, which can make this abstraction "free" in terms of runtime performance!
• We had to change fst and snd to be mut in order to invoke the functions because the underlying closure type is FnMut.
• We had to add move to the closure so that the closure takes ownership of fst and snd, otherwise it would try to borrow function local variables in the return value, which cannot work.

(Playground)

Functions in Rust are expressed differently from how they are expressed in Haskell.

In Haskell, function signatures correspond to types. Two functions with the same signature have the same type, even if they are implemented differently and even if they are closures with different environments. The type is purely derived from the arguments and return value of the function.

In Rust, there is only one "class" of nameable function types, that is fn. These are function pointers that have no environment. Closures are always different types, even if they have the same arguments and return type. This is just a trade off in the languages. In Rust Fn, FnOnce and FnMut are traits not types,
and you cannot create aliases for traits.

There is an RFC for trait aliases in Rust, which might partly do what you want. But this has been going since 2017 and does not appear close to being stabilised.