6

我需要一个执行此操作的函数：

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

4 回答 4

3

看起来@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在状态 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获取可遍历对象，将其 fmap 到类似的前/后对结构，用于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]

而且完全不清楚您希望在这里做什么。

于 2017-05-11T02:08:07.007 回答
2

根据你的问题，我只是叫它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在 state monad 中，这样当你走过可遍历的地方时，它就traverse可以通过。n

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

您可能可以使用mapAccumL捕获状态单子中遍历模式的 HOF 来节省一些击键。

于 2017-05-10T19:19:40.020 回答
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将可折叠文件转换为列表之后。不过，人们可能仍然想要一个更好的实现来避免该步骤，特别是如果我们想要保留原始的可折叠类型，而不仅仅是获取一个列表。

于 2017-05-10T18:56:23.913 回答
1

这听起来有点像没有焦点的拉链；也许是这样的：

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

（为了提高效率，这里使用差异列表）

转换为 fold 看起来有点像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
于 2017-05-10T21:49:40.503 回答