映射同時顯示中間狀態

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

看起來@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採用可遍歷的對象，將其映射到前/後對的相似結構，使用indexed來索引它，並應用一系列partial函數，其中partial i爲第一個i元素選擇「afters」，其餘爲「之前」。

> 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 

的想法是，從nupdate倒計數，當它到達0，我們應用f。我們保持n在狀態monad，以便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],[])] 

（使用差別在這裏列出了效率的緣故）

要轉換到摺疊看上去有點像一個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:) 

對於任意的遍歷，有一個酷時間旅行狀態變壓器稱爲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