使用SKI组合子S I I实现递归时Rust报错的原因与解决办法

当调用s(i,i,i)时，Rust的类型推导会陷入无限递归的类型依赖，导致编译器无法计算出合法的类型大小：

1. 从S组合子的签名fn s<Z,Y,X>(x: fn(Z)->fn(Y)->X, y: fn(Z)->Y, z: Z) -> X出发，三个参数都是i（类型为fn<T>(T)->T），需要匹配各自的类型约束：
   • 第一个i作为x，要求其输入类型Z等于输出类型fn(Y)->X，即Z = fn(Y)->X
   • 第二个i作为y，要求其输入类型Z等于输出类型Y，即Z = Y
   • 第三个i作为z，要求其类型就是Z，即Z本身是fn<T>(T)->T这种函数类型
2. 将Z=Y代入第一个约束，得到Y = fn(Y)->X，进一步推导X = Y(Y)——这形成了循环：Y的类型依赖于自身作为参数的调用结果，导致类型大小无限递归。Rust要求所有类型在编译时必须有确定的有限大小，因此触发错误。

1. 使用Box包装递归函数类型 #

通过Box<dyn Fn(...) -> ...>将递归的函数类型转为固定大小的胖指针，打破无限大小递归：

fn s_dyn<Z: Copy, Y, X>(
    x: impl Fn(Z) -> impl Fn(Y) -> X,
    y: impl Fn(Z) -> Y,
    z: Z,
) -> X {
    x(z)(y(z))
}

fn i<X>(x: X) -> X {
    x
}

fn main() {
    // 定义递归的boxed函数类型
    type RecursiveFn = Box<dyn Fn(RecursiveFn) -> RecursiveFn>;
    let boxed_i: RecursiveFn = Box::new(i);
    
    // 调用s_dyn，此时类型大小固定，可通过编译
    let _result = s_dyn(|z| |y| z(y), |z| z, boxed_i);
}

这里修改了S组合子的签名，使其接受impl Fn而非裸函数指针，以支持trait对象。

2. 使用 trait 对象抽象函数行为 #

定义通用的函数trait，用动态分发的方式规避类型递归：

trait Callable<T> {
    type Output;
    fn call(self, arg: T) -> Self::Output;
}

impl<T, O, F: Fn(T) -> O> Callable<T> for F {
    type Output = O;
    fn call(self, arg: T) -> O {
        self(arg)
    }
}

fn s<Z: Copy, Y, X>(
    x: impl Callable<Z, Output = impl Callable<Y, Output = X>>,
    y: impl Callable<Z, Output = Y>,
    z: Z,
) -> X {
    x.call(z).call(y.call(z))
}

fn i<X>(x: X) -> X {
    x
}

fn main() {
    let i_trait: Box<dyn Callable<Box<dyn Callable<(), Output = ()>>, Output = Box<dyn Callable<(), Output = ()>>>> = Box::new(i);
    let _ = s(|z| Box::new(|y| z.call(y)), |z| z, i_trait);
}

这种方式通过trait抽象函数调用逻辑，用Box包装trait对象来固定类型大小。

3. 避免直接构造无限递归的调用 #

如果不需要严格的SKI组合子调用形式，可以手动拆解S I I x = x(x)的逻辑，直接使用x(x)并配合指针包装：

fn main() {
    type RecFn = Box<dyn Fn(RecFn) -> ()>;
    let f: RecFn = Box::new(|x| {
        // 这里实现x(x)的逻辑
    });
    f(f);
}

内容的提问来源于stack exchange，提问作者Doubtful