haskell - 动态规划(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/

序列引用:

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

我对照数字核对了它:

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

它生成正确的数字，并且比基本代码快得多，基本代码在开始出现递归深度问题之前根本不会太高。

Answer 1

首先，您可以在顶级绑定(bind)中进行模式匹配。通常这并不意味着发生了很多有趣的事情，但如果您想在两个顶级绑定(bind)之间共享本地助手，它会有所帮助。

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，如果我懒惰打字的话。)同样的想法，但它会产生相反方向的答案。