Ленивая оценка терминов в бесконечном списке в Haskell

Меня интересует производительность бесконечного списка, такого как тот, что ниже:

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 выполняет кэширование для предотвращения множественных вычислений здесь?

41
задан Jonathan Sterling 10 June 2012 в 22:31
поделиться