// taken from https://play.rust-lang.org/?gist=cdf47bdfa00043671cdd574ed2380e66
// article to read https://beachape.com/blog/2017/03/12/gentle-intro-to-type-level-recursion-in-Rust-from-zero-to-frunk-hlist-sculpting/

trait ScalarProduct<A> {
    fn scalar_product(&self, second: &A) -> i64;
}

struct Nil;

impl ScalarProduct<Nil> for Nil {
    fn scalar_product(&self, _: &Nil) -> i64 {
        0
    }
}

struct Cons<A> {
    head: i64,
    tail: A,
}

impl<A> ScalarProduct<Cons<A>> for Cons<A>
    where A: ScalarProduct<A>
{
    fn scalar_product(&self, second: &Self) -> i64 {
        self.head * second.head + self.tail.scalar_product(&second.tail)
    }
}

fn main() {
    let n = 15;
    println!("{}", sp(n, 0, Nil, Nil));
}

fn sp<A>(n: i64, i: i64, first: A, second: A) -> i64
    where A: ScalarProduct<A>
{
    if n == 0 {
        first.scalar_product(&second)
    } else {
        sp(
            n - 1, i + 1,
            Cons { head: 2 * i + 1, tail: first },
            Cons { head: i * i, tail: second }
        )
    }
}