Как часто оценивается расширяющийся список

Оценивается ли fib с самого начала для каждого элемента cumfib?

fib = (1:1: zipWith (+) fib (tail fib))
cumfib = [ sum $ take i fib | i<-[1..]]

Или первые элементы i кэшируются и повторно используются для элемента (i + 1) cumsum?

Я более или менее предполагаю, что fib используется в одном и том же лямбда-выражении и, следовательно, вычисляется только один раз.

Кроме того, имеет ли значение реализация fib в отношении того, как часто оценивается i-е число Фибоначчи? Моя актуальная проблема касается простых чисел, а не чисел Фибоначчи, которые я хочу «кэшировать», чтобы легко вычислять простые множители некоторого числа n. Однако я использую только

takeWhile (\x-> x*x<n) primes

простых чисел. Поскольку я сначала оцениваю множители для малых n, а затем для больших n, это подмножество простых чисел увеличивается, и поэтому мне интересно, как часто будут оцениваться простые числа, если я это сделаю:

primes = ... some way of calculating primes ...
helpHandlePrimes ... = ... using primes ...
handlePrimes = ... using primes and helpHandlePrimes ...

Пожалуйста, дайте мне знать, оцениваются ли простые числа один раз, несколько раз или это нельзя определить по тому, как я сформулировал вопрос.


memoization haskell caf
person Herbert    schedule 13.03.2014    source источник
comment
Это зависит от того, где написано fib. Это значение высшего уровня? Или просто пусть связанная переменная в какой-то функции?   -  person Ingo    schedule 13.03.2014
comment
На верхнем уровне, но я мог бы сделать: someFuntion ... = .... где fibsOfInterest = takeWhile (‹=1000) fibs, будет ли это работать?   -  person Herbert    schedule 13.03.2014
comment
Да и выдумки расширяли бы по мере необходимости, без переоценки.   -  person Ingo    schedule 13.03.2014

Ответы (2)


arrow_upward
5
arrow_downward

Термин с привязкой к let обычно используется совместно в пределах его области действия. В частности, термин верхнего уровня в модуле является общим для всей программы. Однако вы должны быть осторожны с типом термина. Если термин является функцией, то совместное использование означает, что совместно используется только лямбда-абстракция, поэтому функция не запоминается. Перегруженный термин внутренне представлен как функция, поэтому совместное использование также не имеет смысла для перегруженного термина.

Итак, если у вас есть мономорфный список чисел, он будет общим. По умолчанию список, такой как fib, который вы указали, будет мономорфным из-за «ограничения мономорфизма» (на самом деле это тот случай, когда это полезно). Однако в наши дни модно отключать ограничение мономорфизма, поэтому в любом случае я рекомендую давать явную сигнатуру типа, такую ​​как

fib :: [Integer]

чтобы быть уверенным и дать понять всем, что вы ожидаете, что это будет мономорфный список.

person kosmikus    schedule 13.03.2014

arrow_upward
0
arrow_downward

Я хотел бы добавить, что таким образом cumfib без необходимости повторно вычисляет сумму первых i элементов fib. Его можно более эффективно определить как

cumfib = tail $ scanl (+) 0 fib
person Petr    schedule 13.03.2014
comment
Я ценю ваш комментарий, и вы правы, но это не ответ на мой вопрос. - person Herbert; 14.03.2014