[Haskell-beginners] Improving Performance

[Robert Heumüller]

Hi again,

hoping to further increase performance i've decided to calculate
the distances between all points ahead of time and store the distance
values in a map of maps. Because of the symmetry of the matrix this
should work in O(0.5*n^2). Could you please take a look at the code and
tell me if this would be the way to go? I fear that i might actually
loose performance due to the lookuptime of the treemap compared to
recalculating the distance between two points?

Thank you very much :)

import qualified Data.Map as Map

data Point a = Pt a a deriving (Show, Eq, Ord)
manhattan (Pt x y) (Pt x' y') = abs (x' - x) + abs (y' - y)

dist' :: Num a => Point a -> [Point a] -> [(Point a, a)]
dist' p [] = []
dist' p l = zip l (map (manhattan p) l)

dist :: (Num a, Ord a) => Point a -> [Point a] -> Map.Map (Point a) a
dist p l = Map.fromList (dist' p l)

distmatrix :: (Num a, Ord a) => 
    [Point a] -> Map.Map (Point a) (Map.Map (Point a) a)
distmatrix (p:[]) = Map.empty 
distmatrix (p:ps) = Map.insert p (dist p ps) (distmatrix ps)

getdist' :: 
    (Num a, Ord a) => 
        Point a -> Point a -> Map.Map (Point a) (Map.Map (Point a) a)
-> a getdist' p1 p2 dm = (dm Map.! p1) Map.! p2

getdist :: 
    (Num a, Ord a) => 
        Point a -> Point a -> Map.Map (Point a) (Map.Map (Point a) a)
-> a getdist p1 p2 dm
    | Map.member p1 dm = getdist p1 p2 dm
    | otherwise = getdist' p2 p1 dm
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120701/43715685/attachment.pgp>