Hacker News Reader

Comment by mickronome | Hacker News Reader

I'm quite of my depth here, and while I can sort of understand the recursive construction of new types, it seems as if the type checker should be able to almost trivialy 'shortcut' the recursion unless the return type is unconstrained in some sense that it can be a recursive type with some type arguments.

Most likely there is something obvious I'm missing as I don't know a lot about rust, but unless the compiler isn't doing what is essentially a type level equivalent of tail call elimination, which it almost certainly does, finding the type of that function should be trivial unless the return type can become recursive with unbounded depth.

View on HN

> unless the compiler isn't doing what is essentially a type level equivalent of tail call elimination

It doesn't, why would it? That's a pretty niche thing to have.

> finding the type of that function should be trivial unless the return type can become recursive with unbounded depth.

The return type is recursive with unbounded depth. The typechecker doesn't know the value of `n`, so to it this returns an infinitely recursive type.

Closures are statically dispatched. If you want something like this to work, you should box them as a trait object so that they get dynamically dispatched.

This example code must be monomorphized at compile time, meaning that each closure will have a different representation. "Tail call optimization at the type level" is not possible with this compilation model.

(The problem is solved by using a trait object to dynamically dispatch the inner call. https://play.rust-lang.org/?gist=0d3c0a5f1291eb34ba61bd39449...)

From memory I solved it using more CPS and currying. Well manually currying with functions like curry1, curry2, etc...

Although I'm pretty sure you can overload the Fn* traits to implement currying in Rust. (Fn traits are unstable). Which is neat.

    // Something like this:
    impl<F, A, B, R> (FnOnce(A) -> Curry<F, A, B>)  for  F
        where F: FnOnce(A, B) -> R,
    { ... }

    // and
    impl<F, A, B, R> (FnOnce(B) -> R) for Curry<F, A, B>
        where F: FnOnce(A, B) -> R

I think I got it working... but you would need some work for more arguments. (And it worked different on different versions of rust-nightly :/)

Reply on news.ycombinator.com