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

Nested self-referencing in Typescript involves a structure where

Angular2 Cache: Enhance Your Application's Performance

Retrieve the user information from Auth0 within the NestJS application

Do const generics similar to Rust exist in TypeScript?

Utilizing React Higher Order Components with TypeScript: can be initialized with a varied subtype of restriction

Having trouble opening a JPEG file that was generated using the Writefile Api in Ionic-Cordova

Do Angular 2 component getters get reevaluated with each update?

Can a generic type be utilized to instantiate an object?

Can someone provide a description for a field within typedoc documentation?

Removing empty options from a select dropdown in Angular 9

How to Extract the Specific Parameter Type from a Function in Typescript

Updating the page dynamically in React/Redux by making API calls based on user submissions

Is there a workaround in TypeScript to add extra details to a route?

Instructions for including a class are ineffective

Using Angular CLI with ES6 instead of TypeScript for your development needs can offer a

Issues with Angular 4 Rxjs subject subscription functionality

Displaying a collection of objects in HTML by iterating through an array

What is the best way to execute a function from a parent element within the child element?

Tips for dynamically implementing a pipe in Angular 5

Unable to modify the border-radius property of Material UI DatePicker