Динамическое программирование (Haskell, последовательность Hofstader M / F)

Question

Это работает:

f :: Int -> Int
f n = gof n where
      gof 0 = 1
      gof i = i - ms!! ( fs!! (i-1) )
      gom 0 = 0
      gom i = i - fs!! ( ms!! (i-1) )
      fs = [gof j | j <- [0..n]]
      ms = [gom j | j <- [0..n]]

m n = gom n where
      gof 0 = 1
      gof i = i - ms!! ( fs!! (i-1) )
      gom 0 = 0
      gom i = i - fs!! ( ms!! (i-1) )
      fs = [gof j | j <- [0..n]]
      ms = [gom j | j <- [0..n]]

Однако это действительно повторяется. Есть ли способ избежать повторения этих кусков кода? Несколько ссылок, это адаптация:

http://jelv.is/blog/Lazy-Dynamic-Programming/

Последовательность ref:

https://en.wikipedia.org/wiki/Hofstadter_sequence

Я проверил это по номерам:

https://oeis.org/A005378 https://oeis.org/A005379

Он генерирует правильные числа и работает намного быстрее, чем базовый код, который не станет слишком высоким, пока не начнутся проблемы с глубиной рекурсии.

Answer 1

Или вы можете просто использовать один из множества memoization пакетов, который поддерживает взаимную рекурсивную функцию. Ниже приведена реализация, использующая monad-memo , которая требует, чтобы записанная функция была определена в монадической форме, но в остальном это просто прямой перевод вашей исходной реализации.

import Control.Monad.Memo
import Control.Monad.ST

-- Same function in monadic form
gof 0 = return 1
gof i = do
  -- gof is memoized on level 0
  fs <- memol0 gof (i-1)
  -- gom is on level 1
  ms <- memol1 gom fs
  return (i - ms)

-- Same here
gom 0 = return 0
gom i = do
  ms <- memol1 gom (i-1)
  fs <- memol0 gof ms
  return (i - fs)

-- Eval monadic form into normal Int -> Int function
fm :: Int -> Int
-- Data.Map-based memoization cache
fm = startEvalMemo . startEvalMemoT . gof

mm :: Int -> Int
mm = startEvalMemo . startEvalMemoT . gom   

-- Or much faster vector-based memoization cashe
fmv :: Int -> Int
-- We use two separate caches: mutable unboxed vectors of `(n+1)` length
fmv n = runST $ (`evalUVectorMemo`(n+1)) . (`evalUVectorMemo`(n+1)) . gof $ n

mmv :: Int -> Int
mmv n = runST $ (`evalUVectorMemo`(n+1)) . (`evalUVectorMemo`(n+1)) . gom $ n

-- This is quite fast in comparison to the original solution
-- but compile it with -O2 to be able to compute `f 1000000`
main :: IO ()
main =
    print ((fm 100000, mm 100000),(fmv 1000000, mmv 1000000))

Answer 2

Прежде всего, вы можете сопоставить с шаблоном в привязке верхнего уровня. Обычно это не означает, что происходит много интересного, но если вы хотите поделиться локальными помощниками между двумя привязками верхнего уровня, это может помочь.

m2 :: Int -> Int
f2 :: Int -> Int
(m2, f2) = (gom, gof)
  where
    gof 0 = 1
    gof i = i - ms !! ( fs !! (i-1) )
    gom 0 = 0
    gom i = i - fs !! ( ms !! (i-1) )
    fs = map gof [0..]
    ms = map gom [0..]

Вы заметите, что там есть еще один трюк. Вместо того, чтобы ограничивать списки fs и ms их максимальными размерами, я просто позволяю лениться справляться с их ограничением. Списки не будут созданы после того, как они были необходимы для запоминания более ранних результатов.

Но индексирование списка - O (n). Избавление даже от некоторых из них может быть значительным ускорением. Если вы посмотрите на шаблон рекурсии для одной и той же функции, вы увидите, что gom i всегда вызывает gom (i-1), и то же самое с gof. Вы можете использовать это для удаления индексации списка в этих поисках, просто передав предыдущее значение. К сожалению, то же самое не относится к вызовам противоположной функции, поскольку они не так легко следуют. Но это все еще убирает большой объем работы. И это можно сделать таким образом, чтобы еще больше использовать лень:

m3, f3 :: Int -> Int
(m3, f3) = ((ms !!), (fs !!))
  where
    (ms, fs) = unzip pairs
    pairs = (0, 1) : zipWith iter [1..] pairs
    iter i (mp, fp) = (i - fs !! mp, i - ms !! fp)

Рекурсивные вспомогательные функции были заменены одновременным отложенным созданием обоих списков результатов. Этот шаблон отличается от стандартной рекурсии тем, что для него не требуется базовый случай, и ему требуется некоторая защита от попыток немедленно найти базовый случай, прежде чем будет предоставлен полный ответ. Эта модель известна как ко-рекурсия. (Или corecursion, если я набираю лениво.) Та же идея, но она дает ответ в противоположном направлении.