[Haskell-cafe] tail-recursing through an associative list

[Malcolm Wallace]

Seth Gordon <sethg at ropine.com> wrote:

> 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