Mapping while showing intermediate states

Question

I need a function that does this:

>>> func (+1) [1,2,3]
[[2,2,3],[2,3,3],[2,3,4]]

My real case is more complex, but this example shows the gist of the problem. The main difference is that in reality using indexes would be infeasible. The List should be a Traversable or Foldable.

EDIT: This should be the signature of the function:

func :: Traversable t => (a -> a) -> t a -> [t a]

And closer to what I really want is the same signature to traverse but can't figure out the function I have to use, to get the desired result.

func :: (Traversable t, Applicative f) :: (a -> f a) -> t a -> f (t a)

Answer 1

It looks like @Benjamin Hodgson misread your question and thought you wanted f applied to a single element in each partial result. Because of this, you've ended up thinking his approach doesn't apply to your problem, but I think it does. Consider the following variation:

import Control.Monad.State

indexed :: (Traversable t) => t a -> (t (Int, a), Int)
indexed t = runState (traverse addIndex t) 0
  where addIndex x = state (\k -> ((k, x), k+1))

scanMap :: (Traversable t) => (a -> a) -> t a -> [t a]
scanMap f t =
  let (ti, n) = indexed (fmap (\x -> (x, f x)) t)
      partial i = fmap (\(k, (x, y)) -> if k < i then y else x) ti
  in  map partial [1..n]

Here, indexed operates in the state monad to add an incrementing index to elements of a traversable object (and gets the length "for free", whatever that means):

> indexed ['a','b','c']
([(0,'a'),(1,'b'),(2,'c')],3)

and, again, as Ben pointed out, it could also be written using mapAccumL:

indexed = swap . mapAccumL (\k x -> (k+1, (k, x))) 0

Then, scanMap takes the traversable object, fmaps it to a similar structure of before/after pairs, uses indexed to index it, and applies a sequence of partial functions, where partial i selects "afters" for the first i elements and "befores" for the rest.

> scanMap (*2) [1,2,3]
[[2,2,3],[2,4,3],[2,4,6]]

As for generalizing this from lists to something else, I can't figure out exactly what you're trying to do with your second signature:

func :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a)

because if you specialize this to a list you get:

func' :: (Traversable t) => (a -> [a]) -> t a -> [t a]

and it's not at all clear what you'd want this to do here.

Answer 2

On lists, I'd use the following. Feel free to discard the first element, if not wanted.

> let mymap f [] = [[]] ; mymap f ys@(x:xs) = ys : map (f x:) (mymap f xs)
> mymap (+1) [1,2,3]
[[1,2,3],[2,2,3],[2,3,3],[2,3,4]]

This can also work on Foldable, of course, after one uses toList to convert the foldable to a list. One might still want a better implementation that would avoid that step, though, especially if we want to preserve the original foldable type, and not just obtain a list.