With a recursive function of more than one argument, does it make sense to keep the arguments that tend to remain constant closer to the front? I.e. is this:
interp :: a -> [a] -> [a] interp y [] = [] interp y (x:[]) = x:[] interp y (x:xs) = x:y:interp y xs
any better than this:
interp :: [a] -> a -> [a] interp [] y = [] interp (x:[]) y = x:[] interp (x:xs) y = x:y:interp xs y
Will any implementations notice interp y x:xs calls interp y, and keep some sort of interp y partial application around? (I don't really expect any effect like this, but even if there were one, I would expect consideration like the fact that "interp constant" is a useful function, while "\x -> interp x const-list" is not so useful to outweigh any such effect. Happily, they don't conflict here. If there is no effect like this, would it make any sense to try to get something similar by hand, and can this actually be done?) -- Aaron Denney -><-
Aaron Denney <wnoise@ofb.net> writes:
With a recursive function of more than one argument, does it make sense to keep the arguments that tend to remain constant closer to the front?
i.e.
Will any implementations notice interp y x:xs calls interp y, and keep some sort of interp y partial application around?
Hugs (and before it, Gofer) implements this optimisation. It saves a small amount of memory by re-using the "root" portion of the original call in the recursive call. As far as I know, no other implementation makes use of this possibility, mainly because every system except Hugs uses vector heap cells instead of chained binary cells. I.e. in ghc, hbc, or nhc98, the function application is represented internally as ( interp y xs ) whereas in Hugs it is represented as ( ( interp y ) xs ) and the latter enables the re-use of the leading portion, whilst the former does not. Regards, Malcolm
Aaron Denney <wnoise@ofb.net> writes:
With a recursive function of more than one argument, does it make sense to keep the arguments that tend to remain constant closer to the front?
i.e.
Will any implementations notice interp y x:xs calls interp y, and keep some sort of interp y partial application around?
Systems which perform lambda-lifting will usually be tuned this way, as the same optimization also speeds up tail recursion. For example: interp y xs = interpaux xs where interpaux [] = ... interpaux (x:xs) = ... interpaux xs ... Will be lambda-lifted to the original interp definition, with an extra call: interp y xs = interpaux y xs interpaux y [] = ... interpaux y (x:xs) = ... interpaux y xs ... This one of the reasons nhc does this optimization, I'm sure. I know the Eager Haskell compiler avoids pushing and popping the invariant arguments from the stack during a tail call; I recall that hbc does so as well. -Jan-Willem Maessen Eager Haskell Project jmaessen@mit.edu
On Tue, 18 Feb 2003 21:59:36 -0800 Aaron Denney <wnoise@ofb.net> wrote:
With a recursive function of more than one argument, does it make sense to keep the arguments that tend to remain constant closer to the front?
At least it is easier to use: if the list argument in foldr was the first, you ought to write f (\ x -> foldr x (+) 0) instead of f (foldr (+) 0) Choosing the argument that is "less variable" as the first argument of a function saves typing and cleans up code. Vincenzo -- Teatri vuoti e inutili potrebbero affollarsi se tu ti proponessi di recitare te [CCCP]
On Tue, 18 Feb 2003, Aaron Denney wrote:
With a recursive function of more than one argument, does it make sense to keep the arguments that tend to remain constant closer to the front?
I.e. is this:
interp :: a -> [a] -> [a] interp y [] = [] interp y (x:[]) = x:[] interp y (x:xs) = x:y:interp y xs
any better than this:
interp :: [a] -> a -> [a] interp [] y = [] interp (x:[]) y = x:[] interp (x:xs) y = x:y:interp xs y
Will any implementations notice interp y x:xs calls interp y, and keep some sort of interp y partial application around?
(I don't really expect any effect like this, but even if there were one, I would expect consideration like the fact that "interp constant" is a useful function, while "\x -> interp x const-list" is not so useful to outweigh any such effect. Happily, they don't conflict here. If there is no effect like this, would it make any sense to try to get something similar by hand, and can this actually be done?)
GHC used to have an optimisation for static argument like this. It would turn both of the above programs into a similar form using a local recursive function: interp y xs = interpaux xs where interpaux [] = [] interpaux (x:[]) = x:[] interpaux (x:xs) = x:y:interpaux xs GHC doesn't do this anymore. The reason for this is unknown to me. /Josef
participants (5)
-
Aaron Denney -
Jan-Willem Maessen -
Josef Svenningsson -
Malcolm Wallace -
Nick Name