How to filter union type?

user_5257860 0
Viewed 128

I have a union type like:

type Animal = "cat" | "dog" | "rabbit"

And I have a union type of all combinations between these animals:

type PairsMap = {
    [K1 in Animal]: {
        [K2 in Animal]: K1 extends K2 ? never : [K1, K2]
    }
}

type Values<T> = T[keyof T]
type Pairs = Values<Values<PairsMap>> 
// type Pairs = ["dog", "cat"] | ["rabbit", "cat"] | ["cat", "dog"] | ["rabbit", "dog"] | ["cat", "rabbit"] | ["dog", "rabbit"]

The question is - how can I remove all pairs which are "inversed" duplicates? (e.g. remove dog-cat if there is a cat-dog).

TS Playground link

union-types typescript tuples
1 Answers

Unfortunately I did not came up with simple solution. If anybody know simpler solution - I'm all ears.

I have rewritten PairsMap implementation. I think it is more generic but I might be wrong, so you can use any implementation you like. Every one has his own style, right ?:D

// credits goes to https://github.com/microsoft/TypeScript/issues/31751#issuecomment-498526919
type IsNever<T> = [T] extends [never] ? true : false;

type PairsMap<
    Union extends string,
    Used extends string = never,
    Cache extends string[] = never
    > =
    IsNever<Union> extends true ? Cache : {
        [Prop in Union]: PairsMap<Exclude<Union, Prop>, Prop, [Prop, Used]>
    }[Union]

type PartialPermutations = PairsMap<Animal>

Next, We need to filter the union. Since we can't iterate over the union of tuples we need to convert it to tuple.

// credits goes to https://stackoverflow.com/a/50375286
type UnionToIntersection<U> = (U extends any ? (k: U) => void : never) extends (
    k: infer I
) => void
    ? I
    : never;

// credits goes to https://github.com/microsoft/TypeScript/issues/13298#issuecomment-468114901
type UnionToOvlds<U> = UnionToIntersection<
    U extends any ? (f: U) => void : never
>;

// credits goes to https://github.com/microsoft/TypeScript/issues/13298#issuecomment-468114901
type PopUnion<U> = UnionToOvlds<U> extends (a: infer A) => void ? A : never;

// credit goes to https://stackoverflow.com/questions/53953814/typescript-check-if-a-type-is-a-union#comment-94748994
type IsUnion<T> = [T] extends [UnionToIntersection<T>] ? false : true;

type UnionToArray<T, A extends unknown[] = []> = IsUnion<T> extends true
    ? UnionToArray<Exclude<T, PopUnion<T>>, [PopUnion<T>, ...A]>
    : [T, ...A];

Similar question

As you might have noticed there are links with explanation above each type utility.

Article

After we had converted it to the inerrable data structure (tuple), we can actually iterate over it:

type Inverse<T> = T extends [infer Fst, infer Scd] ? [Scd, Fst] : never

type MapPredicate<Original, Tuple> = Inverse<Tuple> extends Original ? never : Tuple

type Filter<
    Current extends Array<any>,
    Result extends Array<any> = []
    > = Current extends []
    ? []
    : Current extends [infer H]
    ? [...Result, MapPredicate<Result[number], H>][number]
    : Current extends [infer Head, ...infer Tail]
    ? Filter<[...Tail], [...Result, MapPredicate<Result[number], Head>]>
    : Readonly<Result>;

Here, in my blog, you can find more explanation how it works

Here you have pure js to understand what is going on here. Please treat null as never. Like I said - it is pseudocode, in typescript you should not treat never as null

const predicate = (result, head) => {
    const [fst, scd] = head
    // pseudocode, includes works with primitives
    if (result.includes([scd, fst])) {
        return null
    }
    return head
}

const filter = (current, result = []) => {
    if (current.length === 0) {
        return []
    }

    const [head, ...tail] = current;

    return filter(tail, [...result, predicate(result, head)])
}

Full example:

type Animal = "cat" | "dog" | "rabbit"

// credits goes to https://stackoverflow.com/a/50375286
type UnionToIntersection<U> = (U extends any ? (k: U) => void : never) extends (
    k: infer I
) => void
    ? I
    : never;

// credits goes to https://github.com/microsoft/TypeScript/issues/13298#issuecomment-468114901
type UnionToOvlds<U> = UnionToIntersection<
    U extends any ? (f: U) => void : never
>;

// credits goes to https://github.com/microsoft/TypeScript/issues/13298#issuecomment-468114901
type PopUnion<U> = UnionToOvlds<U> extends (a: infer A) => void ? A : never;

// credit goes to https://stackoverflow.com/questions/53953814/typescript-check-if-a-type-is-a-union#comment-94748994
type IsUnion<T> = [T] extends [UnionToIntersection<T>] ? false : true;

type UnionToArray<T, A extends unknown[] = []> = IsUnion<T> extends true
    ? UnionToArray<Exclude<T, PopUnion<T>>, [PopUnion<T>, ...A]>
    : [T, ...A];

type IsNever<T> = [T] extends [never] ? true : false;

type PairsMap<
    Union extends string,
    Used extends string = never,
    Cache extends string[] = never
    > =
    IsNever<Union> extends true ? Cache : {
        [Prop in Union]: PairsMap<Exclude<Union, Prop>, Prop, [Prop, Used]>
    }[Union]

type PartialPermutations = PairsMap<Animal>

type Inverse<T> = T extends [infer Fst, infer Scd] ? [Scd, Fst] : never

type MapPredicate<Original, Tuple> = Inverse<Tuple> extends Original ? never : Tuple

type Filter<
    Current extends Array<any>,
    Result extends Array<any> = []
    > = Current extends []
    ? []
    : Current extends [infer H]
    ? [...Result, MapPredicate<Result[number], H>][number]
    : Current extends [infer Head, ...infer Tail]
    ? Filter<[...Tail], [...Result, MapPredicate<Result[number], Head>]>
    : Readonly<Result>;

type Result = Filter<UnionToArray<PartialPermutations>>; // ["dog", "cat"] | ["rabbit", "dog"] | ["rabbit", "cat"]

Playground

user_84952540
Related