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?

what have you tried already - as of now this sounds like a homework/exercise - we would be doing for you. us where your tries are failling — epsilonhalbe, May 12 '16 at 20:51

Daniel Wagner · Answer 1 · 2016-05-12T22:10:15.293

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

great answer for a) not containing spoilers, and for b) providing insight to advanced haskellers as well — epsilonhalbe, May 12 '16 at 21:52

Ingo · Answer 2 · 2016-05-12T22:25:59.730

0

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.

edited May 12 '16 at 22:25

answered May 12 '16 at 22:04

Ingo

36,037
5
53
100

1

Perhaps throwing a `tail` out front would eliminate the danger of empty lists. – Daniel Wagner May 12 '16 at 22:12
Indeed, scanl returns a list that is always 1 element longer than the input list. – Ingo May 12 '16 at 22:24

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

2 Answers2