Haskell:回忆录

Question

我正试图重新学习Haskell，在许多年后，忘记了一切，我发现自己仍然困惑我的回忆录。特别是，我正在编写一个程序来生成D[n] of n对象(没有项目的排列)；数字D[n]可以由D[1]=0、D[2]=1、D[n]=(n-1)(D[n-1]+D[n-2])递归定义。

因此，这是可行的：

der :: Int -> Integer
der n = lder !! n
  where lder = 1 : 0 : zipWith3 (\n d1 d2 -> n * (d1+d2)) [1..] lder (tail lder)

这一点也是如此(这有点笨拙，因为它需要三个功能)：

nder :: Int -> Integer
nder n = nderTab !! n

nderTab :: [Integer]
nderTab = [nderCalc n | n <- [0..]]

nderCalc :: Int -> Integer
nderCalc n
  | n == 0    = toInteger 1
  | n == 1    = toInteger 0
  | otherwise = toInteger (n-1) * (nder (n-1) + nder (n-2))

但这并不是：

nders :: Int -> Integer
nders n = (map der [0 ..]) !! n
  where der 0 = 1
        der 1 = 0
        der n = (nders (n-2) + nders (n-1)) * toInteger (n-1)

最后，您会发现这是标准回忆录Fibonacci数函数的副本。我的函数工作，但没有回忆录，因为它挂在大于30的值上。此外，如果我编写此函数仅对大于或等于1的值进行操作：

nders :: Int -> Integer
nders n = (map der [1 ..]) !! n
  where der 1 = 0
        der 2 = 1
        der n = (nders (n-2) + nders (n-1)) * toInteger (n-1)

它坏了。我很想知道最后两个函数有什么问题。

Answer 1

使用

nders :: Int -> Integer
nders n = (map der [0 ..]) !! n
  where der 0 = 1
        der 1 = 0
        der n = (nders (n-2) + nders (n-1)) * toInteger (n-1)

map der [0..]部分将为nders的任何应用程序重新计算，特别是包括der中的递归调用。

您可以移出表的定义，这样它就不会(在语法上)依赖于n，而n应该做正确的事情：

nders :: Int -> Integer
nders = (memoized !!)
  where 
    memoized = map der [0 ..]

    der 0 = 1
    der 1 = 0
    der n = (nders (n-2) + nders (n-1)) * toInteger (n-1)