Как запоминается эта функция Фибоначчи?

По какому механизму запоминается эта функция Фибоначчи?

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

И на связанной ноте, почему эта версия не?

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    
 huon13 июл. 2012 г., 09:51
Слегка безотносительно,fib 0 не заканчивается: вам, вероятно, нужны базовые случаи дляfib' бытьfib' 0 = 0 а такжеfib' 1 = 1.
 Nikita Volkov13 июл. 2012 г., 11:53
Очень хороший вопрос
 Bastian19 авг. 2012 г., 10:24
Обратите внимание, что первая версия может быть более краткой:fibs = 1:1:zipWith (+) fibs (tail fibs) а такжеfib = (fibs !!).

Ответы на вопрос(4)

граммирования нуждается в этих функциях. Тем не менее, Хаскель является функциональным языком и ...

Итак, это пример очень быстрого алгоритма Фибоначчи:

fib = zipWith (+) (0:(1:fib)) (1:fib)

zip с функцией из стандартной прелюдии:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

Тестовое задание:

print $ take 100 fib

Выход:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

Прошедшее время: 0,00018 с

 08 дек. 2015 г., 09:06
Это великолепное решение!
 08 дек. 2015 г., 10:06
fib = zipWith (+) (0: (1: fib)) (0: fib), если мы хотим начать с 0,1,1,2 ...

-O2не забываемая версия не так уж и плоха, внутренний список чисел Фибоначчи все еще запоминается для каждого вызова функции на высшем уровне. Но это не и не может быть разумно запомнено в разных вызовах на высшем уровне. Однако, для другой версии, этот список является общим для вызовов.

Это связано с ограничением мономорфизма.

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

fib :: (Num n) => Int -> n

и такое ограничение становится дефолтным (при отсутствии декларации по умолчанию, говорящей иначе)Integer, фиксируя тип как

fib :: Int -> Integer

Таким образом, существует только один список (типа[Integer]Запомни.

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

Скомпилируйте обе версии с отключенным ограничением мономорфизма или с одинаковыми сигнатурами типов, и обе будут иметь абсолютно одинаковое поведение. (Это было не так для более старых версий компилятора, я не знаю, какая версия сначала это сделала.)

 06 янв. 2014 г., 22:16
Почему нецелесообразно запоминать список для каждого типа? В принципе, может ли GHC создать словарь (очень похожий на вызов функций с ограниченным классом типов), который будет содержать частично вычисляемые списки для каждого типа Num, встречающегося во время выполнения?
 06 янв. 2014 г., 22:35
@misterbee В принципе, может, но если программа вызываетfib 1000000 на многих типах, которые съедают тонну памяти. Чтобы избежать этого, понадобится эвристика, списки которой выбрасываются из кэша, когда он становится слишком большим. И такая стратегия запоминания будет также применяться к другим функциям или значениям, предположительно, поэтому компилятору придется иметь дело с потенциально большим количеством вещей, которые нужно запомнить для потенциально многих типов. Я думаю, что было бы возможно реализовать (частичное) полиморфное запоминание с достаточно хорошей эвристикой, но я сомневаюсь, что это стоило бы.

Я не совсем уверен, но вот обоснованное предположение:

Компилятор предполагает, чтоfib n может быть по-другомуn и, таким образом, придется пересчитывать список каждый раз. Биты внутриwhere заявлениеcould зависит отn, в конце концов. То есть в этом случае весь список чисел по существу является функциейn.

Версияwithout n может создать список один раз и обернуть его в функцию. Списокcannot зависит от стоимостиn прошло, и это легко проверить. Список является константой, которая затем индексируется в. Это, конечно, константа, которая лениво оценивается, поэтому ваша программа не пытается сразу получить полный (бесконечный) список. Поскольку он является константой, его можно использовать для всех вызовов функций.

Это вообще запоминается, потому что рекурсивный вызов просто ищет значение в списке. Посколькуfib версия создает список один раз лениво, она просто рассчитывает достаточно, чтобы получить ответ, не делая лишних вычислений. Здесь "ленивый" означает, что каждая запись в списке является thunk (выражение без оценки). Когда тыdo Оцените thunk, он становится значением, поэтому при следующем обращении к нему вычисления не повторяются. Поскольку список может быть разделен между вызовами, все предыдущие записи уже рассчитаны к тому времени, когда вам потребуется следующая.

Это по существу умная и недорогая форма динамического программирования, основанная на ленивой семантике GHC. Я думаю, что стандарт только указывает, что это должно бытьnon-strictпоэтому совместимый компилятор может потенциально скомпилировать этот код вnot memoize. Однако на практике каждый разумный компилятор будет ленивым.

Для получения дополнительной информации о том, почему второй случай работает вообще, прочитайтеПонимание рекурсивно определенного списка (fibs с точки зрения zipWith).

 13 июл. 2012 г., 17:33
Вы имели в виду & quot;fib' n может быть по-другомуn& Quot; возможно?
 14 июл. 2012 г., 01:19
Я думаю, что я не очень ясно: я имел в виду, что все внутриfib, в том числеfib', может быть по-разномуn, Я думаю, что оригинальный пример немного сбивает с толку, потому чтоfib' также зависит от его собственнойn которая затмевает другогоn.
Решение Вопроса

by-need: когда значение необходимо, оно рассчитывается и сохраняется на случай повторного запроса. Если мы определим какой-то список,xs=[0..] а потом попросить его сотый элемент,xs!!99100-й слот в списке становится «выделенным», удерживая номер99 теперь готов к следующему доступу.

Это то, что использует этот трюк, «прохождение через список». В обычном двукратно-рекурсивном определении Фибоначчиfib n = fib (n-1) + fib (n-2), сама функция вызывается дважды сверху, вызывая экспоненциальный взрыв. Но с помощью этого трюка мы составили список промежуточных результатов и "просматриваем список":

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

Хитрость заключается в том, чтобы этот список создавался, и чтобы этот список не исчезал (посредством сборки мусора) между вызовамиfib, Самый простой способ добиться этого, этоname этот список."If you name it, it will stay."

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

С первой версией компиляторgenerous с нами, вынимая это постоянное подвыражение (map fib' [0..]) и превращение его в отдельную акционерную компанию, но она не обязана это делать.and there are actually cases where we don't want it to do that for us automatically.

(edit:) Рассмотрим эти переписывает:

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

Таким образом, реальная история, кажется, о вложенных определениях области. С 1-м определением не существует внешней области видимости, а 3-е осторожно, чтобы не вызывать внешнюю область.fib3, но на том же уровнеf.

Каждый новый вызовfib2 кажется, создает свои вложенные определения заново, потому что любое из нихcould (в теории) определяется по-разномуdepending по стоимостиn (спасибо Витусу и Тихону за указание на это). С первым определением нетn зависеть, а с третьим есть зависимость, но каждый отдельный вызовfib3 призывает вf который осторожен, чтобы вызывать только определения из области того же уровня, внутренний для этого конкретного вызоваfib3так жеxs повторно используется (т.е. разделяется) для этого вызоваfib3.

Но ничто не мешает компилятору признать, что внутренние определения в любой из версий выше на самом делеindependent внешнегоn обязательна, чтобы выполнитьлямбда-лифтинг в конце концов, что приводит к полной запоминанию (за исключением полиморфных определений). Фактически это именно то, что происходит со всеми тремя версиями, когда они объявлены с мономорфными типами и скомпилированы с флагом -O2. С полиморфными объявлениями типов,fib3 экспонаты местного обмена иfib2 не делиться вообще.

В конечном счете, в зависимости от компилятора и используемых оптимизаций компилятора, и от того, как вы его тестируете (загрузка файлов в GHCI, скомпилированная или нет, с -O2 или нет, или автономно), а также от того, получает ли он мономорфный или полиморфный тип, поведение может полностью изменить - показывает ли он локальное (для каждого вызова) разделение (т. е. линейное время при каждом вызове), запоминание (т. е. линейное время при первом вызове и 0 раз при последующих вызовах с таким же или меньшим аргументом) или вообще не используется ( экспоненциальное время).

Короткий ответ: это вещь компилятора. :)

 06 янв. 2014 г., 23:03
@misterbee Но на самом деле было бы неплохо получить некоторую гарантию от компилятора; какой-то контроль над памятью резидентности конкретного объекта. Иногда мы хотим поделиться, иногда мы хотим предотвратить это. Я представляю / надеюсь, что это будет возможно ...
 13 июл. 2012 г., 17:12
where пункты вводят разделение так же, какlet выражения, но они, как правило, скрывают такие проблемы, как эта. Переписав это немного более явно, вы получите это:hpaste.org/71406
 13 июл. 2012 г., 18:09
Еще один интересный момент о вашем переписывании: если вы дадите им мономорфный тип (т.е.Int -> Integer), затемfib2 работает в экспоненциальном времени,fib1 а такжеfib3 оба работают в линейном времени, ноfib1 также запоминается - опять же, потому что дляfib3 локальные определения переопределяются для каждогоn.
 07 дек. 2018 г., 08:22
@ ElizaBrandt я имел в виду, что иногда мы хотим пересчитать что-то тяжелое, чтобы оно не оставалось для нас в памяти, т. Е. Стоимость пересчета ниже, чем стоимость огромного удержания памяти. Одним из примеров является создание powerset: вpwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]] мы хотимpwr xs рассчитывается независимо, дважды, так что мусор можно собирать на лету во время его производства и потребления.
 13 июл. 2012 г., 15:18
Просто для исправления небольшой детали: вторая версия не получает никакого совместного доступа, главным образом из-за локальной функцииfib' переопределено для каждогоn и поэтомуfib' вfib 1 & # X2260;fib' вfib 2, что также подразумевает, что списки разные. Даже если вы исправите тип как мономорфный, он все равно будет демонстрировать это поведение.

Ваш ответ на вопрос