Как это memoacci-функция memoized?

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

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

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

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

fib :: Int -> Integer

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

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

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

Ответ 4

Вам не нужна функция memoize для Haskell. Для этого нужны только эмпирический язык программирования. Тем не менее, Haskel является функциональным lang и...

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

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

zipWith - это функция из стандартной прелюдии:

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.00018s