Difficulty of function currying in Rust

Rust has functional aspects, which improve the language enormously, but..

If you say functional language then you really mean curried function application, which makes functional language extremely concise and good for building DSLs.

Rust cannot do currying cleanly for numerous reasons: It's C-like function application foo(x,y) instead of ML-style function application foo x y. It's simplistic self focused trait design, as opposed to type classes, modules, etc. As a result, Rust DSLs work via proc macros.

I've seen one nice blog post about currying not working well with Rust, but not sure where now. Anyone?

There are related threads like https://github.com/rust-lang/rfcs/issues/2049 though. Also https://boats.gitlab.io/blog/post/the-problem-of-effects/

2 Likes

Debate over the meaning of "functional" aside, am I to conclude that Rust is "not a functional language" because it doesn't support currying? If so, is that a problem?

Because Rust doesn't support inheritance, some people consider it "not an object-oriented language". Debate over the meaning of "object-oriented" aside, this doesn't seem to have a negative impact on its usefulness in a wide range of applications, and some people even consider the absence of first-class support for inheritance a good thing. You can still contrive inheritance-like patterns by combining Rust's other features, but many of us don't feel the need.

9 Likes

I, for one, don't.

That said, I have encountered a few cases where partial application would have made the code more elegant. It's not always the first argument that I want to fix though, so I really don't miss curried functions.

I don't see any technical or practical reason why that couldn't work with one particular syntax or another.

2 Likes

I'll clarify: Rust needed to sacrifice currying to champion safe zero-cost abstractions, not due to conflicts, but to simplify the problem.

It'd rock if someone designed a curried ML-style language that provides rust's safe zero-cost abstraction, including borrowing, but they'd be doing so by building upon lessons learned from Rust's development, and perhaps considerable code, like NLL, MIR, etc. In particular, you could not make such a language work without dropping unused closures, which goes beyond NLL. I'd wage it'd require polymorphic closures too. You could not design such a language without seeing Rust post-NLL, post-chalk, etc.

I cannot find that old blog post about currying conflicting with rust's trait system.

1 Like

One way to implement currying is to use impl Trait to return a closure with one less function parameter.

fn curried<Ft>(func: F, arg: u32) -> impl Fn(&str, bool) -> String
where
    F: Fn(u32, &str, bool) -> String
{
    move |b: &str, c: bool| { func(arg, b, c) }
}

This could be made generic over the argument type using normal generics:

fn curried<F, A, B, C, Ret>(func: F, arg: A) -> impl Fn(B, C) -> Ret
where
    F: Fn(A, B, C) -> Ret
{
    move |b: B, c: C| { func(arg, b, c) }
}

From here, you could probably abstract this out into a trait which gets implemented for anything callable with 0 to N arguments (Rust doesn't let you have a variable number of generic type parameters so we kinda fudge it with macros).

Unfortunately it's not possible for a trait method to return impl Trait, so you also incur some additional runtime overhead with dynamic dispatch and heap allocations (e.g. by returning Box<dyn Fn(B, C) -> Ret>).


Forgive me for being pedantic, but I'd like to address a couple comments you made in your initial post. They may help clear up some frustrations you've been having.

The position of the parentheses is just syntax. When you parse foo x y and foo(x, y) the two expressions would look identical to the compiler, so I don't think it's really a problem.

This is also not correct, Rust traits are a lot closer to Haskell type classes than Java interfaces. It's just fine for traits to have function members that don't reference self in any way.

I've seen someone implement a brainfuck interpreter purely with traits and the type system, there's also a type-level counting system (typenum) which can be used to do math with the typesystem (e.g. say you are doing matrix math and want the dimensions to be encoded directly in the type).

I haven't really seen macros being used as a workaround for lack of functional programming tools. Rust typically uses macro_rules macros for the same reason that you would in Lisp, to transform a tree of source code at compile time.

If the transformations are more than a simple reshuffling of tokens, procedural macros give you access to a turing complete language (Rust) to let you do arbitrary computations at compile time to generate the code you want.

11 Likes

Correct me if I'm wrong, but isn't this essentially function currying?

    let add = |x, y| { x + y };

    let inc = |x| { add(x, 1) };
    let dec = |x| { add(x, -1) };
    
    dbg!(inc(6));
    dbg!(dec(6));

Or is this just too much syntax? (all things considered - it's not too bad!)

1 Like

Getting into Rust is eye opening.

Programming since 1975 and I never knew what a curried function is or that I might need one. I like many things curried but functions?

Looks like just enough syntax to me.

1 Like

It reminds me of the Blub Paradox. When you get introduced to these "advanced" concepts like monads (think Result, Iterator, Future) you're like "why would I ever want to do something like that?", then after using it for a while you're like "how did we ever make anything useful with just C?".

Currying (and partial application in general) is particularly nice when you already know one or more arguments to a function and don't want to carry them around to where the function is actually used.

6 Likes

I think you are right.

People did not see the need for can openers before someone else invented the can problem. Likewise many other things we apparently need now a days. From can openers to smart phones.

I guess it's the same in programming. Nobody needed OOP till they had to program GUIs for example.

Interestingly the Blub link you posted says:

> Most people without the experience of them can't see language features as really useful things. I know an otherwise extremely talented programmer who can't see the value of garbage collection and thinks it simply encourages "lazy programming" even as he struggles to find the right location to delete objects shared and referenced by many others.

Well, Rust consciously moved away from garbage collection. Are the Rust devs suffering from "Blub Syndrome"? No, they determined GC was not needed and that there is a better way. Perhaps we might come to the same conclusion about function curry.

Personally I had issues with C from my day one, back in 1983, so I welcome 'Result'. Certainly one does not need Iterators or Futures.

I never felt the need for a "monad". Mostly because having read many definitions of "monad" over the years I never found one that meant anything to me.

3 Likes

For me it's Java 7 -> 8, before Java 8, you can make closure with Interfaces and anonymous inner classes, but it's extremely verbose. In Java 8, Oracle added lambda expression and lazy streams for collections.

Basically the main thing making currying more difficult in Rust is the fact that one has to be very explicit about the capturing and calling modes of a closure, since Rust revolves about the by_ref / by_mut_ref / by_(owned_)value choice being given to the programmer.

If you restrict yourself to Copy + 'static types (which, in a way, is what a GC allows a language to emulate), then you can just create move closures everywhere, and assume everything is impl 'static + Copy + Fn(...) -> _, reaching something very close to garbage-collected functional languages.

For instance, OCaml's

let sum =
    List.fold_left
        (fun acc -> fun x -> acc + x) // can be shortened to: (+)
        0
in
print_int (sum [3; 4; 5; 6])

can be written in Rust as:

fn main ()
{
    let sum =
        List::fold_left
            (fun!(acc => x => acc + x))
            (0)
    ;
    print_int (sum (list![3; 4; 5; 6]))
}

impl<T : Copy> List<T> {
    /// fun![
    ///     (fun![(Acc) -> (T) -> Acc]) -> (Acc) -> (List<T>) -> Acc
    /// ]
    fn fold_left<Acc : Copy> (
        folder: fun![(Acc) -> (T) -> Acc],
    ) -> fun![(Acc) -> (List<T>) -> Acc]
    {
        fun!(acc => list => {
            // ...
        })
    }
}
  • Playground

    • (it currently requires the unstable unboxed_closures feature, to be able to have the f (arg) (arg2) call sugar. This is nevertheless doable in stable Rust with a custom trait, but at the cost of that sugar: one would need to write f .a(arg1) .a(arg2)...)

Otherwise one needs to explicit when the closures may "just" be FnMut or Fn(): Playground whith the Copy bounds removed.

2 Likes

So, this got a little derailed into talking about monads, but I think the original post was pretty interesting and wanted to share my thoughts on the benefits of currying.

One way to implement currying is to use impl Trait to return a closure with one less function parameter.

I did something like this for my pratt parser so that I could parse unary expressions with iteration instead of recursion. If I see some C code like (int)(int)(int)x, then instead of doing something like this:

fn unary_expr(&mut self) -> Expr {
    if let Some(cast) = self.parenthesized_type() {
        return Expr::Cast(cast, self.unary_expr());
    }
    self.primary_expr()
}

I create an explicit stack (on the heap - why are programmers so bad at naming things?) which lets me pop things off in a loop:

let mut ops = Vec::new();
while let Some(op) = self.match_prefix_op() {
    ops.push(unary);
}
let mut expr = self.primary_expr();
while let Some(op) = ops.pop() {
    expr = op(expr);
}

This wouldn't be possible without closures and currying since I need to make every op take only one argument, see match_prefix_op for an example of what that looks like.

Okay, the monad tangent has become its own thread.

3 Likes

That the thing about Rust: sometimes it takes a little more syntax, but the syntax is really concise without being an obfuscation contest (I'm looking at you, idiomatic Python).

The biggest problem I see with currying in Rust is lifetime and ownership. Haskell etc. can get away with 'syntaxified' currying because they have a runtime GC. In Rust, what would the lifetime of the arguments be (i.e. is the curried function a Fn, a FnMut or a FnOnce?).

1 Like

We'd necessarily promote curried functions from Fn to/from FnMut to FnOnce when partial application passed &mut or non-Copy values, respectively. It'd screw up Iterator::map all the time, even when passing an Arc<T>, although increased Borrow<T> usage helps.

1 Like