CODEWITHSUNDEEP
haskell
Xander Dunn
Xander Dunn

Reputation: 2402

Haskell replaceValues function

I want to write a function which takes a list of elements l, a list of indices i, and a list of replacement values v. The function will replace the values in l corresponding to the indices in i with the corresponding value in v.

Example: If l = [1,2,3,4,5,6], i = [0,2], and v = [166,667], then replaceValues l i v == [166,2,667,4,5,6]

My function:

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

This function manages to correctly replace the value at the first index in i, but it misplaces all of the following values. In the example above, it would give the output [166,667,3,4,5,6].

Upvotes: 1

Views: 212

Answers (3)

barsoap
barsoap

Reputation: 3376

The first thing that springs to mind is that you should use a list of tuples to specify the replacement, that is, work with

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

... you can use zip to convert your two lists into that format. Then I'm going to stipulate that that list is sorted by the first element of the tuple (sortBy), and that there are no duplicate indices in it (nubBy). The rest is a simple recursion, replacing as you go, with linear complexity and being maximally lazy:

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"

Beware of the code, though, I have only proven it to be correct, not actually tried it.

Using a map works too, of course, but then you're dealing with an complexity of O(m log m + n log m) (construct map + n times lookup) instead of O(n), or, taking sorting into account, O(n + m log m), as well as lose the capability of being lazy in case your list is already sorted and have the replacements incrementally garbage collected while you traverse.

nubBy from the library has quadratic complexity, but as the list is sorted it can be dealt with in linear time, too, just replace the call to error with a recursive call throwing away superfluous (i,r)s.

Upvotes: 2

jdevelop
jdevelop

Reputation: 12296

as said before, use tuples - but don't forget about pattern matching. Or use Map if you are not dealing with large collections

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

Upvotes: 0

ivanm
ivanm

Reputation: 3927

The problem with your implementation is that you aren't keeping track of which index you're currently at.

First of all, you're better off considering using [(Int,a)] rather than [Int] and [a] arguments separate to ensure that the "lists" are equal in length.

An alternate implementation is as follows:

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

What's happening here:

  • Tag each value with its index

  • See if there's a replacement value for that index: if there is, use it; otherwise, use the original value.

Upvotes: 3

Related Questions