# Repeated function application

7 messages
Open this post in threaded view
|

## Repeated function application

 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? I thought this looked a bit like a fold, so I tried expressing it like this: times f n x = foldl (flip (\$)) x (replicate n f) ... which horrifies me, but I can't help feeling that there must be a way to get rid of the explicit recursion. How would you implement times? Ben _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Repeated function application

 Ben Butler-Cole writes: > times :: (a -> a) -> Int -> (a -> a) > times f 0 = id > times f n = f . (times f (n-1)) > > Am I missing something more general > ...I can't help feeling that there must be a way to get rid of the >  explicit recursion. > > How would you implement times? Anything against (apart an auxiliary list, and "x" not curried away) times n f x = (iterate f x)!!n Jerzy Karczmarczuk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Repeated function application

 In reply to this post by Ben Butler-Cole Am Donnerstag, 21. Februar 2008 16:58 schrieb Ben Butler-Cole: > 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)) times f n = (!! n) . iterate f > […] Best wishes, Wolfgang _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Repeated function application

 In reply to this post by Ben Butler-Cole 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Fwd: Repeated function application

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