[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