How to apply a function over a list using previous outputs as arguments?

Question

I have a function f :: (a -> a) -> a -> ((a -> a), a). (In the specific case a is Int, but that is irrelevant.)

I have a function initial :: a -> a, and a list of inputs (inputs :: [a]).

I need to apply f to all the elements of inputs, but, for each, I need to take the fst part of the output of the previous iteration and feed it as the (a -> a) part of the input for the next. As the output, I need to have a list of type [a], which is the snd part of the outputs of each iteration.

How can I recursively apply f to the fst part of the output and the elements of inputs, while building up a list of the intermediate snd parts of the output?

Answer 1

You may like mapM. Below I give it the type it has, a specialization of that type, the newtype unwrapping of the specialized type, and a further specialization. The final type should look quite familiar to you. I use ~:: to informally mean "approximately has the type".

mapM  :: Monad m => (a -> m b) -> [a] -> m [b]
mapM  :: (a -> State s b) -> [a] -> State s [b]
mapM ~:: (a -> s -> (s, b)) -> [a] -> s -> (s, [b])
mapM ~:: (a -> (a -> a) -> (a -> a, a)) -> [a] -> (a -> a) -> (a -> a, [a])

The last type describes exactly what you want to do: it can take (a slightly modified) f, inputs, and initial as arguments, and produce the list of outputs (along with some auxiliary information).

Answer 2

Sounds to me like scanl could help:

scanl g (initial, undefined) xs
  where g (i,_) a = f i a

To remove the initial element from the result list (which will always be 1 longer than the input list), apply a tail to the result.