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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe