Creating a data structure that consists of pairs of elements, inspired by the alignment of domino bricks, using TypeScript syntax

Question

Creating a data structure that consists of pairs of elements, inspired by the alignment of domino bricks, using TypeScript syntax

My goal is to establish a type alias in TypeScript that allows all values which are arrays of Domino pairs, where each pair connects like domino bricks: Pair<A,B> connects with Pair<C,D> only if B = C.

For example:

const chain1: DominoChain = [ ["A", "B"], ["B", "C"], ["C", "D"], ["D", "E"] ] // Accepted
const chain2: DominoChain = [ [3, 4], [4, 2], [2, 1] ] // Accepted
const chain3: DominoChain = [ [3, null], [null, {}], [{}, undefined] ] // Accepted
const chain4: DominoChain = [ [1, 2] ] // Accepted
const chain5: DominoChain = [ ] // Accepted
const chain6: DominoChain = [ [1, 2], [3, 4] ] // Not accepted due to 2 != 3. Compiler error expected.

I have made some attempts but it's not functioning as intended:

type Domino<A,B> = [A, B]

type DominoChain<A = any, B = any> = [Domino<A, B>] | [Domino<A, B>, ...DominoChain<B, any>]

I am unsure how to correctly enforce the matching constraint between two Domino pairs and I suspect there may be an issue with the recursive aspect.

typescript types

Answer 1

Answer №1

To enforce constraints in the typescript type system, generic arguments need to be validated.

A type utility can be created to validate input, as demonstrated in the following example:

type Last<T> = T extends [...infer _, infer LastElem] ? LastElem : never

type Head<T> = T extends [infer First, ...infer _] ? First : never

type IsChainable<Current, Next> =
  (Last<Current> extends Head<Next>
    ? (Head<Next> extends Last<Current>
      ? true
      : false)
    : false)

type DominoChain<List extends any[], Result extends any[] = []> =
  (List extends []
    ? Result
    : (List extends [infer First]
      ? (IsChainable<Last<Result>, First> extends true
        ? [...Result, First]
        : never)
      : (List extends [infer First, ...infer Rest]
        ? (Result extends []
          ? DominoChain<Rest, [...Result, First]>
          : (IsChainable<First, Head<Rest>> extends true
            ? DominoChain<Rest, [...Result, First]>
            : never))
        : never
      )
    )
  )

type Test1 = DominoChain<[["A", "B"], ["B", "C"], ["C", "D"], ["D", "E"]]>
type Test2 = DominoChain<[[3, 4], [4, 2], [2, 1]]>
type Test3 = DominoChain<[[3, null], [null, {}], [{}, undefined]]>
type Test4 = DominoChain<[[1, 2]]> // ok 
type Test5 = DominoChain<[]> // ok

type Test6 = DominoChain<[[1, 2], [3, 4],]> // never

const domino = <
  Elem extends string,
  Tuple extends Elem[],
  List extends [...Tuple][]
>(list: [...List] & DominoChain<[...List]>) => list

domino([["A", "B"], ["B", "C"], ["C", "D"], ["D", "E"]]) // ok
domino([[1, 2], [3, 4],]) // error

Playground

Last - retrieves the last element in a tuple Head - retrieves the first element in a tuple

IsChainable - verifies if the last element in the current tuple extends the first element of the next tuple, and vice versa.

DominoChain - iterates through a list of tuples and applies IsChainable on each tuple.

Although the code may seem extensive, it is actually straightforward once understood.

Answer 2

To enforce constraints in the typescript type system, generic arguments need to be validated.

A type utility can be created to validate input, as demonstrated in the following example:

type Last<T> = T extends [...infer _, infer LastElem] ? LastElem : never

type Head<T> = T extends [infer First, ...infer _] ? First : never

type IsChainable<Current, Next> =
  (Last<Current> extends Head<Next>
    ? (Head<Next> extends Last<Current>
      ? true
      : false)
    : false)

type DominoChain<List extends any[], Result extends any[] = []> =
  (List extends []
    ? Result
    : (List extends [infer First]
      ? (IsChainable<Last<Result>, First> extends true
        ? [...Result, First]
        : never)
      : (List extends [infer First, ...infer Rest]
        ? (Result extends []
          ? DominoChain<Rest, [...Result, First]>
          : (IsChainable<First, Head<Rest>> extends true
            ? DominoChain<Rest, [...Result, First]>
            : never))
        : never
      )
    )
  )

type Test1 = DominoChain<[["A", "B"], ["B", "C"], ["C", "D"], ["D", "E"]]>
type Test2 = DominoChain<[[3, 4], [4, 2], [2, 1]]>
type Test3 = DominoChain<[[3, null], [null, {}], [{}, undefined]]>
type Test4 = DominoChain<[[1, 2]]> // ok 
type Test5 = DominoChain<[]> // ok

type Test6 = DominoChain<[[1, 2], [3, 4],]> // never

const domino = <
  Elem extends string,
  Tuple extends Elem[],
  List extends [...Tuple][]
>(list: [...List] & DominoChain<[...List]>) => list

domino([["A", "B"], ["B", "C"], ["C", "D"], ["D", "E"]]) // ok
domino([[1, 2], [3, 4],]) // error

Playground

Last - retrieves the last element in a tuple Head - retrieves the first element in a tuple

IsChainable - verifies if the last element in the current tuple extends the first element of the next tuple, and vice versa.

DominoChain - iterates through a list of tuples and applies IsChainable on each tuple.

Although the code may seem extensive, it is actually straightforward once understood.

Answer 3

Answer №2

Upon receiving a clever hint from @captain-yossarian regarding the necessity of incorporating an extra function or constant for successful type checking, I devised the following solution:

// Defining the structure of a domino brick
type Domino<A = any, B = any> = readonly [A,B]

// Defining an array of matching domino bricks
type DominoChain<T extends readonly Domino[], FIRST = any> =
    T extends readonly [Domino<any, infer A>, ... infer REST]
        ? (REST extends Domino[] ? readonly [Domino<FIRST, A>, ...DominoChain<REST, A>] : never)
        : readonly []

// Preventing undesired type inference
type NoInfer<T> = [T][T extends any ? 0 : never];

// Using this function to compare an inferred type with 
// the definition of DominoChain
function dominoTest<T extends readonly Domino[]>(domino: T & DominoChain<T>): NoInfer<T> {
    return domino
}

dominoTest(<const>[ ["A","B"], ["B","C"], ["C","D"], ["D","E"] ]) // OK
dominoTest(<const>[ [3, 4], [4, 2], [2, 1] ]) // OK
dominoTest(<const>[ [3, null], [null, {}], [{}, undefined] ]) // OK
dominoTest(<const>[ [1, 2] ]) // OK
dominoTest(<const>[ ]) // OK
dominoTest(<const>[ [1, 2], [3, 4] ]) // error
// TS2345: Argument of type 
// 'readonly [readonly [1, 2], readonly [3, 4]]' 
// is not assignable to parameter of type 
// 'readonly [Domino<any, 2>, Domino<2, 4>]'.   
// Type at position 1 in source is not compatible with type at position 1 in target.     
// Type '3' is not assignable to type '2'.

Update: Enhanced the initial code snippet

Answer 4

Upon receiving a clever hint from @captain-yossarian regarding the necessity of incorporating an extra function or constant for successful type checking, I devised the following solution:

// Defining the structure of a domino brick
type Domino<A = any, B = any> = readonly [A,B]

// Defining an array of matching domino bricks
type DominoChain<T extends readonly Domino[], FIRST = any> =
    T extends readonly [Domino<any, infer A>, ... infer REST]
        ? (REST extends Domino[] ? readonly [Domino<FIRST, A>, ...DominoChain<REST, A>] : never)
        : readonly []

// Preventing undesired type inference
type NoInfer<T> = [T][T extends any ? 0 : never];

// Using this function to compare an inferred type with 
// the definition of DominoChain
function dominoTest<T extends readonly Domino[]>(domino: T & DominoChain<T>): NoInfer<T> {
    return domino
}

dominoTest(<const>[ ["A","B"], ["B","C"], ["C","D"], ["D","E"] ]) // OK
dominoTest(<const>[ [3, 4], [4, 2], [2, 1] ]) // OK
dominoTest(<const>[ [3, null], [null, {}], [{}, undefined] ]) // OK
dominoTest(<const>[ [1, 2] ]) // OK
dominoTest(<const>[ ]) // OK
dominoTest(<const>[ [1, 2], [3, 4] ]) // error
// TS2345: Argument of type 
// 'readonly [readonly [1, 2], readonly [3, 4]]' 
// is not assignable to parameter of type 
// 'readonly [Domino<any, 2>, Domino<2, 4>]'.   
// Type at position 1 in source is not compatible with type at position 1 in target.     
// Type '3' is not assignable to type '2'.

Update: Enhanced the initial code snippet

Creating a data structure that consists of pairs of elements, inspired by the alignment of domino bricks, using TypeScript syntax

Answer №1

Answer №2

Similar questions

Learn how to resubscribe and reconnect to a WebSocket using TypeScript

Error TS2394: Function implementation does not match overload signature in Typescript

Instructions on invoking a function from another Material UI TypeScript component using React

Tips on filtering an array in a JSON response based on certain conditions in Angular 7

Reattempting a Promise in Typescript when encountering an error

Contrast the differences between arrays and inserting data into specific index positions

An effective method to utilize .map and .reduce for object manipulation resulting in a newly modified map

Issue with updating initial state that is null in Redux Toolkit

Could it be possible for a Firestore onUpdate trigger's change parameter, specifically change.after.data() and change.before.data(), to become null or undefined?

Retrieve all services within a Fargate Cluster using AWS CDK

Experimenting with a VSCode extension that requires the act of launching a folder/workspace

Issue with React not displaying JSX when onClick Button is triggered

The noUnusedLocal rule in the Typescript tsconfig is not being followed as expected

Posting an array as form data in Angular Typescript: A step-by-step guide

Transform a string into a class in Typescript/Angular

Tips for showcasing the information from a JSON document in React

How come TypeScript tuples support the array.push method?

Example TypeScript code: Use the following function in Angular 5 to calculate the total by summing up the subtotals. This function multiplies the price by the quantity

Error message: While running in JEST, the airtable code encountered a TypeError stating that it cannot read the 'bind' property of an

Implementing Angular 2 reactive forms checkbox validation in an Ionic application