Почему "итерация" из прелюдии не завязывает узел?
Почему нет iterate определяется как
iterate :: (a -> a) -> a -> [a]
iterate f x = xs where xs = x : map f xs
в прелюдии?
3 ответа
Завязывание узла таким образом не увеличивает обмен.
Контраст с:
cycle xs = let x = xs ++ x in x
Привязка к узлу приводит к созданию круглого связанного списка в памяти. x это собственный хвост. Там есть реальная выгода.
Ваша предлагаемая реализация не увеличивает совместное использование по сравнению с наивной реализацией. И нет никакого способа сделать это в первую очередь - нет общей структуры в чем-то вроде iterate (+1) 0 тем не мение.
В вашей версии нет привязки узлов, она просто поддерживает указатель на одну ступеньку назад в созданном списке, чтобы найти входное значение там для следующей итерации. Это означает, что каждую ячейку списка нельзя редактировать до тех пор, пока не будет создана следующая ячейка.
Версия Prelude, напротив, использует iterateДля этого требуется фрейм вызова, и поскольку он нужен только один раз, хороший компилятор может повторно использовать этот фрейм и изменить его значение для более оптимизированной работы в целом (и в этом случае ячейки списка не зависят друг от друга).
Определение Prelude, которое я включаю ниже для ясности, не требует дополнительных затрат для вызова карты.
iterate f x = x : iterate f (f x)
Просто для удовольствия, я сделал небольшую быструю программу для проверки вашего iterate против прелюдии - просто чтобы привести к нормальной форме take 100000000 $ iterate (+1) 0 (это список Intс). Я провел только 5 тестов, но ваша версия работала 7.833 (Максимум 7.873 мин 7.667) в то время как Прелюдия была в 7.519 (Максимум 7.591 мин 7.477). Я подозреваю, что разница во времени является накладной map получать вызов.
Вторая причина проста: удобочитаемость.