Ways to apply an applicative functor multiple times

6
votes

Hello fellow Haskellers.

Let's say I have an applicative functor (not an instance of monad) I want to apply multiple times to a pure initial value. For example,

λ> Just (1+) <*> (Just (1+) <*> pure 0)
Just 2

If I want to generalize this to any number of consecutive applications, I can do it with a fold.

applyAppl :: Applicative f => f (a -> a) -> Int -> f a -> f a
applyAppl f n i = foldr (<*>) i $ replicate n f

After this definition,

λ> applyAppl (Just (1+)) 10 $ pure 0
Just 10

I have an awkward suspicion that the generalization could also be done with one of the higher-order builtin applicative tools such as sequenceA or traverse. Can it?

(Edited to take into account the first two comments below.)

2
haskell
Can you give the type of the function you're trying to write? - Chris Martin
What do you mean by "more easily"? Your function is a single line of code; it doesn't really get much easier than that. - user2407038
what simplification you want to do? I tried to think of something, but it really ended up to be some sort of folding, and you must call <*> to pull the function from applicative out to be a function in hask. - Jason Hu

2 Answers

3
votes

You could use iterate:

applyAppl :: Applicative f => f (a -> a) -> Int -> f a -> f a
applyAppl f n i = iterate (f <*>) i !! n

Loaded into GHCi:

ghci> applyAppl (Just (+1)) 10 (pure 0)
Just 10

I'm not sure that's necessarily better than your implementation, since I suspect both implementations fuse into something with essentially the same performance profile (though I haven't tested that), but it is different.

I've seen this sort of "iterate with (!!)" pattern for memoization so I'm pretty sure that, at the very least, it won't have worse performance.

0
votes

Perhaps you are looking for the following variation of @David Young's answer:

foo :: Applicative f => f (a -> a) -> Int -> a -> f a
foo f n i = fmap (($ i) . iterateN n) f
   where iterateN n f = (!! n) . iterate f

giving:

> foo (Just (1+)) 10 0
Just 10
>

This uses the "applicative machinery" in the form of the Functor instance for applicatives to perform both the functional iteration and the application without explicit use of <*>. I'm not sure what else you'd be hoping for here.