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))开发者_StackOverflow社区 ) (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?
unfoldr (\(p1, p2) -> let x = f p1 p2 in Just (x, (x, p1)) ) (0, 1)
where f = arbitrary, possibly time-consuming function
in Control.Arrow there is (&&&) which can be used in something like this:
unfoldr (\(p1,p2) -> (Just . (id &&& flip (,) p1)) (p1+p2)) (0,1)
or even:
unfoldr (Just . (fst &&& id) . (uncurry (+) &&& fst)) (0,1)
As well in your example p1+p2 is actually next p1 so you can rewrite it like
tail (unfoldr (\(p1, p2) -> Just (p1, (p1+p2, p1)) ) (0, 1))
加载中,请稍侯......
精彩评论