[Haskell-beginners] Memoization

Shawn Willden shawn-haskell at willden.org
Wed Oct 28 21:45:35 EDT 2009


I've just begun experimenting with Haskell, and I'm having a lot of fun, but 
my first semi-serious program is in need of some optimization, and based on 
the results of profiling I think a really good start is to memoize one 
particular function which is called many, many times (and currently consumes 
over 80% of the program run time).

The function takes a two-dimensional range and a location within that range 
and returns a list of the locations vertically and horizontally adjacent to 
that location and within the bounds

type Bounds = ((Int,Int),(Int,Int))
type Location = (Int,Int)
adjacentCells :: Bounds -> Location -> [Location]
adjacentCells bounds (col, row) = filter valid cells
      valid loc = inRange bounds loc
      neighborLoc' = [(col-1,row),(col+1,row),(col,row-1),(col,row+1)]

The ranges are fairly small -- certainly no more than 10x10, and each location 
has an associated list of at most 4 neighbors (edge locations have less).  
During a given run of the program, the bounds are fixed.

So, any tips on how I can memoize this function?  I have read the Memoization 
page on the wiki, and I understand (I think) the recursive memoization 
section, but it's not clear to me how to apply that approach.  Section one on 
non-recursive memoization seems like what I want, but I don't understand the 
section and the links provided haven't shed any light for me.

The section uses the following notation to describe how to construct a map to 
be used to hold the keys and values:

  Map ()            b  := b
  Map (Either a a') b  := (Map a b, Map a' b)
  Map (a,a')        b  := Map a (Map a' b)

but I'm not sure what that notation is.  It's not Haskell code, I don't think.

Any and all suggestions appreciated.



More information about the Beginners mailing list