haskell - 为什么这个函数会导致编译时溢出？

Question

struct Z;
struct S<N>(N);

struct MinHelper<N1, N2>(N1, N2);

trait Min {
    type Val;
}

impl<N1> Min for MinHelper<N1, Z> {
    type Val = Z;
}

impl<N2> Min for MinHelper<Z, S<N2>> {
    type Val = Z;
}

impl<N1, N2> Min for MinHelper<S<N1>, S<N2>>
where
    MinHelper<N1, N2>: Min,
{
    type Val = S<<MinHelper<N1, N2> as Min>::Val>;
}

fn min<N1, N2>(_1: N1, _2: N2) -> <MinHelper<N1, N2> as Min>::Val {
    unimplemented!()
}

Rust playground

看来问题出在函数的类型检查上。如果我像这样使用 Min，它会表现良好:

let x: <MinHelper<S<Z>, S<S<Z>>> as Min>::Val = S(Z);

我想实现的是 Haskell 中的类型族:

{-# LANGUAGE TypeFamilies #-}

data Z;
data S n;

type family Min (a :: *) (b :: *) :: *;
type instance Min a     Z     = Z
type instance Min Z     b     = Z
type instance Min (S a) (S b) = S (Min a b)

min :: a -> b -> Min a b
min = undefined

Answer 1

我找到了一个解决方案:

struct Z;
struct S<N>(N);

struct Helper;

trait Min<N1, N2> {
    type Val;
}

impl<N1> Min<N1, Z> for Helper {
    type Val = Z;
}

impl<N2> Min<Z, S<N2>> for Helper {
    type Val = Z;
}

impl<N1, N2> Min<S<N1>, S<N2>> for Helper
where
    Helper: Min<N1, N2>,
{
    type Val = S<<Helper as Min<N1, N2>>::Val>;
}

fn min<N1, N2>(_a: N1, _b: N2) -> <Helper as Min<N1, N2>>::Val
where
    Helper: Min<N1, N2>,
{
    unimplemented!()
}

fn main() {
    min(S(Z), S(S(Z)));
}

Rust playground

我还没有找到详细的解释。但@LambdaFairy 的评论听起来很合理。