Каким механизмом мемоизируется эта функция Фибоначчи?
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)
fib 0
не заканчивается: вы, вероятно, хотите, чтобы базовые случаиfib'
былиfib' 0 = 0
иfib' 1 = 1
.fibs = 1:1:zipWith (+) fibs (tail fibs)
иfib = (fibs !!)
.Ответы:
Механизм оценки в Haskell основан на необходимости : когда значение необходимо, оно вычисляется и остается готовым на случай, если его снова попросят. Если мы определим какой-то список,
xs=[0..]
а позже запросим его 100-й элемент,xs!!99
100-й слот в списке будет «развернут», в нем99
теперь будет стоять номер , готовый для следующего доступа.Это то, что использует этот трюк «просмотр списка». В обычном определении Фибоначчи с двойным рекурсивом,
fib n = fib (n-1) + fib (n-2)
сама функция вызывается дважды сверху, вызывая экспоненциальный взрыв. Но с помощью этого трюка мы составили список для промежуточных результатов и проходим его «по списку»:Хитрость заключается в том, чтобы создать этот список и заставить этот список не удаляться (посредством сборки мусора) между вызовами
fib
. Самый простой способ добиться этого - назвать этот список. «Если вы его назовете, он останется».Ваша первая версия определяет мономорфную константу, а вторая определяет полиморфную функцию. Полиморфная функция не может использовать один и тот же внутренний список для разных типов, которые ей могут понадобиться для обслуживания, поэтому никакого совместного использования , то есть мемоизации.
В первой версии компилятор проявил щедрость к нам, исключив это константное подвыражение (
map fib' [0..]
) и сделав его отдельным разделяемым объектом, но он не обязан это делать. и на самом деле бывают случаи, когда мы не хотим, чтобы это происходило автоматически.( править :) Рассмотрим эти переписывания:
Итак, реальная история, похоже, связана с определениями вложенной области видимости. В первом определении нет внешней области видимости, а в третьем стараются не вызывать внешнюю область видимости
fib3
, а того же уровняf
.Каждый новый вызов,
fib2
кажется, создает свои вложенные определения заново, потому что любое из них может (теоретически) быть определено по-разному в зависимости от значенияn
(спасибо Витусу и Тихону за указание на это). С первым определением нетn
зависимости, а с третьим есть зависимость, но каждый отдельный вызовfib3
вызовов, вf
который осторожно, чтобы вызывать определения только из области того же уровня, внутренней для этого конкретного вызоваfib3
, поэтому то же самоеxs
получает повторно используется (т. е. совместно используется) для этого вызоваfib3
.Но ничто не мешает компилятору распознать, что внутренние определения в любой из вышеперечисленных версий фактически не зависят от внешней
n
привязки, чтобы в конце концов выполнить подъем лямбда , что приведет к полной мемоизации (кроме полиморфных определений). Фактически это именно то, что происходит со всеми тремя версиями, когда они объявлены с мономорфными типами и скомпилированы с флагом -O2. С объявлениями полиморфного типаfib3
демонстрирует локальное совместное использование иfib2
полное отсутствие совместного использования.В конечном итоге, в зависимости от компилятора и используемых оптимизаций компилятора, а также от того, как вы его тестируете (загрузка файлов в GHCI, скомпилированных или нет, с -O2 или нет, или автономно), и будет ли он иметь мономорфный или полиморфный тип, поведение может полностью изменится - будет ли он демонстрировать локальное (для каждого вызова) совместное использование (т.е. линейное время для каждого вызова), мемоизацию (т.е. линейное время для первого вызова и нулевое время для последующих вызовов с тем же или меньшим аргументом) или полное отсутствие совместного использования ( экспоненциальное время).
Короткий ответ: это компилятор. :)
источник
fib'
переопределяется для каждогоn
и, следовательно,fib'
вfib 1
≠fib'
infib 2
, что также подразумевает, что списки разные. Даже если вы исправите тип как мономорфный, он все равно будет демонстрировать такое поведение.where
предложения вводят совместное использование во многом схожих сlet
выражениями, но они, как правило, скрывают проблемы, подобные этой. Переписав его более подробно, вы получите следующее: hpaste.org/71406Int -> Integer
), то они будут выполняться вfib2
экспоненциальном времени,fib1
иfib3
оба будут выполняться в линейном времени, ноfib1
также запомнены - опять же, потомуfib3
что локальные определения переопределяются для каждогоn
.pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]
мы действительно хотим,pwr xs
чтобы их вычисляли независимо, дважды, чтобы его можно было собирать мусором на лету, когда он создается и потребляется.Я не совсем уверен, но вот обоснованное предположение:
Компилятор предполагает, что это
fib n
может быть по-другому,n
и поэтому каждый раз придется пересчитывать список. В конце концов, биты внутриwhere
оператора могут зависеть отn
. То есть в данном случае весь список чисел является функцией отn
.Версия без
n
может создать список один раз и обернуть его функцией. Список не может зависеть отn
переданного значения, и это легко проверить. Список - это константа, которая затем индексируется. Конечно, это константа, которая вычисляется лениво, поэтому ваша программа не пытается сразу получить весь (бесконечный) список. Поскольку это константа, ее можно использовать в вызовах функций.Он вообще запомнен, потому что рекурсивный вызов просто должен искать значение в списке. Поскольку
fib
версия создает список один раз лениво, она просто вычисляет достаточно, чтобы получить ответ, не выполняя лишних вычислений. Здесь «ленивый» означает, что каждая запись в списке является преобразователем (неоцененным выражением). Когда вы действительно оценить преобразователь , она становится значением, поэтому доступ к нему в следующий раз это не повторить вычисление. Поскольку список может использоваться совместно между вызовами, все предыдущие записи уже рассчитаны к тому моменту, когда вам понадобится следующая.По сути, это умная и недорогая форма динамического программирования, основанная на ленивой семантике GHC. Я думаю, что стандарт только указывает, что он должен быть нестрогим , поэтому совместимый компилятор потенциально может скомпилировать этот код, чтобы не запоминать. Однако на практике любой разумный компилятор будет ленивым.
Для получения дополнительной информации о том, почему второй случай вообще работает, прочтите Понимание рекурсивно определенного списка (фибры в терминах zipWith) .
источник
fib' n
мог бы быть другим на другомn
"?fib
, в том числеfib'
, могло отличаться от всегоn
. Я думаю, что исходный пример немного сбивает с толку, потому что онfib'
также зависит от того,n
который затеняет другойn
.Во-первых, с ghc-7.4.2, скомпилированная с помощью
-O2
, немемоизированная версия не так уж плоха, внутренний список чисел Фибоначчи по-прежнему запоминается для каждого вызова функции верхнего уровня. Но это не и не может быть запомнено по разным вызовам верхнего уровня. Однако для другой версии список используется совместно для вызовов.Это связано с ограничением мономорфизма.
Первый связан простой привязкой к шаблону (только имя, без аргументов), поэтому по ограничению мономорфизма он должен получить мономорфный тип. Предполагаемый тип
и такое ограничение устанавливается по умолчанию (в отсутствие декларации по умолчанию, говорящей об обратном)
Integer
, фиксируя тип какТаким образом, есть только один список (типа
[Integer]
) для запоминания.Второй определяется с помощью аргумента функции, поэтому он остается полиморфным, и если бы внутренние списки были мемоизированы между вызовами, один список должен был бы быть мемоизирован для каждого типа в
Num
. Это непрактично.Скомпилируйте обе версии с отключенным ограничением мономорфизма или с идентичными типами сигнатур, и обе они будут вести себя одинаково. (Это было не так для старых версий компилятора, я не знаю, какая версия сделала это первой.)
источник
fib 1000000
к множеству типов, это съедает тонну памяти. Чтобы этого избежать, понадобится эвристика, которая выдает списки из кеша, когда он становится слишком большим. И такая стратегия мемоизации, по-видимому, также будет применяться к другим функциям или значениям, поэтому компилятору придется иметь дело с потенциально большим количеством вещей, которые нужно запоминать для потенциально многих типов. Я думаю, что можно было бы реализовать (частичную) полиморфную мемуизацию с достаточно хорошей эвристикой, но я сомневаюсь, что это того стоит.Для Haskell вам не нужна функция Memoize. Эти функции нужны только эмпирическому языку программирования. Однако Haskel - это функциональный язык и ...
Итак, это пример очень быстрого алгоритма Фибоначчи:
zipWith - это функция из стандартного Prelude:
Тест:
Вывод:
Истекшее время: 0,00018 с
источник