Отображение при отображении промежуточных состояний

Question

Мне нужна функция, которая делает это:

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

Мой реальный случай более сложный, но этот пример показывает суть проблемы. Основное отличие состоит в том, что в действительности использование индексов было бы невозможным. List должен быть Traversable или же Foldable,

РЕДАКТИРОВАТЬ: Это должно быть подписью функции:

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

И ближе к тому, что я действительно хочу, это та же подпись traverse но не могу понять, какую функцию я должен использовать, чтобы получить желаемый результат.

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

Answer 1

Похоже, @ Бенджамин Ходжсон неправильно понял ваш вопрос и подумал, что вы хотели 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 принимает перемещаемый объект, сопоставляет его с аналогичной структурой пар до и после, использует indexed индексировать его и применяет последовательность partial функции, где partial i выбирает "после" для первого i элементы и "преды" для отдыха.

> 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

Это звучит немного как молния без фокуса; может быть что-то вроде этого:

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],[])]

(используя списки различий здесь для эффективности)

Преобразовать в складку немного похоже на параморфизм:

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

Для произвольных обходов есть классный преобразователь состояния, путешествующий во времени, называемый Tardis, который позволяет передавать состояние вперед и назад:

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