Блог

Я хочу написать функцию, которая принимает список элементов l, список индексов i и список замещающих значений v. Функция заменит значения в l, соответствующие индексам в i, на соответствующее значение в v.

Пример: Если l = [1,2,3,4,5,6], i = [0,2] и v = [166,667], то replaceValues l i v == [166,2,667,4,5,6]

Моя функция:

 --Replace the values in list l at indices in i with the
--  corresponding value in v
replaceValues :: [a] -> [Int] -> [a] -> [a]
replaceValues l [] [] = l
replaceValues l i v = x    [head v]    (replaceValues (tail y) shiftedIndices (tail v))
    where
        (x,y) = splitAt (head i) l
        --The indices must be shifted because we are changing the list
        shiftedIndices = map ((-)((head i)   1)) (tail i)
  

Этой функции удается корректно заменить значение в первом индексе в i, но она неправильно помещает все следующие значения. В приведенном выше примере это дало бы результат [166,667,3,4,5,6].

Проблема с вашей реализацией заключается в том, что вы не отслеживаете, в каком индексе вы находитесь в данный момент.

Прежде всего, вам лучше рассмотреть возможность использования раздельных аргументов [(Int,a)] вместо [Int] и [a] , чтобы гарантировать, что «списки» равны по длине.

Альтернативная реализация заключается в следующем:

 import Data.Maybe(fromMaybe)
import qualified Data.IntMap as M

replaceValues :: [a] -> [(Int,a)] -> [a]
replaceValues as rs = map rep $ zip [0..] as
  where
    rsM = M.fromList rs

    rep (i,a) = fromMaybe a $ M.lookup i rsM
  

Что здесь происходит:

• Помечайте каждое значение его индексом

• Посмотрите, есть ли заменяющее значение для этого индекса: если есть, используйте его; в противном случае используйте исходное значение.

Первое, что приходит на ум, это то, что вы должны использовать список кортежей для указания замены, то есть работать с

 l = [1,2,3,4,5,6]
r = [(0,166),(2,667)]
  

… вы можете использовать zip для преобразования ваших двух списков в этот формат. Затем я собираюсь оговорить, что этот список отсортирован по первому элементу кортежа ( sortBy ), и что в нем нет повторяющихся индексов ( nubBy ). Остальное — простая рекурсия с заменой по мере выполнения, с линейной сложностью и максимальной ленивостью:

 replaceValues :: [a] -> [(Int, a)] -> [a]
replaceValues xs rs = f 0 xs rs
  where
    f _ xs [] = xs
    f _ [] _  = []
    f n (x:xs) is@((i,r):is')
        | n < i  = x:f (n 1) xs is
        | n == i = r:f (n 1) xs is'
        | otherwise = error "Can't happen"
  

Однако остерегайтесь кода, я только доказал его правильность, на самом деле не пробовал его.

Использование карты, конечно, тоже работает, но тогда вы имеете дело со сложностью O (m log m n log m) (построение карты n-кратный поиск) вместо O (n), или, принимая во внимание сортировку, O (n m log m), а также теряете возможность лениться, если ваш список уже отсортирован, и во время обхода вы постепенно собираете мусор для замен.

nubBy из библиотеки имеет квадратичную сложность, но поскольку список отсортирован, с ним также можно справиться за линейное время, просто замените вызов error рекурсивным вызовом, отбрасывающим лишние (i,r) s.

как говорилось ранее, используйте кортежи, но не забывайте о сопоставлении с шаблоном. Или используйте Map, если вы не имеете дело с большими коллекциями

 replaceValues :: [a] -> [Int] -> [a] ->[a]
replaceValues a b i = map fst $ f (zip a [0..]) (zip b i)
    where
        f [] _ = []
        f xs [] = xs
        f ((x,i):xs) s2@((j,y):ys) | i == j = (y,i) : f xs ys
                                   | otherwise = (x,i) : f xs s2