Fwd: [Haskell-cafe] Repeated function application

[Thomas Hartman]

This was easier for me to understand when written so, with the start
 value explicit

 times3 :: (a -> a) -> Int -> (a -> a)
 times3 f n !start | n == 0 = start
                       | otherwise = times3 f (n-1) (f start)

 -- no stack overflow :)
 tTimes3 = times3 (+1) 1000000 0

 Here, only the third arg, the start value, needs to be
 "bangified/strictified", and it's pretty clear why. Without the bang
pattern, it stack overflows.

 What I'm not sure of is whether this version is in fact completely
 equivalent to Dan's version above.

 I hope it is.

 2008/2/21, Dan Weston <westondan at imageworks.com>:

> 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
 >
 >
 >  _______________________________________________
 >  Haskell-Cafe mailing list
 >  Haskell-Cafe at haskell.org
 >  http://www.haskell.org/mailman/listinfo/haskell-cafe
 >