[Haskell-cafe] Repeated function application

Dan Weston westondan at imageworks.com
Thu Feb 21 14:20:31 EST 2008


Ben Butler-Cole wrote:
> Hello
> 
> I was surprised to be unable to find anything like this in the standard libraries:
> 
> times :: (a -> a) -> Int -> (a -> a)
> times f 0 = id
> times f n = f . (times f (n-1))
> 
> Am I missing something more general which would allow me to repeatedly apply a function to an input? Or is this not useful?

Invariably, this seems to invite a stack overflow when I try this (and 
is usually much slower anyway). Unless f is conditionally lazy, f^n and 
f will have the same strictness, so there is no point in keeping nested 
thunks.

If you apply f immediately to x, there is no stack explosion and faster 
runtime:

times :: (a -> a) -> Int -> (a -> a)
times f !n !x | n > 0     = times f (n-1) (f x)
               | otherwise = x

Dan



More information about the Haskell-Cafe mailing list