Отображение, которое содержит и передает предыдущий результат

При решении системы линейных уравнений с помощью трехдиагонального матричного алгоритма в 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(n2) из-за повторяемости. Но все, что нам на самом деле нужно, это передать во внутреннюю функцию 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? Разве я не изобретаю колесо?

Спасибо.


map haskell
person Andrey    schedule 26.03.2011    source источник

Ответы (3)


arrow_upward
10
arrow_downward

Есть две стандартные функции, называемые mapAccumL и mapAccumR< /a> которые делают именно то, что вы хотите.

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
person Heinrich Apfelmus    schedule 26.03.2011
comment
Спасибо за ваш ответ. После вашего комментария я нашел функцию предварительного сканирования в библиотеке Data.Vector, которая, похоже, представляет собой комбинацию моих generateP и mapP. - person Andrey; 26.03.2011

arrow_upward
1
arrow_downward

Если вы используете Data.Array, что является ленивым, вы можете напрямую выразить повторение, ссылаясь на c' при определении c'.

person augustss    schedule 26.03.2011

arrow_upward
1
arrow_downward

Следующий код кажется самой простой реализацией приведенной выше формулы в моем случае:

import qualified Data.Vector.Generic as V

calcC' a b c = V.postscanl' f 0.0 $ V.zip3 a b c
  where
    f c' (a, b, c) = c / (b - a * c')

Спасибо авторам Vector, которые добавили полезный метод postscanl'.

person Andrey    schedule 28.03.2011