Меня интересует производительность бесконечного списка, такого как тот, что ниже:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Это создаст бесконечный список последовательности Фибоначчи.
Мой вопрос в том, что если я сделаю следующее:
takeWhile (<5) fibs
сколько раз fibs
оценивают каждый термин в списке? Похоже на то
поскольку takeWhile
проверяет функцию предиката для каждого элемента в
список, список fibs
будет оценивать каждый термин несколько раз. То
первые 2 триместра даются бесплатно. Когда takeWhile
хочет оценить
(<5)
для 3-го элемента, мы получим:
1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3
Теперь, когда takeWhile
захочет оценить (<5)
для 4-го элемента: в
рекурсивный характер fibs
построит список снова, как
следующее:
1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5
Казалось бы, 3-й элемент нужно вычислить снова, когда мы
хотите оценить значение 4-го элемента. Кроме того, если
предикат в takeWhile
большой, это указывает на то, что функция
выполнение дополнительной работы, которая необходима, поскольку она оценивает каждый предыдущий
элемент в списке несколько раз. Верен ли мой анализ здесь или нет?
Haskell выполняет кэширование для предотвращения множественных вычислений здесь?