[Haskell-cafe] memoization

[Reid Barton]

On Sat, Sep 05, 2009 at 02:52:50AM -0700, staafmeister wrote:
> How would experienced haskellers solve this problem?

You could just memoize using an array, like in C.

import Data.Array

occurrences :: Num a => String -> String -> a
occurrences key buf = grid ! (0, 0)  -- grid ! (i, j) = occurrences (drop i key) (drop j buf)
  where grid = listArray ((0, 0), (nk, nb)) [
          if i == nk then 1
          else if j == nb then 0
               else (if key !! i == buf !! j then grid ! (i+1, j+1) else 0) + grid ! (i, j+1)
          | i <- [0..nk], j <- [0..nb]
          ]
        nk = length key
        nb = length buf

Regards,
Reid