[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