[Haskell-beginners] Memoization
Shawn Willden
shawn-haskell at willden.org
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.
More information about the Beginners
mailing list