Ответ 1
Я не могу предоставить исчерпывающий ответ для Haskell, но для Scala ответ довольно прост: он выполняет преобразования в байт-коде, так что, например, (простой) хвостовой вызов реализуется как цикл с переменными вместо. По сути, это то, что нужно сделать для достижения хорошей производительности, поскольку компьютеры изменяемы (RAM, а не WORM!).
Превращение метода во что-то, что может быть передано, включает в себя создание объекта, но создание объекта на JVM дешево, и как JVM, так и Scala имеют или будут иметь трюки, чтобы вообще не создавать этот объект, если это действительно необходимо.
Тогда возникает проблема повторного использования памяти и использования новой памяти. Это трудно обойти полностью, но JVM очень хорош в быстром восстановлении памяти, поэтому вы платите относительно скромный штраф за, например, каждый раз воссоздавая свой список, вместо того, чтобы изменять значения в нем. (Если ссылки на старый список не сохранились, вы можете просто изменить значения и назвать их новым списком - я не знаю, играет ли GHC такие трюки.) Худшая ситуация - когда вам нужно локальное обновление, где вы в некоторых случаях может работать log (n) вместо работы с постоянным временем.
Когда вы добавляете все эти вещи вместе, (однопоточная) оценка производительности часто бывает скромной или незначительной.