CODEWITHSUNDEEP
haskellrecursionmemoization
Alasdair
Alasdair

Reputation: 1354

Haskell: memoization

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.

Upvotes: 1

Views: 254

Answers (1)

Cactus
Cactus

Reputation: 27626

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)

Upvotes: 3

Related Questions