двух ипостасях: хвостово-рекурсивный, который разворачивает список, и не хвостово-рекурсивный, который список не разворачивает. Есть какой-то обобщенный способ писать хвостово-рекурсивные мапы для всех типов данных (которые поддерживают данную операцию)? Я покопался в исходниках библиотеки окмала и не нашел там хвостово-рекурсивного map даже для обычных деревьев
Нет такого способа. Хвостовая рекурсия использует O(1) памяти. Для обработки деревьев требуется O(высота) памяти - надо хранить структуру части дерева, которую ещё не отобразили. Разворот списка позволяет использовать кучу вместо стека, расходуя производительность взамен стека. Не-хвосто-рекурсивный вариант подходит только для коротких (высота ограничена) списков, но может быть чуть быстрее. У списка необработанная часть тривиальна, вот и возможно такое.
CPS вас не спасет?
Обсуждают сегодня