Как перевернуть список, используя только три функции

Question

Если мне дано три функции: 1) пустой - возвращает, является ли переданный список пустым 2) split - разбивает один список на два списка одинакового размера 3) concat - объединяет два списка в один

Использование толькоэти три функции, как я могу перевернуть список?

Answer 1

Разделить список на два, рекурсивно перевернуть подсписки и объединить их в обратном направлении.

def reverse(x) {
    y, z = split(x)
    if (empty(y) || empty(z)) 
        return x // list has only one element
    else
        return concat(reverse(z), reverse(y))

}