Взаимно рекурсивные родовые перечисления - PullRequest
Новая
       16

Взаимно рекурсивные родовые перечисления

2 голосов
/ 30 апреля 2019

Общий рекурсив enum

Я могу легко выразить универсальное рекурсивное перечисление в Swift: 

indirect enum Tree<T> {
    case empty
    case leaf(T)
    case node(Tree, Tree)
}

Учитывая это, я могу создать несколько примеров деревьев Int, скажем: 

let exampleTrees: [Tree<Int>] = [
    .empty,
    .leaf(10),
    .node(.node(.leaf(1), .leaf(2)), .node(.leaf(3), .leaf(4)))
]

Взаимная рекурсия

Перечисление Tree является рекурсивным аналогично рекурсивной функции. Случаи empty и leaf завершают рекурсию, а node - рекурсивный случай.

В рекурсивных функциях весьма обычно иметь пару взаимно рекурсивных функций. Глупый, но классический иллюстративный пример: 

func isEven(_ x: Int) -> Bool {
    return x == 0 ? true : isOdd(x-1)
}

func isOdd(_ x: Int) -> Bool {
    return x == 0 ? false : isEven(x-1)
}

Аналогично, также можно объявить пару взаимно рекурсивных enum s: 

indirect enum AB {
    case a
    case b(CD)
}

indirect enum CD {
    case c
    case d(AB)
}

Учитывая это, я могу начать создавать рекурсивные значения. Вот несколько примеров ... 

let exampleRecursives: [AB] = [
    .a,
    .b(.c),
    .b(.d(.a)),
    .b(.d(.b(.c)))
]

(Это, очевидно, все совершенно глупо и бесполезно - это просто для иллюстрации того, что происходит!)

Универсальный взаимно рекурсивный enum

Определения AB и CD имеют ограничительный характер, поскольку они не являются общими, и я бы хотел, чтобы они были общими: 

indirect enum AB<T> {
    case a
    case b(T)
}

indirect enum CD<T> {
    case c
    case d(T)
}

Проблема

Учитывая, что у меня есть эти универсальные альтернативы, я хотел бы иметь возможность выразить тот же вид взаимно рекурсивного вложения, что и я, с неуниверсальными оригиналами. Мне нужно сказать Свифту, что тип AB<CD<AB<CD<AB<CD<AB<CD<AB<CD< …, но бесконечно длинный.

Я попытался выразить это следующим образом: 

typealias RecursiveABCD = AB<CD<RecursiveABCD>>

Это дает ошибку компиляции "Circular reference" хотя.

Я тоже пробовал это: 

typealias RecursiveAB = AB<RecursiveCD>
typealias RecursiveCD = CD<RecursiveAB>

Но опять же, ошибки компилятора с "Circular reference".

Работа вокруг

Обходным путем будет определение типа оболочки, например: 

struct W {
    init(_ x: AB<CD<W>>) {
        self.x = x
    }

    let x: AB<CD<W>>
}

Если я сделаю это, я смогу создать примеры, например: 

let exampleRecursives: [W] = [
    W(.a),
    W(.b(.c)),
    W(.b(.d(W(.a)))),
    W(.b(.d(W(.b(.c)))))
]

Похоже, это станет очень громоздким и неудобным в использовании.

Вопрос

Можно ли использовать рекурсивные обобщенные перечисления без использования оболочки?

...