Haskell：记忆 [英] Haskell: memoization

问题描述

我试图重新学习Haskell，经过很多年，忘记了一切，我发现自己仍然对我的 memoization 感到困惑。特别是，我试图编写一个程序来产生 n 对象的错位数目 D [n] （在原始位置没有项目的排列）;数字 D [n] 可以通过 D [1] = 0 ， D [2] = 1 ， D [n] =（n-1）（D [n-1] + D [n-2]）



所以这个工作：



  der :: Int - >整数
 der n = lder !! n 
其中lder = 1：0：zipWith3（\ n d1 d2  - > n *（d1 + d2））[1 ..] lder（tail lder）
  
 
 
 
同样如此（这有点笨拙，因为它需要三个函数）：
  nder :: Int  - >整数
 nder n = nderTab！ n 
 
 nderTab :: [Integer] 
 nderTab = [nderCalc n | n<  -  [0 ..]] 
 
 nderCalc :: Int  - >整数
 nderCalc n 
 | n == 0 = toInteger 1 
 | n == 1 = toInteger 0 
 |否则= toInteger（n-1）*（nder（n-1）+ nder（n-2））
  
但是这并不是： 
 
 
  nders :: Int  - >整数
 nders n =（地图der [0 ..]）!! n 
其中der 0 = 1 
 der 1 = 0 
 der n =（nders（n-2）+ nders（n-1））* toInteger（n-1）
  
您将最后识别为标准记忆斐波那契数字函数的副本。我的函数可以工作，但不会被记忆，因为它挂在大于30左右的值上。另外，如果我编写这个函数只对大于或等于1的值进行操作：
  nders :: Int  - >整数
 nders n =（地图der [1 ..]）!! n 
其中der 1 = 0 
 der 2 = 1 
 der n =（nders（n-2）+ nders（n-1））* toInteger（n-1）
  
完全不起作用。 
解决方案
使用 
 $ b我很好奇，想知道最后两个函数有什么问题。 $ b 
  nders :: Int  - >整数
 nders n =（地图der [0 ..]）!! n 
其中der 0 = 1 
 der 1 = 0 
 der n =（nders（n-2）+ nders（n-1））* toInteger（n-1）
  
  map der [0 ..] 部分将会重新计算任何 nders 的应用程序，特别是包含 der 中的递归调用。
 
 
 
您可以移出制表符的定义，以便它不会（语法上）依赖于 n ，这应该做正确的事情：
  nders :: Int  - >整数
 nders =（memoized !!）
其中
 memoized = map der [0 ..] 
 $ b $ der 0 = 1 
 der 1 = 0 
 der n =（nders（n-2）+ nders（n-1））* toInteger（n-1）
  
 
I'm trying to relearn Haskell, after many years away and forgetting everything, and I find myself still confused my memoization. In particular, I'm trying to write a program to generate the number of derangements D[n] of n objects (permutations with no item in its original place); the numbers D[n] can be defined recursively by D[1]=0, D[2]=1, D[n]=(n-1)(D[n-1]+D[n-2]).

So this works:
der :: Int -> Integer
der n = lder !! n
  where lder = 1 : 0 : zipWith3 (\n d1 d2 -> n * (d1+d2)) [1..] lder (tail lder)
as does this (which is a bit clumsy as it requires three functions):
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))
But this doesn't:
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)
You'll recognize this last as a copy of the standard memoized Fibonacci number function.  My function works, but isn't memoized, as it hangs on values larger than about 30.  Also, if I write this function to operate only on values greater than or equal to 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)
it doesn't work at all. I'm curious to know what's wrong with these last two functions.
解决方案
With
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)
the map der [0..] part will be recomputed for any application of nders, especially including the recursive calls in der.

You can move out the definition of the tabulation so that it doesn't (syntactically) depend on n, which should do the right thing:
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)


                        
这篇关于Haskell：记忆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！