Display when 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 complicated, but this example shows the essence of the problem. The main difference is that in fact the use of indexes would not be feasible. Listshould be Traversableor Foldable.

EDIT : this must be a function signature:

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

And closer to what I really want, it is the same signature with traverse, but cannot understand which function I need to use in order to get the desired result.

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

Answer 1

, @Benjamin Hodgson , , f . - , , , . :

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]

indexed , ( "", ):

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

, , , mapAccumL:

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

scanMap , fmaps /, indexed partial, partial i "afters" " i " befores " .

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

- , , :

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

:

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

, .

Answer 2

. , .

> 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]]

Foldable, , toList . , , , , , .

Answer 3

func , .

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

, update n, 0, f. n , traverse n, .

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

, , mapAccumL, HOF, .

Answer 4

It sounds a bit like lightning without 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 differences lists here for effectiveness)

Converting to a crease looks a bit like 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 walks, there is a cool state transition transformer called Tardis , which allows you to transfer the state back and forth:

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