CODEWITHSUNDEEP
haskellrust
QuarticCat
QuarticCat

Reputation: 1526

Why does this function cause compile-time overflow?

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

It seems that the problem is in the type checking of functions. If I use Min like this, it behaves well:

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

What I want to implement is type families in 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

Upvotes: 3

Views: 204

Answers (1)

QuarticCat
QuarticCat

Reputation: 1526

I found a solution for this:

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

I still haven't found a detailed explanation. But @LambdaFairy 's comment sounds reasonable.

Upvotes: 1

Related Questions