Seth Gordon
almost-entirely-functional code ... that in its first draft, took about three seconds to process 2,000 rows, eight minutes to process 20,000 rows, and overflowed a 1-MB stack when processing 200,000 rows. Oops.
Which just goes to show that your algorithm is non-linear in the size of the input. I doubt that your posted snippet is the cause of the problem, since it is certainly linear in the AList it is given.
I profiled the code and observed that the most-called-upon function in the program (200 million entries for those 20,000 rows)
By optimisation, you can only make this function a constant factor faster. You need to work out how to call it less often in the first place.
type AList = [(Key, [MetaThingies])]
myFunction :: AList -> Thingie -> AList myFunction [] x = [(key x, [meta x])] myFunction ((k, v):tail) x | matchKeys k (key x) = case tryJoining v x of Nothing -> (k, v) : (myFunction tail x) Just v' -> (k', v') : tail where v' = bestKey k (key x) | otherwise = (k, v) : (myFunction tail x)
myFunction is clearly rather like a map (except that occasionally it stops before traversing the whole list). There is nothing wrong with its recursion pattern or otherwise. Regards, Malcolm