Comments 9
(ленивость в Хаскеле — основополагающая вещь, именно она позволила так упростить язык, что if можно сделать функцией… Да и бесконечные списки вместо циклов — подарок от ленивого выполнения).
Лучше б на какой ML сослались (хоть на F#), чем на Хаскель. А то открываю статью с мыслью «а ну-ка посмотрим, как они там замутили ленивые списки» — ан нет, списки-то обычные,
Плюс один. Впечатление от статьи, что ее задача была именно «да на что нам ваш хаскель, хайповый модный котлин могет не хуже».
Ан нет, не могет.
Согласен, ленивые списки просто волшебные.
Как мне кажется, статья не отражает "Haskell подход". В Haskell — простая структура данных (cons-list) + рекурсия позволяют эффективно решать перечисленные задачи. Предлагаемые в статье алгоритмы выглядят неэффективно.
Например, size использует метод tail типа List, что, в случае array-list'а будет копировать почти весь лист (O(N) по времени и по памяти), а затем не использует хвостовую рекурсию (O(N) по памяти), чтобы прибавить 1. Тем самым общая вычислительная сложность оказывается O(N^2), что отличается от обычной сложности O(N) по времени и O(1) по памяти.
В примере с хвостовой рекурсией автор также использует when(xs.size) внутри функции. В случае, если List — односвязный список, опять окажется, что каждый вызов O(N). В итоге хвостовая рекурсия не спасает, получаем O(N^2). (Можно было бы использовать when(xs.isEmpty) с O(1).)
Списки в Kotlin. Haskell подход