我需要一个函数来做到这一点:
>>> 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)
看起来@Benjamin霍奇森误读了你的问题,并认为你想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
在状态 monad 中操作,为可遍历对象的元素添加一个递增索引(并"免费"获取长度,无论这意味着什么):
> indexed ['a','b','c']
([(0,'a'),(1,'b'),(2,'c')],3)
而且,正如 Ben 指出的那样,它也可以使用mapAccumL
编写:
indexed = swap . mapAccumL (k x -> (k+1, (k, x))) 0
然后,scanMap
获取可遍历的对象,将其映射到类似的前后对结构,使用indexed
为其编制索引,并应用一系列partial
函数,其中partial i
为前i
元素选择"afters",为其余元素选择"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]
而且完全不清楚您希望它在这里做什么。
在列表中,我会使用以下方法。如果需要,可以随意丢弃第一个元素。
> 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
将可折叠设备转换为列表之后。不过,人们可能仍然想要一个更好的实现来避免这一步,特别是如果我们想保留原始的可折叠类型,而不仅仅是获取列表。
根据您的问题,我只是称它为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,它捕获了状态monad中的遍历模式。
这听起来有点像没有焦点的拉链; 也许是这样的:
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