Repeated function application

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Repeated function application

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))

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
Reply | Threaded
Open this post in threaded view
|

Re: Repeated function application

jerzy.karczmarczuk
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
Reply | Threaded
Open this post in threaded view
|

Re: Repeated function application

Wolfgang Jeltsch-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Repeated function application

Dan Weston
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
Reply | Threaded
Open this post in threaded view
|

Fwd: Repeated function application

tphyahoo
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
Reply | Threaded
Open this post in threaded view
|

Re: Repeated function application

tphyahoo
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 <[hidden email]>:

> 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
Reply | Threaded
Open this post in threaded view
|

Re: Repeated function application

Dan Weston
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 <[hidden email]>:
>> 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
>
>


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe