Wed Oct 28 21:45:35 EDT 2009

```Hi,

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
where
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.

Thanks,

Shawn.
```