ประเภท TypeScript สำหรับอาร์เรย์ที่สับอย่างสมบูรณ์

คำถามนี้เพื่อความสนุกสนานเท่านั้น ไม่ใช่สิ่งที่น่าจะต้องใช้ในโลกจริง แต่รู้สึกว่าไม่ถูกต้องที่จะเอาไปลงใน Code Golf เพราะมันเฉพาะเจาะจงมาก

สมมติว่าฉันมี JavaScript:

function shuffle(array) {
    if (array.length === 0 || array.length === 1) {
        return array;
    }

    const rest = array.slice();
    const middle = rest.splice(Math.ceil(array.length / 2), 1)[0];
    const first = rest.shift();

    return [first, middle, ...shuffle(rest)];
}

const array = [1, 2, 3, 4, 5, 6, 7, 8];
const shuffled = shuffle(array); // [ 1, 5, 2, 6, 3, 7, 4, 8 ]
console.log(shuffled);

ฟังก์ชันนี้โดยพื้นฐานแล้วจะสับ array เหมือนกับเป็นสำรับไพ่ที่สับอย่างสมบูรณ์ เริ่มจากไพ่บนสุด จากนั้นไพ่กลาง จากนั้นไพ่ที่สอง แล้วไพ่ที่อยู่หลังไพ่กลาง เป็นต้น อีกวิธีหนึ่งที่จะทำได้คือการแบ่ง array ออกเป็นสองส่วน แล้วรวมสองส่วนเข้าด้วยกันแบบ zip จากนั้นทำให้ array แบนลง

เป็นไปได้ไหมที่จะสร้าง type ใน TypeScript ที่จะรู้วิธีการเปลี่ยน array ให้เป็น shuffled?

นี่คือความพยายามที่ดีที่สุดของฉัน

type Shuffle<T extends readonly [...any[]]> = 
    T['length'] extends 0 | 1 ? T : 
    T extends [...infer A, ...infer B]
        ? A['length'] extends B['length'] 
            ? [A, B] extends [[infer AH, ...infer AR], [infer BH, ...infer BR]] 
                ? [AH, BH, ...Shuffle<[...AR, ...BR]>]
                : never
            : never
        : never;

function shuffle<T extends readonly any[]>(array: T): Shuffle<T> {
    if (array.length === 0 || array.length === 1) {
        return array.slice();
    }

    const rest = array.slice();
    const middle = rest.splice(Math.ceil((array.length - 1) / 2), 1)[0];
    const first = rest.shift();

    return [first, middle, ...shuffle(rest)];
}

const array = [1, 2, 3, 4, 5, 6, 7, 8] as const;
const shuffled = shuffle(array);

type Shuffled = typeof shuffled; // never

console.log(shuffle(array));

สนามเด็กเล่น TypeScript

ชัดเจนว่าจุดสำคัญคือการหาวิธีแบ่งอาเรย์ครึ่งหนึ่ง

บางทีฉันอาจจะสร้างอาร์เรย์สองตัวแบบเรียกซ้ำได้ โดยแต่ละครั้งดึงสมาชิกออกจากจุดเริ่มต้นและจุดสิ้นสุด และวางมันในลำดับที่ถูกต้อง.... (เมื่อฉันมีไอเดียนี้แล้ว ฉันก็แก้ปัญหาได้ ดังนั้นฉันจะโพสต์คำตอบของฉัน)

คำตอบ #1

ประเภทเชิงเงื่อนซ้อนแบบเรียกตัวเองและประเภททูเปิลแบบแปรผันทำให้สามารถทำได้ แต่ก็ยังค่อนข้างยุ่งยาก ในการทำการจัดการประเภทแบบที่คุณพูดถึง

ฉันคิดว่าสิ่งต่อไปนี้เป็นแนวทางทั่วไปเดียวกับที่คุณใช้ในคำตอบของคุณ แม้ว่ารายละเอียดที่แน่นอนจะแตกต่างกันเล็กน้อย ฉันพยายามทำให้ประเภทต่าง ๆ เป็นแบบ "เรียบง่าย" ที่สุดเท่าที่ฉันทำได้ แต่อย่างไรก็ตามฉันจะปล่อยให้ผู้อื่นตัดสินว่าความพยายามนั้นประสบความสำเร็จมากน้อยแค่ไหน:

ฉันจะกำหนดฟังก์ชันประเภทที่เรียกว่า FirstHalf<T> ซึ่งจะส่งกลับครึ่งแรกของทูเพิล T หาก T มีจำนวนสมาชิกเป็นเลขคี่ FirstHalf<T> จะรวมถึงสมาชิกตรงกลางด้วย ดังนั้น FirstHalf<[1,2,3,4]> ควรเป็น [1,2] และ FirstHalf<[1,2,3,4,5]> ควรเป็น [1,2,3]:

type FirstHalf<T extends any[]> = T extends [infer F, ...infer M, any] ?
    [F, ...FirstHalf<M>] : T

และจากนั้น LastHalf<T> จะคืนค่าเศษครึ่งหลังของชนิดทูเพิล T โดยการสร้างส่วนเติมเต็มของ FirstHalf<T> ซึ่งหมายความว่าถ้ามีจำนวนสมาชิกเป็นเลขคี่ใน T สมาชิกตรงกลางจะ ไม่ อยู่ใน LastHalf<T> ดังนั้น LastHalf<[1,2,3,4]> ควรเป็น [3,4] และ LastHalf<[1,2,3,4,5]> ควรเป็น [4,5]:

type LastHalf<T extends any[]> = T extends [...FirstHalf<T>, ...infer E] ? E : never;

จากนั้น, Interleave<T, U> จะสลับองค์ประกอบจาก T กับองค์ประกอบจาก U, ดังนั้น Interleave<[1,2,3],["A","B","C"]> ควรเป็น [1,"A",2,"B",3,"C"]. ถ้า T หรือ U มีองค์ประกอบเหลืออยู่ ส่วนที่เหลือจะอยู่ด้านท้าย ดังนั้น Interleave<[1,2],["A","B","C","D","E"]> ควรเป็น [1,"A",2,"B","C","D","E"]:

type Interleave<T extends any[], U extends any[]> =
    T extends [infer H, ...infer R] ? [H, ...Interleave<U, R>] : U

(โปรดทราบว่านี่เกิดขึ้นโดยการสลับบทบาทของ T และ U ในการเรียกแบบเรียกซ้ำ)

สุดท้าย, Shuffle<T> จะแยก T ออกเป็น FirstHalf และ LastHalf และ Interleave ครึ่งสองส่วนเข้าด้วยกัน:

type Shuffle<T extends any[]> = Interleave<FirstHalf<[...T]>, LastHalf<[...T]>>;   

ฉันไม่ได้เปลี่ยนแปลงการใช้งานของฟังก์ชัน shuffle() ของคุณ; ใช่ คุณต้องใช้การยืนยันชนิดข้อมูลหรือลักษณะอื่นเพื่อโน้มน้าวคอมไพเลอร์ว่าการใช้งานนี้ปลอดภัย แทบไม่มีโอกาสที่คอมไพเลอร์จะสามารถติดตามได้ว่าการปรับเปลี่ยนอาร์เรย์ใด ๆ จะเปลี่ยน T เป็น Shuffle<T> ในตัวอย่างต่อไปนี้ ฉันใช้ฟังก์ชันโอเวอร์โหลดที่มีลายเซ็นเรียกใช้เพียงครั้งเดียวเพื่อหลีกเลี่ยงการต้องใช้การยืนยันภายในตัวฟังก์ชัน:

function shuffle<T extends readonly any[]>(array: T): Shuffle<[...T]>;
function shuffle(array: any[]) {
    if (array.length === 0 || array.length === 1) {
        return array.slice();
    }
    const rest = array.slice();
    const middle = rest.splice(Math.ceil(array.length / 2), 1)[0];
    const first = rest.shift();
    return [first, middle, ...shuffle(rest)];
};

แล้วมาทดลองมันกันเถอะ:

const shuffled = shuffle([1, 2, 3, 4, 5, 6, 7, 8] as const);
// const shuffled: [1, 5, 2, 6, 3, 7, 4, 8]
console.log(shuffled); // [1, 5, 2, 6, 3, 7, 4, 8]

const oddShuffled = shuffle([1, 2, 3, 4, 5, 6, 7] as const);
// const oddShuffled: [1, 5, 2, 6, 3, 7, 4]
console.log(oddShuffled); // [1, 5, 2, 6, 3, 7, 4] 

ใช่ ดูดีนะ!

ลิงก์ Playground ไปยังโค้ด

คำตอบ #2

ตามที่สัญญาไว้ นี่คือวิธีแก้ปัญหาที่ฉันคิดออก

type SplitEven<T extends readonly any[], Start extends any[] = [], End extends any[] = []> =
    T['length'] extends 0 | 1 ? [[...Start, ...T], End] :
    T extends readonly [infer S, ...infer M, infer E] ? SplitEven<M, [...Start, S], [E, ...End]> :
    never;

type Shuffle<T extends readonly any[]> =
    T['length'] extends 0 | 1
        ? T
        : SplitEven<T> extends infer A
            ? A extends readonly [readonly [infer AH, ...infer AR], readonly [infer BH, ...infer BR]]
                ? [AH, BH, ...Shuffle<[...AR, ...BR]>]
                : never
            : never;

function shuffle<T extends readonly any[]>(array: T): Shuffle<T> {
    if (array.length === 0 || array.length === 1) {
        return array.slice() as Shuffle<T>;
    }

    const rest = array.slice();
    const middle = rest.splice(Math.ceil(array.length / 2), 1)[0];
    const first = rest.shift();

    return [first, middle, ...shuffle(rest)] as Shuffle<T>;
}

const array = [1, 2, 3, 4, 5, 6, 7, 8] as const;
const shuffled = shuffle(array);

type Shuffled = typeof shuffled; // [1, 5, 2, 6, 3, 7, 4, 8]

console.log(shuffled);

สนามเด็กเล่น TypeScript

ทั้งฟังก์ชันและประเภทก็ทำงานกับอาร์เรย์ที่มีความยาวเป็นคี่ด้วยเช่นกัน

สิ่งเดียวที่เหลือคือหาวิธีว่าฉันสามารถหลีกเลี่ยง as Shuffle<T> ในคำสั่ง return ได้หรือไม่ ฉันสงสัยว่าคำสั่งที่สองเกินความสามารถของ TSC เพราะมันจะต้องรู้ว่า rest, middle และ first ถูกกำหนดอย่างไร แต่ฉันก็แปลกใจที่คำสั่งแรกไม่ได้รับการอนุมาน