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.

Answer 3

I just called it func, per your question, because I couldn't think of a better name.

import Control.Monad.State

func f t = [evalState (traverse update t) n | n <- [0..length t - 1]]
    where update x = do
            n <- get
            let y = if n == 0 then f x else x
            put (n-1)
            return y

The idea is that update counts down from n, and when it reaches 0 we apply f. We keep n in the state monad so that traverse can plumb n through as you walk across the traversable.

ghci> func (+1) [1,1,1]
[[2,1,1],[1,2,1],[1,1,2]]

You could probably save a few keystrokes using mapAccumL, a HOF which captures the pattern of traversing in the state monad.

Answer 4

This sounds a little like a zipper without a focus; maybe something like this:

data Zippy a b = Zippy { accum :: [b] -> [b], rest :: [a] }

mapZippy :: (a -> b) -> [a] -> [Zippy a b]
mapZippy f = go id where
  go a [] = []
  go a (x:xs) = Zippy b xs : go b xs where
    b = a . (f x :)

instance (Show a, Show b) => Show (Zippy a b) where
  show (Zippy xs ys) = show (xs [], ys)


mapZippy succ [1,2,3]
-- [([2],[2,3]),([2,3],[3]),([2,3,4],[])]

(using difference lists here for efficiency's sake)

To convert to a fold looks a little like a paramorphism:

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f b [] = b
para f b (x:xs) = f x xs (para f b xs)

mapZippy :: (a -> b) -> [a] -> [Zippy a b]
mapZippy f xs = para g (const []) xs id where
  g e zs r d = Zippy nd zs : r nd where
    nd = d . (f e:)

For arbitrary traversals, there's a cool time-travelling state transformer called Tardis that lets you pass state forwards and backwards:

mapZippy :: Traversable t => (a -> b) -> t a -> t (Zippy a b)
mapZippy f = flip evalTardis ([],id) . traverse g where
  g x = do
    modifyBackwards (x:)
    modifyForwards (. (f x:))
    Zippy <$> getPast <*> getFuture