Fwd: [Haskell-cafe] Repeated function application
Thomas Hartman
tphyahoo at gmail.com
Fri Feb 22 14:50:39 EST 2008
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
>
More information about the Haskell-Cafe
mailing list