Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I factor this Haskell expression to avoid repeated computation?

I have this function (produces the fibonacci sequence):

unfoldr (\(p1, p2) -> Just (p1+p2, (p1+p2, p1)) ) (0, 1)

In here, I notice a repeated expression, p1+p2, which I would like to factor so that it is only calculated once. Addition itself isn't an expensive calculation, but for a more general version:

unfoldr (\(p1, p2) -> Just (f p1 p2, (f p1 p2, p1)) ) (0, 1)
    where f = arbitrary, possibly time-consuming function

In the above situation, f p1 p2 is calculated twice (unless there's some magic compiler optimisation I don't know about), which could create a performance bottleneck if f required a lot of computation. I can't factor f p1 p2 into a where because p1 and p2 are not in scope. What is the best way to factor this expression so that f is only calculated once?

like image 799
guhou Avatar asked Jul 10 '10 13:07

guhou


1 Answers

unfoldr (\(p1, p2) -> let x = f p1 p2 in Just (x, (x, p1)) ) (0, 1)
    where f = arbitrary, possibly time-consuming function
like image 113
sepp2k Avatar answered Sep 28 '22 05:09

sepp2k