[Rust] Lagrange 補間

データ点が与えられたとき, そこから Lagrange 補間多項式をクロージャとして返すサブルーチン. データはクロージャが所有権を持つようにムーブする.

パターン 1: std::iter::Sum を要求する.

use std::iter::Sum;
use std::ops::{Sub, Mul, Div};

fn lagrange_interpolation<T>(xs: Vec<T>, fs: Vec<T>) -> impl Fn(T) -> T
    where T: Copy + PartialEq + Sum + Sub<Output=T> + Mul<Output=T> + Div<Output=T>
{
    move | x: T | -> T {
        xs.iter().zip(fs.iter())
            .map(|(xi, &fi)|
                 xs.iter()
                     .filter(|&xk| xk != xi)
                     .fold(fi, |acc, &xk| acc * (x-xk)/(*xi-xk)))
            .sum::<T>()
    }
}

パターン 2: std::default::Default を要求して和を自前で実装. (意味的には num クレートの num::Zero トレイトを用いるべきだけど std だけで完結させたかったので)

use std::default::Default;
use std::ops::{AddAssign, Sub, Mul, Div};

fn lagrange_interpolation<T>(xs: Vec<T>, fs: Vec<T>) -> impl Fn(T) -> T
    where T: Copy + PartialEq + Default + AddAssign + Sub<Output=T> + Mul<Output=T> + Div<Output=T>
{
    move | x: T | -> T {
        let mut f = T::default();

        for (xi, &fi) in xs.iter().zip(fs.iter()) {
            f += xs.iter()
                .filter(|&xk| xk != xi)
                .fold(fi, |acc, &xk| acc * (x-xk)/(*xi-xk));
        }

        f
    }
}