Type level Fibonacci sequence results in “overflow evaluating the requirement”

help
1

I'm writing a type level Fibonacci sequence.

I've already written a type level addition, which works fine.

Basically, every number is represented as Inc<Inc<...<Zero>...>>. There is a trait Add, then structure Bop<Left, Right> (binary operation) implements the Add trait. The usage is that <Bop<Inc<Inc<Inc<Zero>>>, Inc<Inc<Zero>>> as Add>::Get will be Inc<Inc<Inc<Inc<Inc<Zero>>>>>, that is 3 + 2 = 5.

Then I write a Fibonacci sequence based on the addition:

// 0 1 2 3 4 5 6 7
// 0 1 1 2 3 5 8 13
// usage: <Inc<Inc<Inc<Zero>>> as Fib>::Get should be the third fib number,
// i.e. 2, or Inc<Inc<Zero>>
trait Fib { type Get; }
impl Fib for Zero { type Get = Zero; }
impl Fib for One { type Get = One; }

impl<T> Fib for Inc<Inc<T>>
    where T: Fib,
          Inc<T>: Fib,
          Bop<<T as Fib>::Get, <Inc<T> as Fib>::Get>: Add,
{
    type Get = <Bop<
          <T as Fib>::Get, <Inc<T> as Fib>::Get
        > as Add>::Get;
}

But the compiler has trouble figuring out the impl<T> Fib for Uop<Inc<Inc<T>>> part, it complains:

error[E0275]: overflow evaluating the requirement `Inc<_>: Fib`

Here is a complete example in Rust playground:

Playground

What's the reason of the error? How to resolve it?

2

The compiler will complain because you could possibly be going on forever, and it doesn't know if your type will terminate, or is infinite. Due to this, Rust has a recursion limit, and if you exceed it, compilation will fail. This is to guarantee that compilation will end. You will need to either rethink how you do this or it may not be possible.

3

Thanks to your question I looked into this a bit, but I'm certainly not an expert, and I don't have a real answer.
As far as I understand this kind of type inference is done in a rather ad-hoc and unsatisfying way in the current implementation, and there is a effort under way to clean this up under the heading "chalk" / "chalkification" (search the issues).
My only practical suggestion would be to try (syntactically) simpler functions first, e.g. doubling or halving, multiplication etc. and see how far you get.

4

Just out of curiosity, if I had a really long trait/associated type/generic variable, say for some reason (This is ridiculous and it should never happen) I had 100 'layers' of constraints etc. how far would I have to go for it to complain?
Remember, just out of curiosity

5

I'm not sure, how far it can go can be increased by increasing the recursion limit though.

1 Like
6

Compiles fine with some adjustments:

7

Kind of off-topic, but FWIW... There is a closed-form expression for the Fibonacci sequence using the golden ratio.

playground