Кратко — почему медленно/зацикливается, и что делать.
Почему текущая реализация медленная/может зацикливаться
- rev/2 реализована через рекурсивный вызов rev(T, RT) и затем append(RT, [H], R). Для списка длины $n$ каждый шаг делает append, который копирует префикс — суммарная стоимость порядка
${\sum }_{i=1}^{n}i=n(n+1)/2$, то есть $O(n^2)$.
- append/3 реверсивен и при частично/неинициализированных аргументах порождает много разветвлений (он перебирает все разбиения списка). Поэтому запросы с переменными (например, rev(X,Y) или общие режимы поиска всех решений) приводят к огромному числу ветвей или к бесконечному перебору — система будет генерировать всё новые и новые разбиения/списки и не завершится.
Примеры проблемных запросов
- rev(X,Y). — будет порождать бесконечно много пар списков (разной длины) и не завершится.
- rev(L, R) для больших L — сильно медленно из‑за квадратичной сложности.
(указать конкретные шаги можно, но суть — append в теле вызывает множество копирований и разветвлений).
Эффективная реализация (хвостовая рекурсия, аккумулятор)
- Линейная по времени $O(n)$, не использует append:
rev(L, R) :- rev_acc(L, [], R).
rev_acc([], Acc, Acc).
rev_acc([H|T], Acc, R) :- rev_acc(T, [H|Acc], R).
Пояснение:
- rev_acc делает один проход по списку, накапливая результат в аккумуляторе; каждая константа добавляется в голову аккумулятора за $O(1)$, всего $O(n)$.
- Хвостовая рекурсия — экономное использование стека и значительно быстрее.
Замечания по режимам вызова
- Аккумуляторная версия оптимальна, когда первый аргумент известен и нужно получить обратный список.
- Если требуется полная реляционность (перебор всех пар списков, обратных друг другу), исходная реализация более «генеративна», но она и медленная/порождает бесконечные ветви. Для таких задач нужно продумывать ограничения или специальные генераторы (например, генерация списков заданной длины и их реверс), либо использовать другие техники (difference lists) с контролем разветвления.
Вывод: замените rev/2 на версию с аккумулятором для эффективности и предсказуемости; используйте оригинальную только там, где нужно специально перечислять все возможные парные решений.