CODEWITHSUNDEEP
haskell
jhu
jhu

Reputation: 460

Ways to apply an applicative functor multiple times

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

Upvotes: 6

Views: 609

Answers (2)

K. A. Buhr
K. A. Buhr

Reputation: 51129

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.

Upvotes: 0

David Young
David Young

Reputation: 10793

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.

Upvotes: 3

Related Questions