[Haskell-cafe] Repeated function application

Dan Weston westondan at imageworks.com
Fri Feb 22 15:12:22 EST 2008


Actually, the second argument is already strict, and the ! doesn't make 
it any stricter (and is therefore gratuitous): when you evaluate the 
conditional (n == 0), n is evaluated.

Dan

Thomas Hartman wrote:
> On second thought... never mind.
> 
> The only thing of (somewhat marginal) interest that my latest comment
> adds is that the second argument doesn't need to be strict.
> 
> Otherwise my code is exactly identical to Dan's.
> 
> 2008/2/22, Thomas Hartman <tphyahoo at gmail.com>:
>> 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
>>   >
>>
> _______________________________________________
> 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