Как запоминается эта функция Фибоначчи?
По какому механизму запоминается эта функция Фибоначчи?
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)
4 ответа
Механизм оценки в Haskell является побочным: когда значение требуется, оно вычисляется и сохраняется в случае повторного запроса. Если мы определим какой-то список, xs=[0..] а потом попросить его сотый элемент, xs!!99, сотый слот в списке становится "выделенным", держа номер 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, Самый простой способ добиться этого - назвать этот список. "Если вы назовете это, оно останется".
Ваша первая версия определяет мономорфную константу, а вторая определяет полиморфную функцию. Полиморфная функция не может использовать один и тот же внутренний список для разных типов, которые ей, возможно, понадобится обслуживать, поэтому нет общего доступа, то есть нет памятки.
С первой версией компилятор был щедрым с нами, исключая это постоянное подвыражение (map fib' [0..]) и превращение его в отдельную акционерную компанию, но она не обязана это делать. и есть случаи, когда мы не хотим, чтобы это делалось для нас автоматически.
(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 кажется, создает свои вложенные определения заново, потому что любое из них (в теории) может быть определено по-разному в зависимости от значения n (спасибо Витусу и Тихону за указание на это). С первым определением нет n зависеть от, а с третьим есть зависимость, но каждый отдельный вызов fib3 призывает в f который осторожен, чтобы вызывать только определения из области того же уровня, внутренний для этого конкретного вызова fib3 так же xs получает повторное использование (то есть разделяемое) для этого вызова fib3,
Но ничто не мешает компилятору признать, что внутренние определения в любой из версий выше на самом деле не зависят от внешнего n связывание, для выполнения лямбда-лифтинга в конце концов, что приводит к полной запоминанию (за исключением полиморфных определений). Фактически, это именно то, что происходит со всеми тремя версиями, когда они объявлены с мономорфными типами и скомпилированы с флагом -O2. С полиморфными объявлениями типов, fib3 экспонаты местного обмена и fib2 не делиться вообще.
В конечном счете, в зависимости от компилятора и используемых оптимизаций компилятора, а также от того, как вы его тестируете (загрузка файлов в GHCI, скомпилированная или нет, с -O2 или нет или автономно), а также от того, получает ли он мономорфный или полиморфный тип, поведение может полностью изменить - показывает ли он локальное (для каждого вызова) разделение (т. е. линейное время при каждом вызове), запоминание (т. е. линейное время при первом вызове и 0 раз при последующих вызовах с таким же или меньшим аргументом) или вообще не используется (экспоненциальное время).
Короткий ответ, это вещь компилятора.:)
Я не совсем уверен, но вот обоснованное предположение:
Компилятор предполагает, что fib n может быть по-другому n и, таким образом, придется пересчитывать список каждый раз. Биты внутри where заявление может зависеть от n, в конце концов. То есть в этом случае весь список чисел по существу является функцией n,
Версия без n Можно создать список один раз и обернуть его в функцию. Список не может зависеть от значения n прошло, и это легко проверить. Список является константой, которая затем индексируется в. Это, конечно, константа, которая лениво оценивается, поэтому ваша программа не пытается сразу получить полный (бесконечный) список. Поскольку это константа, она может быть разделена между вызовами функций.
Это вообще запоминается, потому что рекурсивный вызов просто ищет значение в списке. Так как fib версия создает список один раз лениво, она просто вычисляет достаточно, чтобы получить ответ, не делая лишних вычислений. Здесь "ленивый" означает, что каждая запись в списке является thunk (неоцененное выражение). Когда вы оцениваете блок, он становится значением, поэтому при следующем обращении к нему вычисления не повторяются. Поскольку список может быть разделен между вызовами, все предыдущие записи уже рассчитаны к тому времени, когда вам понадобится следующая.
По сути, это умная и недорогая форма динамического программирования, основанная на ленивой семантике GHC. Я думаю, что стандарт только указывает, что он должен быть нестрогим, поэтому совместимый компилятор мог бы потенциально скомпилировать этот код, чтобы не запоминать. Однако на практике каждый разумный компилятор будет ленивым.
Для получения дополнительной информации о том, почему второй случай работает вообще, прочитайте Понимание рекурсивно определенного списка (fibs в терминах zipWith).
Во-первых, с помощью ghc-7.4.2, скомпилированного с -O2не забываемая версия не так уж плоха, внутренний список чисел Фибоначчи все еще запоминается для каждого вызова функции на высшем уровне. Но это не и не может быть разумно запомнено в разных вызовах на высшем уровне. Однако для другой версии этот список распределяется между вызовами.
Это связано с ограничением мономорфизма.
Первый связан простой привязкой к шаблону (только имя, без аргументов), поэтому по ограничению мономорфизма он должен получить мономорфный тип. Предполагаемый тип
fib :: (Num n) => Int -> n
и такое ограничение становится дефолтным (при отсутствии декларации по умолчанию, говорящей иначе) Integer, фиксируя тип как
fib :: Int -> Integer
Таким образом, есть только один список (типа [Integer]Запомни.
Второй определяется аргументом функции, поэтому он остается полиморфным, и если внутренние списки запоминаются при вызовах, один список должен запоминаться для каждого типа в Num, Это не практично.
Скомпилируйте обе версии с отключенным ограничением мономорфизма или с одинаковыми сигнатурами типов, и обе будут иметь одинаковое поведение. (Это не относится к более старым версиям компилятора, я не знаю, какая версия впервые это сделала.)
Вам не нужна функция памятки для Haskell. Только эмпирический язык программирования нуждается в этих функциях. Тем не менее, Хаскель является функциональным языком и...
Итак, это пример очень быстрого алгоритма Фибоначчи:
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 с