保存并传递先前结果的映射

Question

当在Haskell中通过三对角矩阵算法求解线性方程组时,我遇到了以下问题.

我们有三个载体:a,b并c,我们想使第三矢量c'是它们的组合:

c'[i] = c[i] / b[i], i = 0
c'[i] = c[i] / (b[i] - a[i] * c'[i-1]), 0 < i < n - 1
c'[i] = undefined, i = n - 1

在Haskell中实现上面的公式如下:

calcC' a b c = Data.Vector.generate n f
  where
    n = Data.Vector.length a
    f i = 
      | i == 0 = c!0 / b!0 
      | i == n - 1 = 0
      | otherwise = c!i / (b!i - a!i * f (i - 1))

看起来这个函数由于重复而calcC'具有复杂度O(n ²).但我们所需要的只是通过f先前生成的值向内部函数传递一个参数.

我编写了我自己的generate复杂度O(n)和辅助函数的版本mapP:

mapP f xs = mapP' xs Nothing
  where
    mapP' [] _ = []
    mapP' (x:xs) xp = xn : mapP' xs (Just xn)
      where
        xn = f x xp

generateP n f = Data.Vector.fromList $ mapP f [0 .. n-1]

可以看出,mapP行为类似于标准map,但也传递给先前生成的值或Nothing第一次调用的映射函数.

我的问题:在Haskell中有没有相当标准的方法可以做到这一点？我不是要重新发明吗？

谢谢.

Answer 1

有两种称为标准功能mapAccumL和mapAccumR该做的正是你想要的.

mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

基本上,他们表现得像组合fold和map.

map   f   = snd . mapAccumL (\_ x -> (()   , f x) ()
foldl f b = fst . mapAccumL (\b x -> (f b x, () ) b