如何使用以前的输出作为参数将函数应用于列表

Question

我有一个函数f :: (a -> a) -> a -> ((a -> a), a)。（在特定情况下，a是Int，但这无关紧要。）

我有一个函数initial :: a -> a和一个输入列表（inputs :: [a]）。

我需要将f应用于inputs的所有元素，但对于每个元素，我需要获取上一次迭代输出的fst部分，并将其作为下一次迭代输入的(a -> a)部分。作为输出，我需要有一个类型为[a]的列表，它是每次迭代输出的snd部分。

如何递归地将f应用于输出的fst部分和inputs的元素，同时建立输出的中间snd部分的列表？

Answer 1

您可能喜欢mapM。下面我给出它的类型，该类型的特殊化，特殊化类型的newtype展开，以及进一步的特殊化。最后一种你应该很熟悉。我使用~::来非正式地表示"近似具有类型"。

mapM  :: Monad m => (a -> m b) -> [a] -> m [b]
mapM  :: (a -> State s b) -> [a] -> State s [b]
mapM ~:: (a -> s -> (s, b)) -> [a] -> s -> (s, [b])
mapM ~:: (a -> (a -> a) -> (a -> a, a)) -> [a] -> (a -> a) -> (a -> a, [a])

最后一种类型准确地描述了您想要做的事情：它可以使用（稍微修改的）f、inputs和initial作为参数，并生成输出列表（以及一些辅助信息）。

Answer 2

听起来scanl可能会有所帮助：

scanl g (initial, undefined) xs
  where g (i,_) a = f i a

要从结果列表中删除初始元素（它总是比输入列表长1），请对结果应用tail。