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

114

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

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)                    
bjornars
источник
13
Слегка несвязанный, fib 0не заканчивается: вы, вероятно, хотите, чтобы базовые случаи fib'были fib' 0 = 0и fib' 1 = 1.
huon
1
Обратите внимание, что первую версию можно было бы сделать более сжатой: fibs = 1:1:zipWith (+) fibs (tail fibs)и fib = (fibs !!).
Bastian

Ответы:

95

Механизм оценки в Haskell основан на необходимости : когда значение необходимо, оно вычисляется и остается готовым на случай, если его снова попросят. Если мы определим какой-то список, xs=[0..]а позже запросим его 100-й элемент, 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. Самый простой способ добиться этого - назвать этот список. «Если вы его назовете, он останется».


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

В первой версии компилятор проявил щедрость к нам, исключив это константное подвыражение ( map fib' [0..]) и сделав его отдельным разделяемым объектом, но он не обязан это делать. и на самом деле бывают случаи, когда мы не хотим, чтобы это происходило автоматически.

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

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)

Итак, реальная история, похоже, связана с определениями вложенной области видимости. В первом определении нет внешней области видимости, а в третьем стараются не вызывать внешнюю область видимости fib3, а того же уровня f.

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

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

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

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

Уилл Несс
источник
4
Просто чтобы исправить небольшую деталь: вторая версия не имеет общего доступа в основном потому, что локальная функция fib'переопределяется для каждого nи, следовательно, fib'в fib 1fib'in fib 2, что также подразумевает, что списки разные. Даже если вы исправите тип как мономорфный, он все равно будет демонстрировать такое поведение.
Vitus
1
whereпредложения вводят совместное использование во многом схожих с letвыражениями, но они, как правило, скрывают проблемы, подобные этой. Переписав его более подробно, вы получите следующее: hpaste.org/71406
Витус
1
Еще один интересный момент, связанный с вашим переписыванием: если вы дадите им мономорфный тип (т.е. Int -> Integer), то они будут выполняться в fib2экспоненциальном времени, fib1и fib3оба будут выполняться в линейном времени, но fib1также запомнены - опять же, потому fib3что локальные определения переопределяются для каждого n.
Vitus
1
@misterbee Но на самом деле было бы неплохо получить какую-то гарантию от компилятора; своего рода контроль над размещением в памяти конкретной сущности. Иногда мы хотим поделиться, иногда мы хотим предотвратить это. Я полагаю / надеюсь, что это должно быть возможно ...
Уилл Несс
1
@ElizaBrandt, я имел в виду, что иногда мы хотим пересчитать что-то тяжелое, чтобы оно не оставалось для нас в памяти - то есть стоимость пересчета ниже, чем стоимость огромного сохранения памяти. одним из примеров является создание набора мощности: in pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]мы действительно хотим, pwr xsчтобы их вычисляли независимо, дважды, чтобы его можно было собирать мусором на лету, когда он создается и потребляется.
Уилл Несс
23

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

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

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

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

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

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

Тихон Джелвис
источник
Вы имели в виду, возможно, " fib' nмог бы быть другим на другом n"?
Will Ness
Думаю, я не очень понял: я имел в виду, что все внутри fib, в том числе fib', могло отличаться от всего n. Я думаю, что исходный пример немного сбивает с толку, потому что он fib'также зависит от того, nкоторый затеняет другой n.
Тихон Джелвис
20

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

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

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

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

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

fib :: Int -> Integer

Таким образом, есть только один список (типа [Integer]) для запоминания.

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

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

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

Для Haskell вам не нужна функция Memoize. Эти функции нужны только эмпирическому языку программирования. Однако Haskel - это функциональный язык и ...

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

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

zipWith - это функция из стандартного Prelude:

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 с

Валерий Кобзарь
источник
Это отличное решение!
Ларри